A cross-intersection theorem for vector spaces based on semidefinite programming

2013/04/19 by Sho Suda, Hajime Tanaka · 1 citation
Mathematics · #math.CO #msc:05D05 #msc:90C22 #msc:90C27 #msc:05C50

paper · pdf · doi:10.1112/blms/bdt101

published as Bull. Lond. Math. Soc. 46 (2014) 342-348 · 7 pages

arxiv created 2013/04/19 · arxiv updated 2014/03/27

Abstract

Let \mathscrF and \mathscrG be families of k- and ℓ-dimensional subspaces, respectively, of a given n-dimensional vector space over a finite field \mathbbF_q. Suppose that x ∩ y ≠ 0 for all x ∈ \mathscrF and y ∈ \mathscrG. By explicitly constructing optimal feasible solutions to a semidefinite programming problem which is akin to Lovász's theta function, we show that |\mathscrF| |\mathscrG| ≤ n-1 \brack k-1 n-1 \brack ℓ-1, provided that n ≥ 2k and n ≥ 2ℓ. The characterization of the extremal families is also established.

Cited by

• P-polynomial coherent configurations

Related

• r-cross t-intersecting families for vector spaces
• More on r-cross t-intersecting families for vector spaces
• A semidefinite programming approach to cross 2-intersecting families
• Non-trivial t-intersecting families for vector spaces
• Simplices in t-intersecting families for vector spaces