{
  "id": "1505.03072",
  "version": "v1",
  "published": "2015-05-12T15:58:41.000Z",
  "updated": "2015-05-12T15:58:41.000Z",
  "title": "Full subgraphs",
  "authors": [
    "Victor Falgas-Ravry",
    "Klas Markström",
    "Jacques Verstraëte"
  ],
  "comment": "16 pages; a first version of this paper appeared in the Mittag--Leffler Institute's preprint series",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be an $n$-vertex graph with edge-density $p$. Following Erd\\H{o}s, \\L uczak and Spencer, an $m$-vertex subgraph H of G is called full if it has minimum degree at least $p(m - 1)$. Let $f(G)$ denote the order of a largest full subgraph of $G$, and let $f_p(n)$ denote the minimum of $f(G)$ over all $n$-vertex graphs $G$ with edge-density $p$. In this paper we show that for $p$: $n^{-2/3} <p< 1-n^{-1/5}$, the function $f_p(n)$ is of order at least $(1-p)^{1/3} n^{2/3}$, improving on an earlier lower bound of Erd\\H{o}s, \\L uczak and Spencer in the case $p=1/2$. Moreover we show that this bound is tight: for infinitely many $p$ near the elements of $\\{\\frac{1}{2}, \\frac{2}{3}, \\frac{3}{4}, \\ldots \\}$ we have $f_p(n)= \\Theta (n^{2/3})$ As an ingredient of the proof, we show that every graph $G$ on $n$ vertices has a subgraph $H$ on $m$ vertices with $\\frac{n}{r}-1< m <\\frac{n}{r}+2$ such that for every every vertex $v$ in $V(H)$ the degree of $v$ in $H$ is at least $\\frac{1}{r}$ times its degree in $G$. Finally, we discuss full subgraphs of random and pseudorandom graphs, and introduce several open problems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-05-12T15:58:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C70",
      "05D10",
      "G.2.2"
    ],
    "keywords": [
      "vertex graph",
      "largest full subgraph",
      "earlier lower bound",
      "minimum degree",
      "edge-density"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150503072F"
    }
  }
}