Hallova věta
Z Wikipedie, otevřené encyklopedie
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 = {S1, S2, … } 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 = {x1, x2, …} různých prvků množiny M (kde |X| = |S|), přičemž pro každé i platí, že xi je prvkem Si.
Hallova podmínka pro množinu S je splněna pokud pro každou její podmnožinu T platí, že
(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 = {S1, S2, … } existuje SRR X = {x1, x2, … } právě když S splňuje Hallovu podmínku.
