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
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.
- P. Erdős, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Q. J. Math. 12 (1961), 313-320.
- P. Frankl, An Erdős-Ko-Rado Theorem for Direct Products, European J. Combin. 17 (1996), 727-730.
- A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Q. J. Math. 18 (1967), 369-384.
- G. Katona, On a conjecture of Erdős and a stronger form of Sperner's theorem, Studia Sci. Math. Hungar. 1 (1966), 59-63.
- G.O.H. Katona, A simple proof of the Erdős-Chao Ko-Rado theorem, J. Combin. Theory Ser. B 13 (1972), 183-184.
- D.J. Kleitman, On a lemma of Littlewood and Offord on the distribution of certain sums, Math. Z. 90 (1965), 251-259.
- A. Mészáros, New bounds for 3-part Sperner theorems, Moscow J. Combin. Number Theory 5 (2015), 255-273.
- A. Sali, Some intersection theorems, Combinatorica 12 (1992), 351-361.
- E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27 (1928), 544-548.
- 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.
- Received: 2016-12-31.
- Revised: 2017-03-01.
- Accepted: 2017-03-03.
- Published online: 2017-04-28.
