Diversity of uniform intersecting families

2017/09/08 by Kupavskii, Andrey · 3 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1709.02829

Abstract

A family \mathcal F⊂ 2^[n] is called intersecting if any two of its sets intersect. Given an intersecting family, its diversity is the number of sets not passing through the most popular element of the ground set. Peter Frankl made the following conjecture: for n> 3k>0 any intersecting family \mathcal F⊂ [n]\choose k has diversity at most n-3\choose k-2. This is tight for the following "two out of three" family: \F∈ [n]\choose k: |F∩ [3]|≥ 2\. In this note, we prove this conjecture for n≥ ck, where c is a constant independent of n and k. In the last section, we discuss the case 2k

Cited by

• Two results on set families: sturdiness and intersection
• The overflow in the Katona Theorem
• Intersecting families of sets are usually trivial for n≥ 2k+3

Related

• Diversity
• Improved bounds on the maximum diversity of intersecting families
• A generalization of diversity for intersecting families
• Intersecting families with full difference sets
• Intersecting non-uniform families containing subfamilies