Hallova věta

Hallova věta je matematické tvrzení dokázané v roce 1935 anglickým matematikem Philipem Hallem. Týká se kombinatoriky a podává nutnou a postačující podmínku pro existenci systému různých reprezentantů ze systému podmnožin.

Znění

Nechť S = {S₁, S₂, … } je (ne nutně spočetná) množina konečných podmnožin množiny M.

Systém různých reprezentantů (někdy se zkracuje na SRR) je množina X = {x₁, x₂, …} různých prvků množiny M (kde |X| = |S|), přičemž pro každé i platí, že x_i je prvkem S_i.

Hallova podmínka pro množinu S je splněna, pokud pro každou její podmnožinu T platí, že

$|\bigcup T_{i}|\geq |T|$ (tj. libovolných n množin z množiny S má dohromady alespoň n prvků)

Hallova věta pak říká, že pro množinu S = {S₁, S₂, … } existuje SRR X = {x₁, x₂, … }, právě když S splňuje Hallovu podmínku.

Příklady

Triviální

(i) Je dán množinový systém $M=(M_{i}:i\in I)$. Mějme množiny I = {1,2,3,4}, M₁ = {a, b, d}, M₂ = {a, c}, M₃ = {b, c}, M₄ = {b, d}. Existuje SRR?

Odpověď: Ano, SRR existuje, například v M₁ vybereme b, v M₂ vybereme a, v M₃ vybereme c a v M₄ zvolíme d.

(ii) Je dán množinový systém $M=(M_{i}:i\in I)$. Mějme množiny I = {1,2,3,4}, M₁ = {a, c}, M₂ = {a, c}, M₃ = {b, c}, M₄ = {a, b}. Chceme rozhodnout, zda existuje SRR.

Řešení: SRR neexistuje, protože není splněna Hallova podmínka. Zvolíme-li totiž množinu J jako množinu indexů takovou, že J = {1,2,3,4}, pak by podle Hallovy věty mělo platit $|\bigcup M_{i}|\geq |J|$. To ale neplatí, protože $|\bigcup M_{i}|=|{a,b,c}|=3$ a $|J|=4$.

Sezdávací věta

Historická formulace tohoto problému (díky které se v anglofonním prostředí Hallově větě občas říká také „marriage theorem“ a Hallově podmínce „marriage condition“) zní tak, že máme n mužů a n žen, přičemž ke každé ženě i muži máme přiřazenu množinu potenciálních partnerů a máme za úkol zjistit, jestli můžeme přiřadit každé ženě jednoho různého muže, aby byla všechna takto vytvořená partnerství v definovaných skupinách.

Toto zadání se od hledání SRR poněkud liší v tom, že se v něm na problém díváme jakoby z obou stran. Při hledání SRR bychom chtěli uspokojit buď jen ženy s jejich požadavky na muže nebo muže s jejich požadavky na ženy. Problémy jsou však převoditelné.

Využití

Pomocí Hallovy věty lze dokázat, že

• v k-regulárním bipartitním grafu existuje k navzájem disjunktních perfektních párování.
• částečně (po celých řádcích) vyplněný latinský čtverec lze vždy doplnit na celý.

Důkaz věty

Důkaz se provádí matematickou indukcí a patří do základních hodin kombinatoriky na vysokých školách.