← All problems

Erdős Problem #752 — Many distinct cycle lengths from minimum degree and girth

34 years old · traced to

For a finite graph GG, let δ(G)\delta(G) be its minimum degree, let girth⁡(G)\operatorname{girth}(G) be the length of its shortest cycle (taken to be ∞\infty if it has no cycles), and define its cycle-length set by

C(G)={ℓ∈Z>0:G contains a cycle of length ℓ}.\mathcal{C}(G)=\{\ell\in\mathbb{Z}_{>0}:G\text{ contains a cycle of length }\ell\}.

The question is: for every integer s≥2s\ge 2, does there exist a constant cs>0c_s>0 such that, for every integer k≥2k\ge 2 and every finite graph GG satisfying δ(G)≥k\delta(G)\ge k and girth⁡(G)>2s\operatorname{girth}(G)>2s, one has

∣C(G)∣>csks ?|\mathcal{C}(G)|>c_s k^s\,?

Erdős Problem #752

The restriction k≥2k\ge2 makes explicit the intended degree range: if k=1k=1, a single edge has minimum degree 11, infinite girth, and no cycle lengths. Erdős Problem #752

Background

The question is recorded among Erdős’s problems on cycle lengths and is attributed to Erdős, Faudree, and Schelp; the case s=2s=2 was proved earlier. Its central tension is that forbidding all cycles of length at most 2s2s imposes strong local sparsity, while a large minimum degree should force a broad range of longer cycle lengths. The result for general ss is stronger than merely counting distinct lengths: it produces a run of consecutive even cycle lengths. Erdős Problem #752 Erdős (1992)

References

P. Erdős, Some of my favourite problems in various branches of combinatorics, Le Matematiche 47 (1992), no. 2, 231–240.

Source: P. Erdős, Some of my favourite problems in various branches of combinatorics, Le Matematiche 47 (1992), no. 2, 231–240.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.