A size-sensitive inequality for cross-intersecting families

2016/03/03 by Peter Frankl, Frankl, Peter, Andrey Kupavskii +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1603.00936

arxiv created 2017/01/15 · arxiv updated 2017/12/01

Abstract

Two families \mathcal A and \mathcal B of k-subsets of an n-set are called cross-intersecting if A∩ B≠∅ for all A∈ \mathcal A, B∈ \mathcal B . Strengthening the classical Erd\H os-Ko-Rado theorem, Pyber proved that |\mathcal A||\mathcal B|≤ n-1\choose k-1² holds for n≥ 2k. In the present paper we sharpen this inequality. We prove that assuming |\mathcal B|≥ n-1\choose k-1+n-i\choose k-i+1 for some 3≤ i≤ k+1 the stronger inequality |\mathcal A||\mathcal B|≤ (n-1\choose k-1+n-i\choose k-i+1)(n-1\choose k-1-n-i\choose k-1) holds. These inequalities are best possible.

Related

• Uniform s-cross-intersecting families
• Intersection theorems for \0,± 1\-vectors and s-cross-intersecting families
• The maximum product of sizes of cross-t-intersecting uniform families
• The maximum sum of sizes of cross-intersecting families of subsets of a set
• On a weaker notion of cross t-intersecting families