Erdős–Ko–Rado-tétel
Sablon:Nincs forrás Az Erdős–Ko–Rado-tétel a kombinatorika egyik fontos tétele, amely az ún. metszőrendszerekről szól. Erdős Pál, Ko Csao és Richard Rado 1938-ban találta, de csak 1961-ben publikálta.
A tétel állítása
Ha V egy n elemű halmaz, és k < n/2 egész, akkor a V feletti k-uniform metsző halmazrendszerre (azaz olyan halmazrendszerre, melyben ):
Egyenlőség felállhat, például, ha rögzített elemet beveszünk minden halmazába, majd a maradék k-1 elemet -ből választva valóban alkothatunk számosságú, a feltételeknek megfelelő halmazrendszert.
Bizonyítás[1]
A bizonyítás Katona Gyulától, 1972-ből származik[2]. A házigazda n-1 vendége egy körasztalnál foglal helyet a vacsorához. Az n fős csoportban vannak baráti társaságok, melyeknek mind-mind k tagja van, illetve bármely két társaságnak van közös tagja. Ezek a társaságok alkotják a csoport n számosságú halmaza felett a k-uniform metsző halmazrendszert.
A házigazda fix helyen ül, így összesen féleképpen ültethető le a csoport összes tagja. Bármely ilyen ültetésben egyes társaságok egymás mellé kerülnek, ívet alkotnak, míg mások nem. Először lássuk be, hogy legfeljebb k társaság alkothat ívet!
Az asztalon két szomszédos hely között 1-1 pohár van. Belátjuk, hogy minden pohárnál legfeljebb egy társaság íve kezdődhet, ugyanis ha egy irányba kezdődnének (pl. balra), akkor uniformitása miatt a két társaság megegyezne, ha pedig két irányba, balra és jobbra is kezdődne egy-egy társaság íve, akkor miatt a két társaságnak nem lenne közös tagja, amely ellentmond a feltételünknek.
Tehát, hogyha társaság ívet alkot, mivel mindegyik másik társasággal van közös tagja, ezért bármely másik ívet alkotó társaságnak k tagja közötti k-1 pohár valamelyikétől kell kezdődnie, így -n kívül valóban legfeljebb k-1 társaság alkothat ívet.
Ülésrend összesen van, így eddig társaságot számoltunk, azonban mindegyiket -szor, ugyanis ennyiféle ülésrendnél alkot ívet egy adott társaság. Tehát: