A semidefinite programming approach to cross $2$-intersecting families
Preprint
Abstract
Let $k\geq 2$ and $n\geq 3(k-1)$. Let $\mathcal{F}$ and $\mathcal{G}$ be families of $k$-element subsets of an $n$-element set. Suppose that $|F\cap G|\geq 2$ for all $F\in\mathcal{F}$ and $G\in\mathcal{G}$. We show that $|\mathcal{F}||\mathcal{G}|\leq\binom{n-2}{k-2}^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.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Extremal problems for intersecting families of subspaces with a measureEuropean Journal of Combinatorics, 2025
- AK-type stability theorems on cross -intersecting familiesEuropean Journal of Combinatorics, 2019
- A semidefinite programming approach to a cross-intersection problem with measuresMathematical Programming, 2017
- Towards extending the Ahlswede–Khachatrian theorem to cross -intersecting familiesDiscrete Applied Mathematics, 2017
- The eigenvalue method for cross t-intersecting familiesJournal of Algebraic Combinatorics, 2013
- On the measure of intersecting families, uniqueness and stabilityCombinatorica, 2008
- The Terwilliger Algebra of the HypercubeEuropean Journal of Combinatorics, 2002
- A Pushing-Pulling Method: New Proofs of Intersection TheoremsCombinatorica, 1999
- The Diametric Theorem in Hamming Spaces—Optimal AnticodesAdvances in Applied Mathematics, 1998
- The Complete Intersection Theorem for Systems of Finite SetsEuropean Journal of Combinatorics, 1997