Erdős – Ko – Radova věta - Erdős–Ko–Rado theorem
v kombinatorika, Erdős – Ko – Radova věta z Paul Erdős, Chao Ko, a Richard Rado je věta o protínající se sady rodin.
Věta je následující. Předpokládejme to A je výrazná rodina podmnožiny z takže každá podskupina má velikost r a každá dvojice podmnožin má neprázdnost průsečík a předpokládejme to n ≥ 2r. Pak počet sad A je menší nebo rovno binomický koeficient
Výsledek je součástí teorie hypergrafy. Rodina sad může být také nazývána hypergrafem, a když všechny sady (které se v tomto kontextu nazývají „hyperedges“) mají stejnou velikost r, nazývá se to r-jednotný hypergraf. Věta tedy udává horní mez pro počet párových nedisjunktních hyper-hran v an r-jednotný hypergraf s n vrcholy a n ≥ 2r.
Věta může být také formulována z hlediska teorie grafů: číslo nezávislosti z Kneserův graf KGn,r pro n ≥ 2r je
Podle Erdős (1987) věta byla prokázána v roce 1938, ale byla publikována až v roce 1961 ve zjevně obecnější podobě. U příslušných podmnožin se vyžadovala pouze velikost nejvíce r, a s dalším požadavkem, aby žádná podmnožina nebyla obsažena v žádném jiném.
Platí také verze věty podepsané sady (Bollobás & Leader 1997 )
Důkaz
Byl použit původní doklad z roku 1961 indukce na n. V roce 1972 Gyula O. H. Katona poskytl následující krátký důkaz pomocí dvojité počítání.
Předpokládejme, že máme nějakou takovou rodinu podmnožin A. Uspořádejte prvky {1, 2, ...,n} v každém cyklický řád a vezměte v úvahu sady z A které tvoří intervaly délky r v tomto cyklickém pořadí. Například pokud n = 8 a r = 3, můžeme uspořádat čísla {1, 2, ..., 8} do cyklického pořadí (3,1,5,4,2,7,6,8), které má osm intervalů:
- (3,1,5), (1,5,4), (5,4,2), (4,2,7), (2,7,6), (7,6,8), (6 , 8,3) a (8,3,1).
Není však možné, aby patřily všechny intervaly cyklického pořadí A, protože některé páry z nich jsou disjunktní. Klíčovým postřehem Katony je to nanejvýš r intervalů pro jeden cyklický řád může patřit A. Chcete-li to vidět, nezapomeňte, že pokud (A1, A2, ..., Ar) je jedním z těchto intervalů v A, pak každý další interval stejného cyklického řádu, který patří A odděluje Ai a Ai+1 pro některé i (to znamená, že obsahuje přesně jeden z těchto dvou prvků). Dva intervaly, které oddělují tyto prvky, jsou disjunktní, takže nanejvýš jeden z nich může patřit A. Tedy počet intervalů v A je jedna plus počet oddělených párů, což je maximálně (r - 1).
Na základě této myšlenky můžeme spočítat počet párů (S,C), kde S je soubor v A a C je cyklický řád, pro který S je interval dvěma způsoby. Nejprve pro každou sadu S jeden může generovat C výběrem jednoho z r! obměny S a (n − r)! permutace zbývajících prvků, což ukazuje, že počet párů je |A|r!(n − r) !. A za druhé, existují (n - 1)! cyklické objednávky, z nichž každý má maximálně r intervaly A, takže počet párů je maximálně r (n - 1) !. Kombinace těchto dvou počtů dává nerovnost
a vydělením obou stran r!(n − r)! dává výsledek

Rodiny maximální velikosti
Pro protínající se rodinu existují dvě různé a přímé konstrukce r-prvkové sady dosahující Erdős – Ko – Rado vázané na mohutnost. Nejprve vyberte libovolný pevný prvek Xa nechte A skládat se ze všech r- podmnožiny které zahrnují X. Například pokud n = 4, r = 2 a X = 1, vznikne rodina tří 2 sad
- {1,2}, {1,3}, {1,4}.
Jakékoli dvě sady v této rodině se protínají, protože obě obsahují X.Druhé, kdy n = 2r a s X jak je uvedeno výše, nechť A skládat se ze všech r- podmnožiny které nezahrnují XU stejných parametrů jako výše to vytváří rodinu
- {2,3}, {2,4}, {3,4}.
Jakékoli dvě sady v této rodině mají celkem 2r = n prvky mezi nimi, vybrané z n - 1 prvek, který je nerovný X, tak podle princip pigeonhole musí mít společný prvek.
Když n > 2r, rodiny prvního typu (různě známé jako slunečnice, hvězdy, diktatury, soustředěné rodiny, hlavní rodiny) jsou jedinečné maximální rodiny. Friedgut (2008) dokázal, že v tomto případě má rodina téměř maximální velikosti prvek, který je společný téměř pro všechny její sady. Tato vlastnost je známá jako stabilita.

Maximální protínající se rodiny
Protínající se rodina r-prvkové sady mohou být maximální v tom, že nelze přidat žádnou další sadu bez zničení vlastnosti průniku, ale ne maximální velikosti. Příklad s n = 7 a r = 3 je sada 7 řádků Fano letadlo, mnohem méně než Erdős – Ko – Rado na hranici 15.
Protínající se rodiny podprostorů
Tady je q-analog věty Erdős – Ko – Rado pro protínající se rodiny podprostorů konečná pole. Frankl & Wilson (1986)
Li je protínající se rodina -rozměrné podprostory an -dimenzionální vektorový prostor přes konečné pole řádu , a , pak
Vztah ke grafům v asociačních schématech
Věta Erdős – Ko – Rado dává vazbu na maximální velikost an nezávislá sada v Kneserovy grafy obsaženo v Johnsonovy schémata.[Citace je zapotřebí ]
Podobně analogie Erdős – Ko – Radovy věty pro protínající se rodiny podprostorů nad konečnými poli dává vazbu na maximální velikost nezávislé množiny v q-Kneserovy grafy obsaženo v Grassmannova schémata.[Citace je zapotřebí ]
Reference
- Bollobás, B.; Vedoucí, I. (1997), „Erdős-Ko-Radova věta pro podepsané množiny“, Počítače a matematika s aplikacemi, 34 (11): 9–13, doi:10.1016 / S0898-1221 (97) 00215-0, PAN 1486880
- Erdős, P. (1987), „My joint work with Richard Rado“, in Whitehead, C. (ed.), Surveys in combineatorics, 1987: Invited Papers for the Eleventh British Combinatorial Conference (PDF), Série přednášek London Mathematical Society, 123, Cambridge University Press, s. 53–80, ISBN 978-0-521-34805-8.
- Erdős, P.; Ko, C.; Rado, R. (1961), "Věty o křižovatce pro systémy konečných množin" (PDF), Quarterly Journal of Mathematics. Oxford. Druhá série, 12: 313–320, doi:10.1093 / qmath / 12.1.313.
- Frankl, P .; Wilson, R. M. (1986), „The Erdős-Ko-Rado theorem for vector spaces“, Journal of Combinatorial Theory, Series A, 43: 228–236, doi:10.1016/0097-3165(86)90063-4.
- Friedgut, Ehud (2008), „Na míru protínajících se rodin, jedinečnosti a stability“ (PDF), Combinatorica, 28 (5): 503–528, doi:10.1007 / s00493-008-2318-9
- Katona, G. O. H. (1972), „Jednoduchý důkaz věty Erdös-Chao Ko-Rado“, Journal of Combinatorial Theory, Series B, 13 (2): 183–184, doi:10.1016/0095-8956(72)90054-8.
- Godsil, Christopher; Karen, Meagher (2015), Věty Erdős – Ko – Rado: Algebraické přístupy, Cambridge Studies in Advanced Mathematics, Cambridge University Press, ISBN 9781107128446.