{"id":"arxiv/2610.26763","url":"https://arxiv.org/abs/2610.26763","tags":["math.CO"],"score":0,"title":"Small subgraphs of large minimum degree","domain":"math.CO","source":"arxiv","authors":["Zach Hunter","Barnabás Janzer","Oliver Janzer","Benny Sudakov"],"reviews":0,"subject":"math.CO","summary":"In 1991, Erdős, Faudree, Rousseau and Schelp asked to estimate the smallest $u=u(n,d,s)$ such that every $n$-vertex graph with average degree at least $d$ has a subgraph on at most $u$ vertices with minimum degree at least $s$. We resolve this problem up to polylogarithmic factors for all even values of $s$. More precisely, we prove that every $n$-vertex graph with minimum degree $d\\geq s$ has a subgraph on $O_s\\left(\\max\\left\\{\\frac{n}{d^{s/(s-2)}}(\\log n)^{180},\\log n\\right\\}\\right)$ vertices with minimum degree at least $s$, whenever $s\\ge 4$ is even. This improves a result of Janzer,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-19","reactions":{}}