Prueba de Konig ' teorema s en lenceria

Question

Estoy tratando de trabajar a través de una prueba de Konig del Teorema, y hay un par de pasos de donde yo estoy completamente atascado. Primero he estado el teorema y un bosquejo de la prueba, a continuación, mencionar donde estoy atascado, y toda la terminología se define como un anexo. Estoy esperando que alguien me puede ayudar!

$\bf\text{Konig's Theorem}$ Deje $(X,Y,E)$ $k$- regular bipartito gráfico. Entonces existe un perfecto maridaje de $X$$Y$.

$\bf\text{Proof}$:

$\color{blue}{(1)}$ Primero el problema se reduce al caso en que cada dos puntos en $V=X\cup Y$ están unidas por una ruta de acceso y el tanto $|X| =|Y| = \infty$.

$\color{blue}{(2)}$ Ahora fix $x\in X,y\in Y$, y definir $$ Z_{1} = \{x,y\} \cup V(\{x,y\})\text{ y } Z_{n} = V(Z_{n-1})\text{ para todo }n\geq 2. $$

y, a continuación,$X_{n} = X\cap Z_{n}, Y_{n} = Y\cap Z_{n}$, e $E_{n}$ es el conjunto de todas las aristas en $E$ se utiliza en la definición de $Z_{n}$.

$\color{blue}{(3)}$ Por cada $n\geq 1$, $(X_{n},Y_{n},E_{n})$ es un bipartito subgrafo en el que cada vértice es un punto final en la mayoría de las $k$ vértices.

Elegir un $k$-regular subgrafo $(X_{n}', Y_{n}', E_{n}')$ $(X,Y,E)$ tal que $(X_{n},Y_{n},E_{n})$ es un subgrafo de $(X_{n}', Y_{n}', E_{n}')$.

Por el teorema de Matrimonio, hay una perfecta adecuación de la $X_{n}'$$Y_{n}'$, lo que restringe a un perfecto maridaje de $X_{n}$ con un subconjunto de a $Y$.

$\color{blue}{(4)}$ Finalmente, definimos una secuencia $(F_{n})_{n=1}^{\infty}$ con las siguientes propiedades:

(i) $F_{n}$ es un perfecto maridaje de $X_{n}$ con un subconjunto de a $Y$.

(ii) $F_{j}\subset F_{n}$ siempre $j\leq n$.

(iii) Para todos los $m > n$, existe un perfecto maridaje $F_{m}'$ $X_{m}$ con un subconjunto de a $Y$ tal que $F_{n}\subset F_{m}$.

$\color{blue}{(6)}$ $F:=\bigcup_{n=1}^{\infty}F_{n}$ es un perfecto maridaje de $X$$Y$, lo que completa la prueba.

$\bf\text{Things I am completely stuck on:}$

$\color{red}{(1)}$ No veo cómo en el paso $\color{blue}{(3)}$ obtenemos un gráfico de $(X_{n}',Y_{n}',E_{n}')$. He trabajado un par de ejemplos, y parece fácil de hacer en cada caso concreto: sólo hay que añadir la cantidad suficiente de puntos o bordes cuando sean necesarias. Pero me parece que no puede abstraerse de la intuición en una prueba.

$\color{red}{(2)}$ I no parecen funcionar la existencia de dicha secuencia. Los detalles de la prueba de definir la secuencia inductiva. Por $k$-regularidad, hay sólo un número finito de maneras para formar un perfecto maridaje entre el $X_{1}$ y un subconjunto de a $Y$, por lo $F_{1}$ puede ser elegido para satisfacer $(i)$$(iii)$. Si $F_{1}\subset \dots F_{n}$ se definen satisfacer $(i)$$(iii)$, ya que hay sólo un número finito de maneras para formar un perfecto maridaje entre el $X_{n+1}$ y un subconjunto de $Y$, $F_{n+1}$ puede ser elegido para satisfacer $(i)$$(iii)$.

$\color{red}{(3)}$ Basado en la prueba, $F$ debe ser un perfecto maridaje entre el $X$ y un subconjunto de a $Y$. ¿Por qué esto nos da un perfecto maridaje de $X$$Y$?

(Nota: lo que más me preocupa con $\color{red}{(2)}$, me siento como $\color{red}{(1)}$ no es importante para comprender la gran idea de la prueba, y me siento como $\color{red}{(3)}$ amanecer en mí lo suficientemente pronto.

Muchas gracias a cualquiera que pueda que me lo explique!

$\bf\text{Background Terminology}$

Deje $(V,E)$ un gráfico.

$(V,E)$ $k$- regular si cada vértice $V$ es el extremo de exactamente $k$ bordes en $E$.

$(V,E)$ es bipartito si existe una partición de $\{A,B\}$ $V$ tales que cada arista en $E$ se une a un elemento de $A$ con un elemento de $B$. En este caso, $(X,Y,E)$ también significa $(V,E)$

Para un subconjunto $S\subset V$, $V(S)$ es el conjunto de todos los vértices en $V$ que se unen a un vértice en $S$ a través de algunos borde en $E$.

Para subconjuntos $A\subset X,B\subset Y$, un perfecto maridaje de $A$ $B$ es un subconjunto $F\subset E$ tal que $F$ es un bijection de$A$$B$.

$\bf\text{Marriage Theorem}$ Deje $(X,Y,E)$ $k$- regular bipartito grafo tal que $|X\cup Y| < \infty$. Entonces existe un perfecto maridaje de $X$$Y$.

Answer 1

(1) Corregido: Vamos A $G_n(0)=\langle X_n,Y_n,E_n\rangle$. Si $G_n(i)$ no $k$-regular, vamos a $G_n(i+1)$ ser la gráfica obtenida mediante la adición de la falta vecinos de los vértices de $G_n(i)$; de lo contrario vamos a $G_n(i+1)=G_n(i)$. A continuación, la unión de la $G_n(i)$ $i\in\Bbb N$ $k$- regular y ha $G_n(0)$ como subgrafo. Sin embargo, esta unión puede ser la gráfica original $\langle X,Y,E\rangle$, como puede apreciarse al considerar el caso en que $X$ es el conjunto de números enteros, $Y$ es el conjunto de enteros impares, y $x$ $y$ son adyacentes iff $|x-y|=1$: este gráfico es $2$-regular y conectado, y que no tiene finita $2$-regular subgrafo. Por lo tanto, parece ser una verdadera brecha en el argumento aquí, aunque el gráfico de la pregunta no admite un perfecto maridaje.

Lo que realmente se necesita es una finito de expansión de $\langle X_n,Y_n,E_n\rangle$ a un subgrafo $\langle X_n',Y_n',E_n'\rangle$ $\langle X,Y,E\rangle$ que satisface las hipótesis del teorema de matrimonio; me vas a tener que pensar un poco.

(2) sabemos que para cada una de las $n$ hay una perfecta adecuación de la $X_n$ con un subconjunto de a $Y$; deje $\mathscr{F}_n$ ser el conjunto de todos los perfectos de las asignaciones. Si $F_m\in\mathscr{F}_m,F_n\in\mathscr{F}_n$, e $m\le n$, escribir $F_m\preceq F_n$ fib $F_m$ es la restricción de $F_n$$X_m$. Deje $\mathscr{F}=\bigcup_{n\in\Bbb Z^+}\mathscr{F}_n$. Para cada una de las $F\in\mathscr{F}_1$ vamos $$N(F)=\{n\in\Bbb Z^+:F\preceq F_n\text{ for some }F_n\in\mathscr{F}_n\}\;;$$ $\mathscr{F}_1$ is finite, so there must be some $F_1\en\mathscr{F}_1$ such that $N(F_1)$ is infinite. This implies that $N(F_1)=\Bbb Z^+$; why? Now let $\mathscr{F}_2'=\{F\in\mathscr{F}_2:F_1\preceq F\}$; $\mathscr{F}_2'\ne\varnothing$ by the choice of $F_1$. For $F\in\mathscr{F}_2'$ let $$N(F)=\{n\ge 2:F\preceq F_n\text{ for some }F_n\in\mathscr{F}_n\}\;;$$ by the same reasoning as before there must be some $F_2\in\mathscr{F}_2'$ such that $N(F_2)$ is infinite and therefore equals $\{n\in\Bbb Z^+:n\ge 2\}$. Now let $\mathscr{F}_3'=\{F\in\mathscr{F}_3:F_2\preceq F\}$, and repeat. In this way you can recursively construct a sequence $\langle F_n:n\in\Bbb Z^+\rangle$ such that each $F_n$ is a perfect matching of $X_n$ with a subset of $S$, and $F_n$ extends $F_m$ whenever $m\le n$. (I'll leave it to you to write down the general step of the construction, from $F_n$ to $F_{n+1}$.)

Puesto que para cada una de las $m,n\in\Bbb Z^+$ los matchings $F_m$ $F_n$ está de acuerdo en $X_{\min\{m,n\}}$, $F=\bigcup_{n\in\Bbb Z^+}F_n$ es una coincidencia de $\bigcup_{n\in\Bbb Z^+}X_n=X$ con un subconjunto $Y_0$$Y$.

(3) Todo lo que queda es comprobar que $Y_0=Y$. La construcción en $\color{blue}{(3)}$ asegura que si $v\in X_n\cup Y_n$, entonces cada vecino de $v$ pertenece a $X_{n+k}\cup Y_{n+k}$. Por lo tanto, si $y\in Y$, hay un $n\in\Bbb Z^+$ tal que $y\in Y_n$, y cada vecino de $y$$X_n$. La coincidencia completa de $X_n'$ $Y_n'$ debe incluir un borde entre el $y$ y uno de estos vecinos, y que edge va a ser parte de la restricción de la coincidencia de a $X_n$. Por lo tanto, $y$ será usado en todos coincidentes en $\mathscr{F}_m$$m\ge n$, y de ello se sigue que $Y_0=Y$.