{
  "id": "2106.16203",
  "version": "v1",
  "published": "2021-06-30T16:56:08.000Z",
  "updated": "2021-06-30T16:56:08.000Z",
  "title": "The feasible region of induced graphs",
  "authors": [
    "Xizhi Liu",
    "Dhruv Mubayi",
    "Christian Reiher"
  ],
  "comment": "27 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The feasible region $\\Omega_{{\\rm ind}}(F)$ of a graph $F$ is the collection of points $(x,y)$ in the unit square such that there exists a sequence of graphs whose edge densities approach $x$ and whose induced $F$-densities approach $y$. A complete description of $\\Omega_{{\\rm ind}}(F)$ is not known for any $F$ with at least four vertices that is not a clique or an independent set. The feasible region provides a lot of combinatorial information about $F$. For example, the supremum of $y$ over all $(x,y)\\in \\Omega_{{\\rm ind}}(F)$ is the inducibility of $F$ and $\\Omega_{{\\rm ind}}(K_r)$ yields the Kruskal-Katona and clique density theorems. We begin a systematic study of $\\Omega_{{\\rm ind}}(F)$ by proving some general statements about the shape of $\\Omega_{{\\rm ind}}(F)$ and giving results for some specific graphs $F$. Many of our theorems apply to the more general setting of quantum graphs. For example, we prove a bound for quantum graphs that generalizes an old result of Bollob\\'as for the number of cliques in a graph with given edge density. We also consider the problems of determining $\\Omega_{{\\rm ind}}(F)$ when $F=K_r^-$, $F$ is a star, or $F$ is a complete bipartite graph. In the case of $K_r^-$ our results sharpen those predicted by the edge-statistics conjecture of Alon et. al. while also extending a theorem of Hirst for $K_4^-$ that was proved using computer aided techniques and flag algebras. The case of the 4-cycle seems particularly interesting and we conjecture that $\\Omega_{{\\rm ind}}(C_4)$ is determined by the solution to the triangle density problem, which has been solved by Razborov.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-06-30T16:56:08.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "feasible region",
      "induced graphs",
      "quantum graphs",
      "edge density",
      "clique density theorems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 27,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}