ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let k≥2k\geq 2, let n≥k+1n\geq k+1, and define

tk(n)=(k−1)(n−k+2)+(k−22).t_k(n)=(k-1)(n-k+2)+\binom{k-2}{2}.

A graph has minimum degree kk if every vertex has at least kk neighbors.

Erdős's conjecture. For every k≥2k\geq 2 there exists an ϵk>0\epsilon_k>0 such that every graph on n≥k+1n\geq k+1 vertices and tk(n)+1t_k(n)+1 edges contains a subgraph of minimum degree kk with at most (1−ϵk)n(1-\epsilon_k)n vertices.

Erdős, Faudree, Rousseau and Schelp proved the corresponding existence result with a smaller saving of order n\sqrt n, while this paper improves the guaranteed saving to at least Ω(n/log⁡n)\Omega(n/\log n). The conjecture asks for a positive constant proportion of the vertices to be removed, and remains open in the supplied source.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.