← All problems

Erdős Problem #642 — Graphs with fewer chords than cycle lengths

29 years old · traced to

For a positive integer nn, let GG range over finite simple graphs with ∣V(G)∣=n|V(G)|=n. For a simple cycle CC in GG, a chord is an edge of GG joining two vertices of CC that are not consecutive along CC; write cG(C)c_G(C) for the number of such edges. Define

f(n)=max⁡{∣E(G)∣:∣V(G)∣=n,cG(C)<∣V(C)∣ for every simple cycle C⊆G}.f(n)=\max\left\{|E(G)|: |V(G)|=n,\quad c_G(C)<|V(C)|\text{ for every simple cycle }C\subseteq G\right\}.

Is f(n)≪nf(n)\ll n? Equivalently, do there exist an absolute constant KK and an integer n0n_0 such that f(n)≤Knf(n)\leq Kn for all n≥n0n\geq n_0? Erdős Problem #642

Background

The problem is attributed to Hamburger and Szegedy and was recorded by Erdős. It asks for the edge-density threshold that forces a cycle with at least as many chords as vertices, the exact obstruction excluded in the definition of f(n)f(n). In related work, Bollobás showed that sufficiently large constant average degree forces a cycle whose chords contain a cycle; Chen, Erdős, and Staton extended this to arbitrarily long chains of cycles, each formed from chords of the preceding one. These nested-cycle results provide context, but they address a different forcing condition. Erdős Problem #642 Cycles with many chords Chen, Erdős, and Staton (1996)

References

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.