Combinatorica Вычислительная математика

L-Systems and the Lovász Number

William Linz
Springer Nature · 2025-03-07 · DOI 10.1007/s00493-025-00136-4

Аннотация

Abstract Given integers $$n> k > 0$$ n > k > 0 , and a set of integers $$L \subset [0, k-1]$$ L ⊂ [ 0 , k - 1 ] , an L - system is a family of sets $$\mathcal {F}\subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) $$ F ⊂ [ n ] k such that $$|F \cap F'| \in L$$ | F ∩ F ′ | ∈ L for distinct $$F, F'\in \mathcal {F}$$ 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ász number $$\vartheta (G)$$ ϑ ( 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))$$ ϑ ( G ( n , k , L ) ) of any generalized Johnson graph with k and L fixed and $$n\rightarrow \infty $$ n → ∞ . 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$$ ϵ > 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 })$$ ϑ ( G ) / c ( G ) = Ω ( n 1 - ϵ ) , which improves on all known constructions. The graph G a fortiori also has ratio $$\vartheta (G)/\alpha (G) = \Omega (n^{1-\epsilon })$$ ϑ ( G ) / α ( G ) = Ω ( n 1 - ϵ ) , which greatly improves on the best known explicit construction.

Читать у издателя →