En el problema del matrimonio, si cada niña conoce al menos$m$ niños, entonces hay al menos$m!$ maneras de arreglar los matrimonios.

Question

Me estoy encontrando problemas relativos a la Sala del teorema muy difícil, incluso cuando no lo están. (Ver aquí por ejemplo. Estoy seguro de que no han dado con la solución en un millón de años, aunque es probablemente uno de los más simples soluciones a cualquier problema que he visto nunca.) Esta es, probablemente, demasiado fácil, pero no tengo idea de cómo acercarse a él. Por favor, si puedes, incluye en sus respuestas algunos consejos generales porque estoy empezando a sentir que no soy capaz de aprender a pensar acerca de estas cosas correctamente.

Supongamos que tenemos $n$ de las niñas y $k$ niños satisfactoria de la Sala condición para la existencia de un matrimonio de transcripción tales que cada una de las niñas se le da un marido. Supongamos además que cada niña sabe, al menos, $m$ varones ($m\leq n$). Estoy de demostrar que hay al menos $m!$ posibles maneras de arreglar los matrimonios.

En primer lugar, creo que podría ser una buena idea para cambiar la suposición de que los jóvenes satisfacer Sala de la condición a la suposición de que existe al menos un matrimonio disposición. Podemos hacer esto mediante el Hall del teorema, y esta es la idea de que me estaba perdiendo en el intento de resolver el problema vinculado.

Segundo, creo que debería ser posible para resolver esto a través de la inducción en $m$. Eso es porque hay un factorial involucrados. Al principio pensé que a partir de los enlaces de hecho podría inferir que cualquier chica podría casarse con alguien que ella conocía, y luego proceder por inducción de obtener el resultado, pero eso es incorrecto porque de la siguiente contraejemplo. Chicos: a,b; niñas: A,B; a conoce a; B sabe que a y b. Ahora es posible coincidir con todos ellos, pero B no puede casarse con un a pesar de que ella sabe que él.

Tercero, duele no entender lo que la suposición de que $m\leq n$ es para el, que yo no.

Esto es realmente todo lo que tengo. Aún no puedo resolver el problema de $m=2$. Entonces puedo asumir que tenemos cada una de las chicas casada con un chico y que cada uno conoce un chico de otro, a continuación, su marido. Entonces tengo que demostrar que puedo divorcio de las parejas y organizarlos de una manera diferente. Pero no sé cómo.

Answer 1

Es correcto que la inducción en $m$ puede ser utilizado para probar el resultado.

Primero vamos a introducir una notación. Deje $G$ denotar el bipartito gráfico con desdoblamiento $A,B$ donde $A$ es el conjunto de las niñas y los $B$ es el conjunto de los varones. También sabemos $|A|=k$, $|B|=n$ y $\deg(v)\geq m$ todos los $v\in A$.

Caso Base ($m=1$): Desde el Hall de la condición tiene por $A$, tenemos (por el Hall del teorema) de que existe una coincidencia de saturar todos los de $A$.

Inducción de la hipótesis: Supongamos que cualquier gráfico bipartito $G$ con desdoblamiento $A,B$, la satisfacción del Salón de la condición de $A$, y de tal manera que $\deg(v)\geq m$ todos los $v\in A$ admite $m!$ matchings saturando todos los de $A$.

Inductivo paso: Vamos a $G$ ser un bipartito gráfico como en la hipótesis inductiva donde $\deg(v)\geq m+1$ (en lugar de $\deg(v)\geq m$)$v\in A$. Vamos a mostrar que este gráfico admite $(m+1)!$ matchings saturar $A$.

Deje $a\in A$ ser tales que cada arista incidente a que se encuentra en una coincidencia de saturar todos los de $A$ (ver aquí para la existencia de dicho vértice). Deje $b_1,b_2,\ldots,b_{m+1}$ vecinos de $a$. Considere la gráfica de $H_i=G-\{a,b_i\}$. El gráfico de $H_i$ es bipartito, satisface la Sala de la condición de $A\setminus\{a\}$ (esto se deduce ya que en $G$ hay una perfecta coincidencia que contengan $ab_i$) y $\deg(v)\geq m$ todos los $v\in A\setminus\{a\}$. Por hipótesis de inducción, hay $m!$ elecciones en $H_i$ saturar $A\setminus\{a\}$. Cada una de estas elecciones en $H_i$ puede ser extendida a los matchings en $G$ contiene $ab_i$ y saturando todos los de $A$. El resultado de la siguiente manera de contar las elecciones, es decir, no se $m!$ elecciones en cada $H_i$, $1\leq i\leq m+1$ para un total de $(m+1)!$ elecciones.

Gracias a @darijgrinberg por su comentario.

Edit: Vértice $a\in A$ no puede ser elegido arbitrariamente, tiene que ser elegido de tal forma que cada arista incidente a que pertenece a una coincidencia de saturar todos los de $A$.