Submit progress

on Erdős #1016 · graph theory / cycles

The statement

Let $h(n)$ be minimal such that there is a graph on $n$ vertices with $n+h(n)$ edges which contains a cycle on $k$ vertices, for all $3\leq k\leq n$ . Estimate $h(n)$ . In particular, is it true that

h(n) \geq \log_2n+\log_*n-O(1),

where $\log_*n$ is the iterated logarithmic function?

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.