Frage zu Gewerkschaften von Sets
Lassen $n >0$ und $(X_i)_{i \in [\![ 1,n+1 ]\!]}$ nicht leere Teilmengen von sein $[\![ 1,n ]\!]$. Zeigen Sie, dass zwei nicht leere Teilmengen vorhanden sind$I$ und $J$ von $[\![ 1,n+1 ]\!]$ so dass $$\bigcup_{i\in I}X_i = \bigcup_{j\in J}X_j $$
Ich habe eine Lösung mit dem Hall-Theorem gefunden, aber ich habe sie vergessen. Kann mir jemand helfen ?
Ich brauche keine Lösung mit linearer Algebra. Ich nicht. Wenn mir jemand eine Lösung mit Kombinatorik anbieten könnte ...
Antworten
Betrachten Sie ein zweiteiliges Diagramm mit dem $X_i$ist auf einer Seite und $1,\ldots,n$auf der anderen Seite. Wenn$X_i$ enthält $k$, dann $X_i$ ist verbunden mit $k$. Der obige Satz ist nun äquivalent zu:
Für einen zweigeteilten Graphen $H$ mit Zweipartitionen $X$ und $Y$ so dass $|X| = n+1$ und $|Y| = n$ und Grad jedes Scheitelpunkts von $X$ ist größer als $0$gibt es zwei disjunkte Teilmengen von $X$ mit der gleichen Nachbarschaft gesetzt in $Y$.
Lassen Sie uns einführen $n$.
Basisfall :$n = 1$
Zum $n=1$, beide Eckpunkte in $X$ ist mit den einzelnen Eckpunkten in verbunden $Y$. Also beides$\{X_1\}$ und $\{X_2\}$habe die gleiche Nachbarschaft. Daher bewiesen
Definitionen:
Ein Scheitelpunkt $v$soll durch ein Matching gesättigt sein$M$ wenn $v$ hat eine Kante auf $M$.
Halls Theorem:
Lassen $G$ sei ein zweigliedriger Graph mit zweiteiliger Darstellung $(X,Y)$ , dann $G$ enthält eine Übereinstimmung, die jeden Scheitelpunkt in sättigt $X$ dann und nur dann, wenn $|N(S)| \geq |S|$ für alle $S \subseteq X$ (wo $N(S)$ ist die Nachbarschaft von $S$).
Induktiver Fall : Nehmen wir an, dass der obige Satz für alle ganzen Zahlen kleiner als gilt$n$ und lassen Sie uns versuchen, zu beweisen $n$.
Fall 1 :$H$ hat keine Übereinstimmung, die jeden Scheitelpunkt in sättigt $Y$.
Schon seit $H$ enthält keine Übereinstimmung, die gesättigt ist $Y$Nach dem Satz von Hall existiert ein$S$ so dass $S$ ist eine Teilmenge von $Y$ und $|N(S)| < |S|$. Betrachten Sie nun die Grafik$H'$ mit Zweipartitionen $X \setminus N(S)$ und $Y \setminus S$. Schon seit$|X \setminus N(S)| > |Y \setminus S|$durch Induktion, $H'$hat zwei Scheitelpunktmengen, die den Satz erfüllen. Wir können deutlich sehen, dass diese beiden Scheitelpunktmengen auch den Satz in erfüllen$H$ (Weil diese beiden Scheitelpunktsätze nach dem Hinzufügen keine zusätzlichen Kanten erhalten $N(S)$ und $S$). Daher bewiesen.
Fall 2 :$H$ hat eine passende $M$ das sättigt jeden Scheitelpunkt in $Y$.
$M$ muss gesättigt sein $n$ Eckpunkte in $X$. Lassen Sie den ungesättigten Scheitelpunkt herein$X$ Sein $u$. Betrachten Sie das Maximum$M$-Alternierender Baum verwurzelt bei $u$. Alle ungeraden Ebenen in diesem Baum haben Eckpunkte von$Y$ und alle geraden Ebenen im Baum haben Eckpunkte von $X$.
Alle Blätter dieses Baumes sind Eckpunkte von $X$. Beweisen wir dies durch Widerspruch. Lassen$v$ sei ein Scheitelpunkt in $Y$ das ist ein blatt in der $M$alternierender Baum. Jeder Scheitelpunkt in$Y$ wird durch eine Kante nicht erreicht $M$. Schon seit$Y$ ist gesättigt von $M$, $v$ hat eine Kante $e \in M$. Wir können jetzt nehmen$e$ und einen anderen Scheitelpunkt erreichen $w$ und verlängern Sie das Maximum $M$-Ändernder Baum durch Hinzufügen $e$. Daher Widerspruch. Daher$v$ist kein Blatt. Daher bewiesen.
Betrachten Sie die Mengen aller Eckpunkte in $4k$ und $4k+2$ Ebenen für $k \in \mathbb(W)$. $u$ gehört $0$th Ebene. Beide Sets haben die gleiche Nachbarschaft. Beweisen wir dies durch Widerspruch. Nehmen wir an, sie haben nicht die gleiche Nachbarschaft in$H$. Lass einen Scheitelpunkt$w$ in einem von $4k$ Ebenenscheitelpunkte werden mit einem Scheitelpunkt verbunden $v$ das ist mit keinem verbunden $4k+2$ebener Scheitelpunkt. Dann$v$ ist ein Blatt in der $M$alternierender Baum. Aber wir haben bewiesen, dass alle Blätter von$M$-Änderungsbaum sind in $X$. Aber$v \in Y$. Daher Widerspruch. Ebenso können wir das für den Scheitelpunkt beweisen$u$ im $4k+2$ Ebene mit einem Scheitelpunkt verbunden $v$ nicht verbunden mit a $4k$Level Vertex führt zu Widerspruch. Beide Scheitelpunktsätze haben also dieselbe Nachbarschaft.