pipette
ENEnglish

Small subgraphs of large minimum degree

Zach Hunter, Barnab\'as Janzer, Oliver Janzer, Benny Sudakov

Preprint

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.

Resultado principalLimitación que admiten los autores

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 29 pages, 9 figures