A new property of the Lovasz number and duality relations between graph parameters

We show that for any graph G, by considering "activation" through the strong product with another graph H, the relation alpha(G) <= upsilon(G) between the independence number and the Lovasz number of G can be made arbitrarily tight: Precisely, the inequality alpha(G boxed times H) <= upsilon(G boxed times H) = upsilon(G) upsilon(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 alpha(G boxed times H) <= alpha*(G)alpha(H), with the fractional packing number alpha*(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* are dual to each other, and the Lovasz number upsilon is self-dual. We also show duality of Schrijver's and Szegedy's variants upsilon(-) and upsilon(+) of the Lovasz number, and explore analogous notions for the chromatic number under strong and disjunctive graph products. (C) 2016 Elsevier B.V. All rights reserved.