Regular induced subgraphs of a random Graph
An old problem of Erd?s, Fajtlowicz, and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on vertices, i.e., in a binomial random graph . We prove that with high probability a largest induced regular subgraph of has about vertices.  2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 235250, 2011
regular induced subgraph random graph extremal graph theory random regular graphs