##
**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 **{**A_{k} **}** of subsets, |A_{k}| = n, |A_{k1} \cap A_{k2}| \leq 1; 1 \leq k \leq f(n) and which is three-chromatic, i.e. if \phi \cap A_{k} \ne Ø for every 1 \leq k \leq f(n). Then for some k \phi \supset A_{k}. We prove c_{1}4^{n}/n^{4} < f(n) < c_{2}4^{n}n^{4}. (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 **{**A_{k} **}**, 1 \leq k \leq g(n), |A_{k}| = n, A_{k1} \cap A_{k} \ne Ø so that for any |\phi| = n-1 there is an A_{k} with \phi \cap A_{k} = Ø. 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