×

zbMATH — the first resource for mathematics

The shifting technique in extremal set theory. (English) Zbl 0633.05038
Surveys in combinatorics 1987, Pap. 11th Br. Combin. Conf., London/Engl. 1987, Lond. Math. Soc. Lect. Note Ser. 123, 81-110 (1987).
[For the entire collection see Zbl 0611.00003.]
In this survey paper several classical and new results in extremal set theory are presented, with proof. The simple, but powerful technique of shifting is introduced and applied to prove the Erdős-Ko-Rado theorem, the Kruskal-Katona theorem, a Katona theorem on the size of the shadow of a t-intersecting family, another on t-intersecting families, the Hilton- Milner theorem on the second extremal family in the Erdős-Ko-Rado theorem. The asymptotic behavior of the maximum size of r-wise t- intersecting families is studied. Numerical calculations are given for the case \(r=3\), \(t\leq 6\). A result is presented in connection with a conjecture of Erdős on the cardinality of a system containing no s pairwise disjoint members. A bound is given to families where the intersection of r members is always non-empty. Finally, the Brace-Daykin theorem is proved. Along the theorems (in every case at least the proof is given by the author) the most important open problems are presented.
Reviewer: P.Komjáth

MSC:
05C35 Extremal problems in graph theory
05C65 Hypergraphs
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics