Small subgraphs of large minimum degree
En palabras de los autores
In 1991, Erd\H{o}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.
Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 29 pages, 9 figures