Hall-tétel

A matematikában a Hall-tétel (1935, Philip Hall) egy kombinatorikai állítás, ami feltételt ad arra, hogy mikor lehet kiválasztani egy adott halmaz valahány nem feltétlenül diszjunkt részhalmazából különböző elemeket. Legyen S = {S₁, S₂, … } egy (nem feltétlenül megszámlálható) halmaza egy M halmaz véges részhalmazainak. A diszjunkt reprezentáns rendszer (innentől DRR) egy olyan X = {x₁, x₂, …} halmaza M-beli páronként diszjunkt elemeknek, melyekre |X| = |S|, és minden i-re x_i eleme S_i-nek teljesül. Az S halmaz teljesíti a Hall-feltételt, ha S minden T = {T_i } részhalmazára:

$|\bigcup T_i|\ge |T|$ (vagyis bármely n részhalmaz együtt legalább n elemből áll)

A Hall-tétel azt állítja, hogy akkor és csak akkor létezik diszjunkt reprezentáns rendszer X = {x_i}, ha S teljesíti a Hall-feltételt. Például: Legyen S₁ = {1, 2, 3}, S₂ = {1, 4, 5}, S₃ = {3, 5}. Erre az S = {S₁, S₂, S₃} halmazra, egy megfelelő DRR az {1, 4, 5} (Nem csak ez az egy DRR lehetséges: a {2, 1, 3} ugyanúgy jó lenne). A leggyakoribb példa a Hall-tétel alkalmazására, ha elképzelünk egy-egy n tagú férfiakból, illetve nőkből álló csoportot. Minden nő boldogan hozzámenne a férfiak egy bizonyos részhalmazához, és minden férfi boldogan elvenne bármely nőt, aki hozzá akarna menni. Gondoljuk meg, mikor lenne lehetséges úgy összeházasítani a férfiakat a nőkkel, hogy mindenki boldog legyen. Ha M_i lesz az a halmaza a férfiaknak, akikkel az i-edik nő boldogan összeházasodna, akkor a tétel állítása szerint akkor és csak akkor tudna minden nő boldogan férjhez menni, ha az {M_i} halmazok halmaza kielégíti a Hall-feltételt. A Hall-feltétel jelen esetben bármely $I$ részhalmazára a nőknek, azon férfiak száma, akik az $I$-beli nők közül legalább egyet elvennének ($|\bigcup _{i\in I}{T}_i|$) legyen legalább akkora, mint a nők ezen részhalmazának elemszáma, $|I|=|\{T_i:i\in I\}|$. Az természetes, hogy a feltétel szükséges, hiszen enélkül nem lenne elég az $I$-beli nők között szétosztható férfi. Annál érdekesebb, hogy a feltétel elégséges is. A tételnek vannak egyéb alkalmazásai is. Például vegyünk egy csomag francia kártyát, és osszuk szét őket 13 darab csoportba, minden csoportba 4-et téve. Ezek után a Hall-tételt használva láthatjuk, hogy lehetséges minden csoportból 1-1 kártyát úgy kiválasztani, hogy a 13 kiválasztott kártya közül minden kártyaértékből pontosan 1 szerepeljen (ász, 2, 3, …, dáma, király). Absztraktabb példaként legyen G egy csoport és H egy véges részcsoportja G-nek. Ekkor a tétel segítségével megmutathatjuk, hogy létezik olyan X halmaz, ami egyaránt DRR-je a H G-beli jobb és bal oldali mellékosztályainak. A tétel a megbízatási problémára is alkalmazható: Adott n alkalmazott halmaza, és mindhez egy lista, hogy kit mire lehet alkalmazni. Akkor és csak akkor tudunk mindenkinek a képességeihez megfelelő munkát adni, ha k (1…n) minden értékére bármely k db lista összesen legalább k db munkát tartalmaz. A még általánosabb problémára, melyben (nem feltétlenül különböző) elemeket kell kiválasztani halmazok egy halmazából, általában csak a csoportaxiómákat feltéve alkalmazhatjuk.

Bizonyítás

A Hall-tétel véges esetét fogjuk az |S|-re, azaz $S$ elemszámára vonatkozó indukcióval bizonyítani. A végtelen eset a kompaktsági tétel segítségével történik. A tétel triviálisan igaz az |S| = 0 esetben. Feltesszük, hogy a tétel minden |S| < n értékre igaz, ekkor |S| = n-re bizonyítunk. Először nézzük, mi van akkor, ha az alábbi $|\cup T|\ge \left|T\right|+1$ erősebb feltételt tesszük fel minden $\mathrm{\varnothing }\ne T\subset S$-re. Vegyük bármely $x\in S_n$ -et is $S_n$ reprezentánsának; a DRR-t $S^{\prime }=\{S_1\setminus \{x\},\dots ,S_{n-1}\setminus \{x\}\}$ -ből kell választanunk. De, ha $\{S_{j_1}\setminus \{x\},...,S_{j_k}\setminus \{x\}\}=T^{\prime }\subseteq S^{\prime }$ , akkor a feltevésünk szerint $|\cup T^{\prime }|\ge \left|\underset{i=1}{\overset{k}{\cup }}{S}_{j_i}\right|-1\ge k$. A tétel már bizonyított esetét $S^{\prime }$-re alkalmazva látható, hogy találhatunk megfelelő DRR-t $S^{\prime }$-höz. Egyébként bizonyos $\mathrm{\varnothing }\ne T\subset S$ értékekre az éles egyenlőség áll fent $|\cup T|=\left|T\right|$. $T$-n belül már bármely $T^{\prime }\subseteq T\subset S$-re beláttuk $|\cup T^{\prime }|\ge \left|T^{\prime }\right|$-t, így a tétel már bizonyított esete alapján választhatunk DRR-t $T$ számára. Az maradt hátra, hogy találjunk egy DRR-t $S\setminus T$-hez, ami nélkülözi $\cup T$ összes elemét (ezek az elemek $T$ SDR-ében vannak benne). Ahhoz, hogy (újfent) fel tudjuk használni a tétel már bizonyított esetét, meg kell mutatnunk, hogy bármely $T^{\prime }\subseteq S\setminus T$-re, $\cup T$ elemeinek figyelembe vétele nélkül is marad elég elem $\cup T^{\prime }$-ben: azaz $|\cup T^{\prime }\setminus \cup T|\ge \left|T^{\prime }\right|$-t kell belátnunk. De $|\cup T^{\prime }\setminus \cup T|$ $=|\bigcup (T\cup T^{\prime })|-|\cup T|\ge |T\cup T^{\prime }|-\left|T\right|$ $=\left|T\right|+\left|T^{\prime }\right|-\left|T\right|=\left|T^{\prime }\right|$, $T$ és $T^{\prime }$ diszjunktságát felhasználva. Így a tétel már bizonyított esetét felhasználva látható, hogy $S\setminus T$-hez tényleg létezik megfelelő DRR, amely $\cup T$ egyetlen elemét sem tartalmazza. Ezzel bebizonyítottuk a tételt.

Következmény

Ha $G(V_1,V_2,E)$ egy páros gráf, akkor $G$-ben akkor és csak akkor van $V_1$-et lefedő párosítás, ha $|S|\le |N(S)|$ minden $S\subset V_1$ részhalmazra.

Gráfelmélet

A Hall-tételnek főleg a gráfelméleten belül vannak alkalmazásai. Gráfelméleti problémaként így fogalmazhatjuk meg az alapkérdést: Adott egy páros gráf, G:= (S + T, E), két ugyanakkora méretű csúcshalmazzal, S-sel és T-vel, a kérdés pedig az, hogy létezik-e G-ben teljes párosítás. A Hall-tétel megadja a választ:

Példa egy páros gráfra, ahol a fenti ponthalmaz teljesíti a Hall-feltételt, így létezik őt lefedő párosítás.

Jelentse $N_G(X)$ a G-beli X csúcshalmaz szomszédainak számát. A Hall-tétel szerint akkor és csak akkor létezik teljes párosítás G-ben, ha S minden X részhalmazára

$\Vert X\Vert \le \Vert N_G(X)\Vert$

A tetszőleges gráfokra történő általánosítást a Tutte-tétel teszi lehetővé.

Egy még általánosabb állítás

Legyen G egy páros gráf, BIP^N(X,Y) úgy, hogy X és Y nem feltétlenül azonos méretűek. Ilyenkor G-ben akkor és csak akkor párosíthatók X összes csúcsai Y-beliekkel, ha az X csúcshalmaz kielégíti a Hall-feltételt. A korábbi jelöléseket használva a Hall-feltétel: minden A részhalmazára X-nek igaz, hogy |Г(A)| $\ge$ |A|.

Logikai ekvivalenciák

Ez a tétel tagja annak a 7 db különösen jelentős kombinatorikai tételnek, amelyek egyébként logikailag ekvivalensek. Ezek:

• Kőnig-tétel
• A Kőnig–Egerváry-tétel (1931) (Kőnig Dénes, Egerváry Jenő)
• Menger–tétel (1927)
• A Maximális folyam–minimális vágás-tétel (Ford-Fulkerson-algoritmus)
• A Birkhoff–Neumann-tétel (1946)
• Dilworth-tétel

Hivatkozások

• Equivalence of seven major theorems in combinatorics
• Katona, Recski, Szabó: A számítástudomány alapjai. Typotex. Budapest, 2006. p. 58,59.

További információk

• Marriage Theorem a cut-the-knot honlapról
• Marriage Theorem and Algorithm a cut-the-knot honlapról

Ez a szócikk a PlanetMath proof of Hall's marriage theorem cikkéből származó szövegen alapul. A PlanetMath GFDL licenc alatt terjeszthető.