Full subgraphs

Victor Falgas-Ravry, Klas Markström, Jacques Verstraëte

Published 2015-05-12Version 1

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.