A new property of the Lovász number and duality relations between graph parameters

Abstract

We show that for any graph $G$, by considering "activation" through the strong product with another graph $H$, the relation $\alpha (G)\le \vartheta (G)$ between the independence number and the Lovász number of $G$ can be made arbitrarily tight: Precisely, the inequality \[ α(G \times H) \leq \vartheta(G \times H) = \vartheta(G)\,\vartheta(H) \] becomes asymptotically an equality for a suitable sequence of ancillary graphs $H$. This motivates us to look for other products of graph parameters of $G$ and $H$ on the right hand side of the above relation. For instance, a result of Rosenfeld and Hales states that \[ α(G \times H) \leq α^*(G)\,α(H), \] with the fractional packing number ${\alpha }^{\ast }(G)$, and for every $G$ there exists $H$ that makes the above an equality; conversely, for every graph $H$ there is a $G$ that attains equality. These findings constitute some sort of duality of graph parameters, mediated through the independence number, under which $\alpha$ and ${\alpha }^{\ast }$ are dual to each other, and the Lovász number $\vartheta$ is self-dual. We also show duality of Schrijver's and Szegedy's variants ${\vartheta }^{-}$ and ${\vartheta }^{+}$ of the Lovász number, and explore analogous notions for the chromatic number under strong and disjunctive graph products.

16 pages, submitted to Discrete Applied Mathematics for a special issue in memory of Levon Khachatrian; v2 has a full proof of the duality between theta+ and theta- and a new author, some new references, and we corrected several small errors and typos

References in corpus (2)

• Potential capacities of quantum channels
• On zero-error communication via quantum channels in the presence of noiseless feedback

Cited by in corpus (6)

• On converse bounds for classical communication over quantum channels
• Observations on the Lovász $\theta$-Function, Graph Capacity, Eigenvalues, and Strong Products
• Observations on Graph Invariants with the Lovász $\vartheta$-Function
• Uncertainty relations from state polynomial optimization
• Exploring the boundary of quantum correlations with a time-domain optical processor
• Duality of Graph Invariants