2023/05/09 by Agnijo Banerjee, Banerjee, Agnijo
Computer Science · Mathematics · #05D05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2305.05481
openalex publication_date 2023/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A family F ⊂ P(n) is r-wise k-intersecting if |A1 ∩ … ∩ Ar| ≥ k for any A1, …, Ar ∈ F. It is easily seen that if F is r-wise k-intersecting for r ≥ 2, k ≥ 1 then |F| ≤ 2n-1. The problem of determining the maximal size of a family F that is both r1-wise k1-intersecting and r2-wise k2-intersecting was raised in 2019 by Frankl and Kupavskii [1]. They proved the surprising result that, for (r1,k1) = (3,1) and (r2,k2) = (2,32) then this maximum is at most 2n-2, and conjectured the same holds if k2 is replaced by 3. In this paper we shall not only prove this conjecture but we shall also determine the exact maximum for (r1,k1) = (3,1) and (r2,k2) = (2,3) for all n.