Observations on Graph Invariants with the Lovász $\vartheta$-Function

Abstract

This paper delves into three research directions, leveraging the Lovász $\vartheta$-function of a graph. First, it focuses on the Shannon capacity of graphs, providing new results that determine the capacity for two infinite subclasses of strongly regular graphs, and extending prior results. The second part explores cospectral and nonisomorphic graphs, drawing on a work by Berman and Hamud (2024), and it derives related properties of two types of joins of graphs. For every even integer such that $n\ge 14$, it is constructively proven that there exist connected, irregular, cospectral, and nonisomorphic graphs on $n$ vertices, being jointly cospectral with respect to their adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrices, while also sharing identical independence, clique, and chromatic numbers, but being distinguished by their Lovász $\vartheta$-functions. The third part focuses on establishing bounds on graph invariants, particularly emphasizing strongly regular graphs and triangle-free graphs, and compares the tightness of these bounds to existing ones. The paper derives spectral upper and lower bounds on the vector and strict vector chromatic numbers of regular graphs, providing sufficient conditions for the attainability of these bounds. Exact closed-form expressions for the vector and strict vector chromatic numbers are derived for all strongly regular graphs and for all graphs that are vertex- and edge-transitive, demonstrating that these two types of chromatic numbers coincide for every such graph. This work resolves a query regarding the variant of the $\vartheta$-function by Schrijver and the identical function by McEliece et al. It shows, by a counterexample, that the $\vartheta$-function variant by Schrijver does not possess the property of the Lovász $\vartheta$-function of forming an upper bound on the Shannon capacity of a graph.

arXiv commentThis published research paper also serves as a tutorial of mutual interest in zero-error information theory and algebraic graph theory

References in corpus (23)

• Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function
• Lower bounds on the Probability of Error for Classical and Classical-Quantum Channels
• The Shannon capacity of a graph and the independence numbers of its powers
• A brief introduction to Spectral Graph Theory
• New lower bound on the Shannon capacity of C7 from circular graphs
• The asymptotic spectrum of graphs and the Shannon capacity
• The Lovasz number of random graphs
• High-rate storage codes on triangle-free graphs
• Sandwich theorems and capacity bounds for non-commutative graphs
• Observations on the Lovász $\theta$-Function, Graph Capacity, Eigenvalues, and Strong Products
• A Bound on the Shannon Capacity via a Linear Programming Variation
• A new property of the Lovász number and duality relations between graph parameters
• On the normalized Shannon capacity of a union
• New Eigenvalue Bound for the Fractional Chromatic Number
• Positive and Negative Square Energies of Graphs
• The Spectrum of Triangle-free Graphs
• Storage codes on coset graphs with asymptotically unit rate
• Sums of squares of eigenvalues and the vector chromatic number
• The BCH Family of Storage Codes on Triangle-Free Graphs is of Unit Rate
• Orthonormal representations, vector chromatic number, and extension complexity
• Symmetry and asymmetry between positive and negative square energies of graphs
• Shannon capacity, Lovász theta number and the Mycielski construction
• On the Ratio of Shannon Numbers of Graphs

Cited by in corpus (3)

• An example showing that Schrijver's $\vartheta$-function need not upper bound the Shannon capacity of a graph
• On Spectral Graph Determination
• On H-Intersecting Graph Families and Counting of Homomorphisms