Markström, Klas , Victor Falgas-Ravry & Jaques Verstraete | 2017
Journal of Graph theory 88, no 3, p.411-427.
Let be a graph of density p on n vertices. Following Erdős, Łuczak, and Spencer, an m‐vertex subgraph H of G is called full if H has minimum degree at least . Let denote the order of a largest full subgraph of G. If is a nonnegative integer, define
Erdős, Łuczak, and Spencer proved that for ,
In this article, we prove the following lower bound: for ,
Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of . In contrast, we show that for any n‐vertex graph G, either G or contains a full subgraph on vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems.