{
  "id": "1708.05454",
  "version": "v1",
  "published": "2017-08-17T22:43:55.000Z",
  "updated": "2017-08-17T22:43:55.000Z",
  "title": "On subgraphs of $C_{2k}$-free graphs and a problem of Kühn and Osthus",
  "authors": [
    "Dániel Grósz",
    "Abhishek Methuku",
    "Casey Tompkins"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $c$ denote the largest constant such that every $C_{6}$-free graph $G$ contains a bipartite and $C_4$-free subgraph having $c$ fraction of edges of $G$. Gy\\H{o}ri et al. showed that $\\frac{3}{8} \\le c \\le \\frac{2}{5}$. We prove that $c=\\frac{3}{8}$. More generally, we show that for any $\\varepsilon>0$, and any integer $k \\ge 2$, there is a $C_{2k}$-free graph $G_1$ which does not contain a bipartite subgraph of girth greater than $2k$ with more than $\\left(1-\\frac{1}{2^{2k-2}}\\right)\\frac{2}{2k-1}(1+\\varepsilon)$ fraction of the edges of $G_1$. There also exists a $C_{2k}$-free graph $G_2$ which does not contain a bipartite and $C_4$-free subgraph with more than $\\left(1-\\frac{1}{2^{k-1}}\\right)\\frac{1}{k-1}(1+\\varepsilon)$ fraction of the edges of $G_2$. One of our proofs uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erd\\H{o}s: For any $\\varepsilon>0$, and any integers $a$, $b$, $k \\ge 2$, there exists an $a$-uniform hypergraph $H$ of girth greater than $k$ which does not contain any $b$-colorable subhypergraph with more than $\\left(1-\\frac{1}{b^{a-1}}\\right)\\left(1+\\varepsilon\\right)$ fraction of the hyperedges of $H$. We also prove further generalizations of this theorem. In addition, we give a new and very short proof of a result of K\\\"uhn and Osthus, which states that every bipartite $C_{2k}$-free graph $G$ contains a $C_{4}$-free subgraph with at least $1/(k-1)$ fraction of the edges of $G$. We also answer a question of K\\\"uhn and Osthus about $C_{2k}$-free graphs obtained by pasting together $C_{2l}$'s (with $k>l\\ge3$).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-17T22:43:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graph",
      "free subgraph",
      "girth greater",
      "short proof",
      "bipartite subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}