betaFeedback

WorksMathematics

Small subgraphs of large minimum degree

Abstract

In 1991, Erdős, Faudree, Rousseau and Schelp asked to estimate the smallest u=u(n,d,s)u=u(n,d,s) such that every nn-vertex graph with average degree at least dd has a subgraph on at most uu vertices with minimum degree at least ss. We resolve this problem up to polylogarithmic factors for all even values of ss. More precisely, we prove that every nn-vertex graph with minimum degree d≥sd\geq s has a subgraph on Os(max⁡{nds/(s−2)(log⁡n)180,log⁡n})O_s\left(\max\left\{\frac{n}{d^{s/(s-2)}}(\log n)^{180},\log n\right\}\right) vertices with minimum degree at least ss, whenever s≥4s\ge 4 is even. This improves a result of Janzer, Sudakov and Tomon, who obtained a similar conclusion for subgraphs of average degree at least ss. We also prove that for every positive integer ss and every ε>0\varepsilon>0, there exists a finite family H\mathcal{H} of graphs with minimum degree ss such that ex⁡(n,H)=O(n2−2/s+ε)\operatorname{ex}(n,\mathcal{H})=O(n^{2-2/s+\varepsilon}). This is tight and is the first result of similar kind that applies to odd values of ss greater than 3.

Paper details

vlnc:W_b4snrft6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…