Small subgraphs of large minimum degree
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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.26763
curl -X POST /api/v1/records/arxiv/2610.26763/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.26763/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'