L-systems and the Lov\'asz number

Given integers $n > k > 0$, and a set of integers L ⊂ [0, k-1], an L-system is a family of sets F ⊂ [n]k such that |F ∩ F'| ∈ L for distinct F, F'∈ 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 Lov\'asz number ϑ(G) is a semidefinite programming approximation of the independence number of a graph G. In this paper, we determine the order of magnitude of ϑ(G(n, k, L)) of any generalized Johnson graph with k and L fixed and n→ ∞. As an application of this theorem, we give an explicit construction of a graph G on n vertices with large gap between the Lov\'asz number and the Shannon capacity $c(G)$. Specifically, we prove that for any ε > 0, for infinitely many n there is a generalized Johnson graph G on n vertices which has ratio ϑ(G)/c(G) = Ω(n1-ε), which greatly improves on the best known explicit construction.