Upper Bounds on the Order of Nearly Regular Induced Subgraphs in Random Graphs

Abstract

Finding the order of a largest induced regular subgraph in every graph on $n$ vertices was posed long ago by Erd\H{o}s, Fajtlowicz and Staton. Motivated by this problem and recent investigation in random graphs, we consider the order of nearly regular induced (bipartite) subgraphs in Erd\H{o}s-R\'enyi random graph $G(n,1/2)$ and random bipartite graph $G(n,m,1/2)$. Comparable upper bounds have been derived by using combinatorial and probabilistic techniques.