Hallova věta

Matematická Hallova věta (1935) je připisována matematiku Philipu Hallovi. Věta se týká kombinatoriky a podává nutnou a postačující podmínku pro existenci systému různých reprezentantů ze systému podmnožin.

Nechť S = {S₁, S₂, … } je (ne nutně spočetná množina) 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| \ge |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:

(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| \ge |J|$ . To ale neplatí, protože $|\bigcup M_i| = |{a,b,c}|= 3$ a $| J | = 4$ .

Kategorie: Kombinatorika | Matematické věty a důkazy

Hallova věta v jiných jazycích: English, עברית, Magyar, Polski

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Hallova_v%C4%9Bta“
Stránka byla naposledy upravena v Stránka byla naposledy editována 21. 6. 2008 v 09:05.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).