{
  "id": "1505.01265",
  "version": "v1",
  "published": "2015-05-06T07:31:50.000Z",
  "updated": "2015-05-06T07:31:50.000Z",
  "title": "A new property of the Lovász number and duality relations between graph parameters",
  "authors": [
    "Antonio Acín",
    "Runyao Duan",
    "Ana Belén Sainz",
    "Andreas Winter"
  ],
  "comment": "14 pages, submitted to Discrete Applied Mathematics for a special issue in memory of Levon Khachatrian",
  "categories": [
    "math.CO",
    "quant-ph"
  ],
  "abstract": "We show that for any graph $G$, by considering \"activation\" through the strong product with another graph $H$, the relation $\\alpha(G) \\leq \\vartheta(G)$ between the independence number and the Lov\\'{a}sz number of $G$ can be made arbitrarily tight: Precisely, the inequality \\[ \\alpha(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 \\[ \\alpha(G \\times H) \\leq \\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 Lov\\'{a}sz number $\\vartheta$ is self-dual. We also show results towards the duality of Schrijver's and Szegedy's variants $\\vartheta^-$ and $\\vartheta^+$ of the Lov\\'{a}sz number, and explore analogous notions for the chromatic number under strong and disjunctive graph products.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-05-06T07:31:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "graph parameters",
      "duality relations",
      "lovász number",
      "independence number",
      "right hand side"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150501265A"
    }
  }
}