Full subgraphs

Let $G=(V,E)$ be a graph of density $p$ on $n$ vertices. Following Erdős, Łuczak and Spencer, an $m$-vertex subgraph $H$ of $G$ is called {\em full} if $H$ has minimum degree at least $p(m - 1)$. Let $f(G)$ denote the order of a largest full subgraph of $G$. If $p\binom{n}{2}$ is a non-negative integer, define $f(n,p) = \min\{f(G) : \vert V(G)\vert = n, \ \vert E(G)\vert = p\binom{n}{2} \}.$ Erdős, Łuczak and Spencer proved that for $n \geq 2$, $(2n)^{\frac{1}{2}} - 2 \leq f(n, {\frac{1}{2}}) \leq 4n^{\frac{2}{3}}(\log n)^{\frac{1}{3}}.$ In this paper, we prove the following lower bound: for $n^{-\frac{2}{3}} <p_n <1-n^{-\frac{1}{7}}$, $f(n,p) \geq \frac{1}{4}(1-p)^{\frac{2}{3}}n^{\frac{2}{3}} -1.$ Furthermore we show that this is tight up to a multiplicative constant factor for infinitely many $p$ near the elements of $\{\frac{1}{2},\frac{2}{3},\frac{3}{4},\dots\}$. In contrast, we show that for any $n$-vertex graph $G$, either $G$ or $G^c$ contains a full subgraph on $Ω(\frac{n}{\log n})$ vertices. Finally, we discuss full subgraphs of random and pseudo-random graphs, and several open problems.

No reviews yet.

No comments yet.