Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 136.21302
Autor: Erdös, Pál
Title: A problem on independent r-tuples (In English)
Source: Ann. Univ. Sci. Budapest. Rolando Eötvös, Sect. Math. 8, 93-96 (1965).
Review: 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 ({rk-1 \choose r},g(n,r,k-1) ) [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 090.39401) und für k = 2 vom Verf., Chao Ko und R. Rado (Zbl 100.01902) bereits früher bewiesen wurde, beweist der Verf. für hinreichend großes n:
Theorem. Für n > crk (cr 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)
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag