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

Abstract

Let $\mathcal{F}$ and $\mathcal{G}$ be families of $k$- and $\ell$-dimensional subspaces, respectively, of a given $n$-dimensional vector space over a finite field ${\mathbb{F}}_q$. Suppose that $x\cap y\ne 0$ for all $x\in \mathcal{F}$ and $y\in \mathcal{G}$. By explicitly constructing optimal feasible solutions to a semidefinite programming problem which is akin to Lovász's theta function, we show that $|\mathcal{F}||\mathcal{G}|\le \left[\genfrac{}{}{0ex}{}{n-1}{k-1}\right]\left[\genfrac{}{}{0ex}{}{n-1}{\ell -1}\right]$, provided that $n\ge 2k$ and $n\ge 2\ell$. The characterization of the extremal families is also established.

7 pages

Cited by in corpus (3)

• A cross-intersection theorem for subsets of a set
• A semidefinite programming approach to a cross-intersection problem with measures
• Extremal problems for intersecting families of subspaces with a measure