Feladat: A.504 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 2010/március, 160. oldal  PDF  |  MathML 
Témakör(ök): Nehéz feladat, Gráfelmélet

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Bizonyítsuk be, hogy tetszőleges 0<r<k<t egészekhez létezik egy N(r,k,t) pozitív egész a következő tulajdonsággal: ha a G  r-uniform hipergráfnak legalább N(r,k,t) pontja van, és bármely k pontja között van legalább egy él, akkor G tartalmaz teljes t-pontú részhipergráfot. (A hipergráf olyan gráf, amelyben az élek nem csak kettő, hanem tetszőleges számú pontot kötnek össze. A hipergráf akkor r-uniform, ha minden éléhez pontosan r pont tartozik. Egy r-uniform hipergráf teljes, ha bármely r pontját él köti össze.)