{
  "id": "1905.02856",
  "version": "v1",
  "published": "2019-05-08T01:04:42.000Z",
  "updated": "2019-05-08T01:04:42.000Z",
  "title": "Max-Cut in Degenerate $H$-Free Graphs",
  "authors": [
    "Ray Li",
    "Nitya Mani"
  ],
  "comment": "Comments welcome",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We obtain several lower bounds on the $\\textsf{Max-Cut}$ of $d$-degenerate $H$-free graphs. Let $f(m,d,H)$ denote the smallest $\\textsf{Max-Cut}$ of an $H$-free $d$-degenerate graph on $m$ edges. We show that $f(m,d,K_r)\\ge \\left(\\frac{1}{2} + d^{-1+\\Omega(r^{-1})}\\right)m$, improving on and generalizing a recent work of Carlson, Kolla, and Trevisan. We also give bounds on $f(m,d,H)$ when $H$ is a cycle, odd wheel, or a complete bipartite graph with at most 4 vertices on one side. We also show stronger bounds on $f(m,d,K_r)$ assuming a conjecture of Alon, Bollabas, Krivelevich, and Sudakov (2003). We conjecture that $f(m,d,K_r)= \\left( \\frac{1}{2} + \\Theta_r(d^{-1/2}) \\right)m$ for every $r\\ge 3$, and show that this conjecture implies the ABKS conjecture.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-08T01:04:42.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35"
    ],
    "keywords": [
      "free graphs",
      "complete bipartite graph",
      "stronger bounds",
      "degenerate graph",
      "lower bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}