Markström, Klas , Victor Falgas-Ravry & Jaques Verstraete | 2017
Journal of Graph theory 88, no 3, p.411-427.
Abstract
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.
