Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 116.01104
Autor: Erdös, Pál
Title: On a combinatorial problem (In English)
Source: Nordisk Mat. Tidskr. 11, 5-10 (1963).
Review: p sei eine natürliche Zahl. Wir betrachten Familien F von p-elementigen Mengen A1,...,Ak. F besitzt die "Bernstein-Eigenschaft", wenn es eine Menge B gibt, die a) einerseits mit jedem Ai wenigstens ein gemeinsames Element hat, b) anderseits aber keins der Ai ganz umfaßt. Nimmt man hinreichend viele Mengen Ai über einem geeigneten Elementenbereich, so wird a) u.U. die Zugehörigkeit so vieler Elemente zu B nach sich ziehen, daß b) nicht mehr erfüllbar ist. So hat z.B. für p = 3 die aus 7 Mengen bestehende Familie {{1,2,3,}, {1,4,5}, {1,6,7}, {2,4,7}, {2,5,6}, {3,4,6}, {3,5,7}} die Bernstein-Eigenschaft nicht mehr, wohl aber jede Familie von 6 dreielementigen. m(p) sei die minimale Anzahl von p-elementigen Ai, die eine Familie bilden können, welche nicht mehr die Bernstein-Eigenschaft besitzt. Es ist m(1) = 1, m(2) = 3, m(3) = 7 (vgl. unser Beispiel). Weitere Werte sind nicht bekannt.
Der Verf. beweist die Abschätzung (1-\epsilon) 2P log 2 < m(p) \leq {2p-1 \choose p} für jedes \epsilon > 0 und für p > p0 (\epsilon), wobei die rechte Ungleichung sogar stets gilt. Beweislemma ist eine Bedingung, die für Familien, in denen die Ai sogar verschiedene Anzahlen \alphai haben dürfen, das Erfülltsein der Bernstein-Eigenschaft durch die Gültigkeit einer Formel zwischen den \alphai garantiert. Diese Bedingung wird für unendliche Familien verallgemeinert und auf eine verfeinerte Bernstein-Eigenschaft [welche wie das hier behandelte Problem erstmals in einer Arbeit von Erdös und A.Hajnal, Acta Math. Acad. Sci. Hung. 12, 87-123 (1961; Zbl.201.32801) auftritt] ausgedehnt.
Zusatz: Die behauptete Implikation ==> (3) gilt i.a. nicht, wie das Gegenbeispiel \alpha1 = \alpha2 = 2; \alpha3 = 4 zeigt. Dies beeinträchtigt aber die anderen Schlüsse nicht.
Reviewer: W.Oberschelp
Classif.: * 05A99 Classical combinatorial problems
Index Words: combinatorics
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag