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

|\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 = {S1, S2, … } existuje SRR X = {x1, x2, … } právě když S splňuje Hallovu podmínku.

V jiných jazycích