2006/08/07 by Noga Alon, Alon, Noga, Eyal Lubetzky +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.math/0608173
arxiv created 2006/08/07 · openalex publication_date 2006/08/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let A and \matchcalB denote two families of subsets of an n-element set. The pair (A,B) is said to be ℓ-cross-intersecting iff |A∩ B| = ℓ for all A\inA and B\inB. Denote by P_ℓ(n) the maximum value of |A||B| over all such pairs. The best known upper bound on P_ℓ(n) is Θ(2n), by Frankl and Rödl. For a lower bound, Ahlswede, Cai and Zhang showed, for all n ≥ 2ℓ, a simple construction of an ℓ-cross-intersecting pair (A,B) with |A||B| = \binom2ℓℓ2n-2ℓ=Θ(2n/√(ℓ)), and conjectured that this is best possible. Consequently, Sgall asked whether or not P_ℓ(n) decreases with ℓ. In this paper, we confirm the above conjecture of Ahlswede et al. for any sufficiently large ℓ, implying a positive answer to the above question of Sgall as well. By analyzing the linear spaces of the characteristic vectors of A,B over ℝ, we show that there exists some ℓ0>0, such that P_ℓ(n) ≤ \binom2ℓℓ2n-2ℓ for all ℓ ≥ ℓ0. Furthermore, we determine the precise structure of all the pairs of families which attain this maximum.