$L$-systems and the Lovász number

Abstract

Given integers $n>k>0$, and a set of integers $L\subset [0,k-1]$, an \emph{$L$-system} is a family of sets $\mathcal{F}\subset \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ such that $|F\cap F^{\prime }|\in L$ for distinct $F,F^{\prime }\in \mathcal{F}$. $L$-systems correspond to independent sets in a certain generalized Johnson graph $G(n,k,L)$, so that the maximum size of an $L$-system is equivalent to finding the independence number of the graph $G(n,k,L)$. The \emph{Lovász number} $\vartheta (G)$ is a semidefinite programming approximation of the independence number $\alpha$ of a graph $G$. In this paper, we determine the leading order term of $\vartheta (G(n,k,L))$ of any generalized Johnson graph with $k$ and $L$ fixed and $n\to \infty$. As an application of this theorem, we give an explicit construction of a graph $G$ on $n$ vertices with a large gap between the Lovász number and the Shannon capacity $c(G)$. Specifically, we prove that for any $\epsilon >0$, for infinitely many $n$ there is a generalized Johnson graph $G$ on $n$ vertices which has ratio $\vartheta (G)/c(G)=\Omega (n^{1-\epsilon })$, which improves on all known constructions. The graph $G$ \textit{a fortiori} also has ratio $\vartheta (G)/\alpha (G)=\Omega (n^{1-\epsilon })$, which greatly improves on the best known explicit construction.

21 pages; modified the statement of Theorem 1.6 and expanded the proof of Lemma 2.11; some minor revisions