Opuscula Math. 37, no. 4 (2017), 577-588
http://dx.doi.org/10.7494/OpMath.2017.37.4.577

Opuscula Mathematica

# A general 2-part Erdȍs-Ko-Rado theorem

Gyula O. H. Katona

Abstract. A two-part extension of the famous Erdȍs-Ko-Rado Theorem is proved. The underlying set is partitioned into $$X_1$$ and $$X_2$$. Some positive integers $$k_i$$, $$\ell_i$$ ($$1\leq i\leq m$$) are given. We prove that if $$\mathcal{F}$$) is an intersecting family containing members $$F$$ such that $$|F\cap X_1|=k_i$$, $$|F\cap X_2|=\ell_i$$ holds for one of the values $$i$$ ($$1\leq i\leq m$$) then $$|\mathcal{F}|$$ cannot exceed the size of the largest subfamily containing one element.

Keywords: extremal set theory, two-part problem, intersecting family.

Mathematics Subject Classification: 05D05.

Full text (pdf)

1. P. Erdős, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Q. J. Math. 12 (1961), 313-320.
2. P. Frankl, An Erdős-Ko-Rado Theorem for Direct Products, European J. Combin. 17 (1996), 727-730.
3. A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Q. J. Math. 18 (1967), 369-384.
4. G. Katona, On a conjecture of Erdős and a stronger form of Sperner's theorem, Studia Sci. Math. Hungar. 1 (1966), 59-63.
5. G.O.H. Katona, A simple proof of the Erdős-Chao Ko-Rado theorem, J. Combin. Theory Ser. B 13 (1972), 183-184.
6. D.J. Kleitman, On a lemma of Littlewood and Offord on the distribution of certain sums, Math. Z. 90 (1965), 251-259.
7. A. Mészáros, New bounds for 3-part Sperner theorems, Moscow J. Combin. Number Theory 5 (2015), 255-273.
8. A. Sali, Some intersection theorems, Combinatorica 12 (1992), 351-361.
9. E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27 (1928), 544-548.
10. J. Wang, H. Zhang, Intersecting families in $${[m]\choose l}\cup {[n]\choose k}$$, Discrete Math., to appear.
• Gyula O. H. Katona
• MTA Rényi Institute, Budapest Pf 127, 1364 Hungary
• Communicated by Ingo Schiermeyer.
• Revised: 2017-03-01.
• Accepted: 2017-03-03.
• Published online: 2017-04-28.