A semidefinite programming approach to cross 2-intersecting families

2025/03/19 by Hajime Tanaka, Tanaka, Hajime, Norihide Tokushige +1 · 3 citations
Engineering · Mathematics · #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Packing Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2503.14844

openalex publication_date 2025/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let k≥ 2 and n≥ 3(k-1). Let F and G be families of k-element subsets of an n-element set. Suppose that |F∩ G|≥ 2 for all F\inF and G\inG. We show that |F||G|≤\binomn-2k-2², and determine the extremal configurations. This settles the last unsolved case of a recent result by Zhang and Wu (J. Combin. Theory Ser. B, 2025). We also obtain the corresponding result in the product measure setting. Our proof is done by solving semidefinite programming problems.

Cited by

• Tokushige's conjecture on measures of cross t-intersecting families
• The maximum product of sizes of cross-\(t\)-intersecting families
• Extremal cross t-intersecting families under t-covering number constraints for vector spaces

Related

• On cross-2-intersecting families
• Two extremal problems on intersecting families
• Disjoint Cross Intersecting Families
• On non-empty cross-intersecting families
• Sharp results concerning disjoint cross-intersecting families