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 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 n 2is a nonnegative integer, definef ( n , p ) = min { f ( G ) : | V ( G ) | = n , | E ( G ) | = p n 2 } .Erdős, Łuczak, and Spencer proved that for n ≥ 2 ,( 2 n ) 1 2 − 2 ≤ f ( n , 1 2 ) ≤ 4 n 2 3( log n )1 3. In this article, we prove the following lower bound: forn − 2 3< p n < 1 − n − 1 7,f ( n , p ) ≥ 1 4( 1 − p )2 3n 2 3− 1 . Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of { 1 2 , 2 3 , 3 4 , ⋯ } . In contrast, we show that for any n ‐vertex graph G , either G or G c contains a full subgraph on Ω ( n log n ) vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems.