WorksMathematics
Small subgraphs of large minimum degree
Abstract
In 1991, Erdős, Faudree, Rousseau and Schelp asked to estimate the smallest such that every -vertex graph with average degree at least has a subgraph on at most vertices with minimum degree at least . We resolve this problem up to polylogarithmic factors for all even values of . More precisely, we prove that every -vertex graph with minimum degree has a subgraph on vertices with minimum degree at least , whenever is even. This improves a result of Janzer, Sudakov and Tomon, who obtained a similar conclusion for subgraphs of average degree at least . We also prove that for every positive integer and every , there exists a finite family of graphs with minimum degree such that . This is tight and is the first result of similar kind that applies to odd values of greater than 3.