Teorema de Hall

Question

Actualmente estoy estudiando el curso Math for CS en MIT OCW, estoy atascado en la siguiente pregunta para la que no encuentro solución:

A lo largo de los siglos, los estudiosos han identificado veinte virtudes virtudes humanas fundamentales: honradez, generosidad, lealtad, prudencia, completar la lectura semanal del curso, etc. lectura semanal, etc. Al principio del curso, cada alumno de 6.042 poseía exactamente ocho de estas virtudes. Además, cada alumno era único, es decir, no había dos alumnos que poseyeran exactamente el mismo conjunto de virtudes. exactamente el mismo conjunto de virtudes. El personal del curso 6.042 debe seleccionar una virtud adicional para impartir a cada estudiante al final del curso. del curso. Demuestre que existe un modo de seleccionar una virtud adicional para para cada alumno de modo que cada alumno sea único también al final del curso. también.

Sugerencia: Utiliza el teorema de Hall. Pruebe varias interpretaciones para los vértices de los lados izquierdo y derecho de tu grafo bipartito.

He dividido G en X e Y, donde X es el conjunto de virtudes con |X|=20 e Y es el alumno. Sé que la cardinalidad de cada vértice en X es 8, y que hay un emparejamiento único, pero no sé cómo avanzar.

Answer 1

Tenemos que contemplar la posibilidad de que haya ${20\choose 8}=125\,970$ estudiantes, cada uno de ellos incorporando otro conjunto de $8$ virtudes. Por otra parte, hay ${20\choose 9}=167\,960$ combinaciones de $9$ virtudes.

Por lo tanto, establecemos un grafo bipartito $G$ con un conjunto de vértices $L\cup R$ como sigue: A la izquierda tenemos ${20\choose 8}$ vértices $v$ que representan las colecciones de $8$ virtudes, y a la derecha tenemos ${20\choose 9}$ vértices $w$ que representan las colecciones de $9$ virtudes. De cada conjunto de ocho $v$ dibujar bordes a la $12$ nueve juegos $w$ que contiene $v$ como subconjunto.

Afirmo que esta gráfica cumple la condición del teorema de Hall.

Prueba. Considere cualquier subconjunto no vacío $P\subset L$ y que $Q\subset R$ sea el conjunto de vértices conectados al menos a un $v\in P$ . Existen $12|P|$ bordes que emanan de $P$ pero cualquier $w\in Q$ puede recibir como máximo $9$ de ellos. De ello se deduce que $$|Q|\geq{12|P|\over 9}>|P|\ .\qquad\square$$ Por tanto, el teorema de Hall garantiza la existencia de un emparejamiento perfecto. Un procedimiento práctico podría ser el siguiente: Utilizando una demostración constructiva del teorema de Hall, el personal del curso 6.042 establece una tabla de búsqueda para todas las correspondencias $v\mapsto w$ de una vez por todas. Cualquier estudiante que se inscriba en el curso tendrá que nombrar sus ocho virtudes, tras lo cual se le asignará una novena según la tabla.