A new intersection condition in extremal set theory

2025/04/19 by Nagy, Kartal
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2504.14389

Abstract

We call a family F (3,2,ℓ)-intersecting if |A ∩ B|+|B ∩ C|+|C ∩ A| ≥ ℓ for all A, B, C ∈ F. We try to look for the maximum size of such a family F in case when F ⊂ [n] \choose k or F ⊂ 2^[n]. In the uniform case we show that if F is (3,2,2)-intersecting, then \vert F \vert ≤ n+1 \choose k-1+n \choose k-2 and if F is (3,2,3)-intersecting, then |F| ≤ n \choose k-1 + 2 n \choose k-3 + 3 n-1 \choose k-3. For the lower bound we construct a (3,2,ℓ)-intersecting family and we show that this bound is sharp when ℓ=2 or 3 and n is sufficiently large compared to k. In the non-uniform case we give an upper bound for a (3,2,n-x)-intersecting family, when n is sufficiently large compared to x.

Related

• Two extremal problems on intersecting families
• Maximal 3-wise intersecting families
• Intersecting families of sets and permutations: a survey
• Extremal t-intersecting families for finite sets with t-covering number at least t+2
• Non-trivial 3-wise intersecting uniform families