{
  "id": "2006.14466",
  "version": "v1",
  "published": "2020-06-25T15:00:47.000Z",
  "updated": "2020-06-25T15:00:47.000Z",
  "title": "Splits with forbidden subgraphs",
  "authors": [
    "Maria Axenovich",
    "Ryan R. Martin"
  ],
  "comment": "12 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this note, we fix a graph $H$ and ask into how many vertices can each vertex of a clique of size $n$ can be \"split\" such that the resulting graph is $H$-free. Formally: A graph is an $(n,k)$-graph if its vertex sets is a pairwise disjoint union of $n$ parts of size at most $k$ each such that there is an edge between any two distinct parts. Let $$ f(n,H) = \\min \\{k \\in \\mathbb N : \\mbox{there is an $(n,k)$-graph $G$ such that $H\\not\\subseteq G$}\\} . $$ Barbanera and Ueckerdt observed that $f(n, H)=2$ for any graph $H$ that is not bipartite. If a graph $H$ is bipartite and has a well-defined Tur\\'an exponent, i.e., ${\\rm ex}(n, H) = \\Theta(n^r)$ for some $r$, we show that $\\Omega (n^{2/r -1}) = f(n, H) = O (n^{2/r-1} \\log ^{1/r} n)$. We extend this result to all bipartite graphs for which an upper and a lower Tur\\'an exponents do not differ by much. In addition, we prove that $f(n, K_{2,t}) =\\Theta(n^{1/3})$ for any fixed $t$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-25T15:00:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05D40"
    ],
    "keywords": [
      "forbidden subgraphs",
      "lower turan exponents",
      "vertex sets",
      "pairwise disjoint union",
      "well-defined turan exponent"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}