×

zbMATH — the first resource for mathematics

A problem on independent \(r\)-tuples. (English) Zbl 0136.21302
Betrachtet werden die verallgemeinerten Graphen \(G^{(r)}\), deren Basiselemente Punkte und \(r\)-Tupel von Punkten sind \((r \geq 2)\). Eine Menge von \(r\)-Tupeln wird unabhängig genannt, wenn keine zwei von ihnen einen gemeinsamen Punkt haben. Der Verf. untersucht die Frage nach der kleinsten Zahl \(f(n,r,k)\), so daß jeder Graph \(G^{(r)}\) mit \(n\geq rk\) Punkten und \(f(n,r,k)\) \(r\)-Tupeln mindestens \(k\) unabhängige \(r\)-Tupel enthält. Die Gleichung \[ f(n,r,k) = 1+\max \left({rk-1 \choose r},g(n,r,k-1) \right) \] \([g(n,r,k-1)=\) Zahl \(r\)-Tupel aus \(n\) Punkten, die mindestens einen von \(k-1\) gegebenen Punkten enthalten], die für \(r = 2\) vom Verf. und T. Gallai (Zbl 0090.39401) und für \(k=2\) vom Verf., Chao Ko und R. Rado (Zbl 0100.01902) bereits früher bewiesen wurde, beweist der Verf. für hinreichend großes \(n\):
Theorem. Für \(n > c_rk\) (\(c_r\) eine Konstante, die nur von \(r\) abhängt) gilt \(f(n,r,k) = 1+g(n,r,k-1)\). Eine vollständige Lösung des Problems steht noch aus.
{Druckfehler: Rechte Seite von (8) richtig: \(1+g(n-1,r,k-2)\).}
Reviewer: W.Wessel (Berlin)

MSC:
05C35 Extremal problems in graph theory
Keywords:
topology
PDF BibTeX XML Cite