Setlerin birliği hakkında soru
İzin Vermek $n >0$ ve $(X_i)_{i \in [\![ 1,n+1 ]\!]}$ boş olmayan alt kümeler olmak $[\![ 1,n ]\!]$. Boş olmayan iki ayrık alt küme olduğunu gösterin$I$ ve $J$ nın-nin $[\![ 1,n+1 ]\!]$ öyle ki $$\bigcup_{i\in I}X_i = \bigcup_{j\in J}X_j $$
Hall teoremini kullanarak bir çözüm buldum ama unuttum. Biri bana yardım edebilir mi?
Doğrusal cebir kullanarak çözüme ihtiyacım yok. Yapmıyorum. Birisi bana kombinatorik kullanarak bir çözüm sunabilirse ...
Yanıtlar
İle iki taraflı bir grafik düşünün $X_i$bir tarafta ve $1,\ldots,n$diğer tarafta. Eğer$X_i$ içerir $k$, sonra $X_i$ ile bağlantılı $k$. Yani yukarıdaki teorem artık şuna eşdeğerdir:
İkili bir grafik için $H$ iki bölümlü $X$ ve $Y$ öyle ki $|X| = n+1$ ve $|Y| = n$ ve her köşesinin derecesi $X$ daha büyüktür $0$, iki ayrık alt kümesi vardır $X$ aynı mahallede $Y$.
Başlayalım $n$.
Temel durum :$n = 1$
İçin $n=1$, içindeki her iki köşe $X$ içindeki tek köşelere bağlıdır $Y$. Yani ikisi de$\{X_1\}$ ve $\{X_2\}$aynı mahalleye sahip olmak. Dolayısıyla kanıtladı
Tanımlar:
Bir tepe $v$bir eşleşme ile doygun olduğu söylenir$M$ Eğer $v$ üzerinde bir uç olay var $M$.
Hall teoremi:
İzin Vermek $G$ iki bölümlü iki parçalı bir grafik olmak $(X,Y)$ , sonra $G$ içindeki her tepe noktasını doyuran bir eşleştirme içerir $X$ ancak ve ancak $|N(S)| \geq |S|$ hepsi için $S \subseteq X$ (nerede $N(S)$ mahalle $S$).
Endüktif durum : Yukarıdaki teoremin, şundan küçük tüm tamsayılar için doğru olduğunu varsayalım.$n$ ve kanıtlamaya çalışalım $n$.
Durum 1 :$H$ her köşeyi doyuran herhangi bir eşleşmeye sahip $Y$.
Dan beri $H$ doyuran herhangi bir eşleşme içermez $Y$Tarafından Hall'un teoremi , vardır bir$S$ öyle ki $S$ alt kümesidir $Y$ ve $|N(S)| < |S|$. Şimdi grafiği düşünün$H'$ iki bölümlü $X \setminus N(S)$ ve $Y \setminus S$. Dan beri$|X \setminus N(S)| > |Y \setminus S|$, tümevarım yoluyla, $H'$teoremi sağlayan iki köşe kümesine sahiptir. Bu iki köşe kümesinin de teoremi karşıladığını açıkça görebiliriz.$H$ (Çünkü bu iki köşe kümesi, biz geri ekledikten sonra fazladan $N(S)$ ve $S$). Dolayısıyla kanıtladı.
Durum 2 :$H$ eşleşmesi var $M$ her köşeyi doyuran $Y$.
$M$ doyurmalı $n$ köşeler $X$. Doymamış tepe noktasının içeri girmesine izin verin$X$ olmak $u$. Maksimum düşünün$M$köklü alternatif ağaç $u$. Bu ağaçtaki tüm garip seviyeler,$Y$ ve ağaçtaki tüm seviyelerin köşeleri $X$.
Bu ağacın tüm yaprakları $X$. Bunu çelişki ile kanıtlayalım. İzin Vermek$v$ tepe noktası olmak $Y$ bu bir yaprak $M$alternatif ağaç. Her köşe$Y$ içinde olmayan bir kenardan ulaşılır $M$. Dan beri$Y$ doymuş $M$, $v$ üstünlüğü var $e \in M$. Şimdi alabiliriz$e$ ve başka bir tepe noktasına ulaşın $w$ ve maksimumu uzatın $M$- alternatif ağaç ekleyerek $e$. Dolayısıyla çelişki. Bu nedenle$v$yaprak değil. Dolayısıyla kanıtladı.
İçindeki tüm köşe kümelerini düşünün $4k$ ve $4k+2$ seviyeleri $k \in \mathbb(W)$. $u$ ait olmak $0$inci seviye. Her iki set de aynı mahalleye sahip. Bunu çelişki ile kanıtlayalım. Aynı mahalleye sahip olmadıklarını varsayalım$H$. Bir tepe noktası olsun$w$ birinde $4k$ seviye köşeleri bir tepe noktasına bağlanabilir $v$ herhangi biriyle bağlantılı olmayan $4k+2$seviye tepe noktası. Sonra$v$ içinde bir yaprak $M$alternatif ağaç. Ama biz tüm yaprakların$M$alternatif ağaç var $X$. Fakat$v \in Y$. Dolayısıyla çelişki. Benzer şekilde vertex için bunu kanıtlayabiliriz$u$ içinde $4k+2$ bir tepe noktasına bağlı seviye $v$ ile bağlantılı değil $4k$seviye tepe çelişkiye yol açar. Yani her iki köşe kümesi aynı mahalleye sahip.