Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 315.05117
Autor: Erdös, Paul; Lovász, László
Title: Problems and results on 3-chromatic hypergraphs and some related questions. (In English)
Source: Infinite finite Sets, Colloq. Honour Paul Erdös, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 609-627 (1975).
Review: [For the entire collection see Zbl 293.00009.]
The authors investigate several extremal problems on set systems and state many unsolved problems. In this short review I can state only two of them. Denote by f(n) the smallest integer for which there is a family {Ak } of subsets, |Ak| = n, |Ak1 \cap Ak2| \leq 1; 1 \leq k \leq f(n) and which is three-chromatic, i.e. if \phi \cap Ak \ne Ø for every 1 \leq k \leq f(n). Then for some k \phi \supset Ak. We prove c14n/n4 < f(n) < c24nn4. (1) It would be desirable to have an asymptotic formula for f(n). Let g(n) be the smallest integer for which there is a family {Ak }, 1 \leq k \leq g(n), |Ak| = n, Ak1 \cap Ak \ne Ø so that for any |\phi| = n-1 there is an Ak with \phi \cap Ak = Ø. Is it true that g(n)/n ––> oo? We only get crude upper and lower bounds for g(n).
Classif.: * 05C35 Extremal problems (graph theory)
05C99 Graph theory
05C15 Chromatic theory of graphs and maps
00A07 Problem books
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag