{
  "id": "1904.05307",
  "version": "v1",
  "published": "2019-04-10T17:17:20.000Z",
  "updated": "2019-04-10T17:17:20.000Z",
  "title": "On the sizes of large subgraphs of the binomial random graph",
  "authors": [
    "Jozsef Balogh",
    "Maksim Zhukovskii"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In the paper, we answer the following two questions. Given $e(k)=p{k\\choose 2}+O(k)$, what is the maximum $k$ such that $G(n,p)$ has an induced subgraph with $k$ vertices and $e(k)$ edges? Given $k>\\varepsilon n$, what is the maximum $\\mu$ such that a.a.s.~the set of sizes of $k$-vertex subgraphs of $G(n,p)$ contains a full interval of length $\\mu$? We prove that the value $\\mathcal{X}_n$ from the first question is not concentrated in any finite set (in contrast to the case of a small $e=e(k)$). Moreover, we prove that for an $\\omega_n\\to\\infty$, a.a.s.~the size of the concentration set is smaller than $\\omega_n\\sqrt{n/\\ln n}$. Otherwise, for an arbitrary constant $C>0$, a.a.s.~it is bigger than $C\\sqrt{n/\\ln n}$. Our answer on the second question is the following: $\\mu=\\Theta(\\sqrt{(n-k)n\\ln{n\\choose k}})$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-04-10T17:17:20.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "binomial random graph",
      "large subgraphs",
      "second question",
      "arbitrary constant",
      "vertex subgraphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}