Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 209.28003
Autor: Erdös, Paul
Title: On a lemma of Hajnal-Folkman (In English)
Source: Combinat. Theory Appl., Colloquia Math. Soc. János Bolyai 4, 311-316 (1970).
Review: [For the entire collection see Zbl 205.00201.]
The symbol (m,n,i,r) ––> p means that if |S| = m \geq n, Aj \subset S, |Aj| \geq n is any family of subsets of S which cannot be represented by any i elements of S, then there is a subset S1 of S, |S1| = p, p \geq r, every r-tuple of which occurs in some Aj. (m,n,i,r) (not)––> p means that (m,n,i,r) ––> p does not hold. (2n-1,n,1,2) ––> n+1 is an old result of Hajnal and Folkman. The author proves (2n+i-2,n,i,2) ––> n+i and that this result is best possible. Several problems are posed, some of which have been settled since. Also a connection with Ramsey's theorem is established.
Classif.: * 05C55 Generalized Ramsey theory
Citations: Zbl 205.002(EA)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag