Erdős Problem #1016 — Minimum excess of pancyclic graphs
For each integer , let be the least integer for which there is a graph with vertices and edges that contains a cycle of every length from through . Thus must contain, for each integer with , a cycle having exactly vertices (equivalently, edges); such a graph is called pancyclic. The problem is to estimate this minimum excess and, in particular, to determine whether an absolute constant exists such that, for all ,
where is the least number of repeated base- logarithms needed to reach a value at most . Changing the convention for changes this inequality by at most an additive constant. Erdős Problems #1016
Background
The excess of a graph is its number of edges minus its number of vertices, so measures the additional edges beyond the edges needed for a connected graph with one cycle. The problem asks how much extra structure is required to realize every possible cycle length in a single graph, rather than merely to contain a long cycle. Bondy raised the minimal-pancyclicity question in 1971 and claimed, without giving details, bounds that already place the minimum near , with a possible iterated-logarithmic correction in the upper bound. Erdős Problems #1016 Minimal Pancyclicity, §4.5
Erdős believed Bondy’s upper bound was closer to the truth, but could not prove even that tends to infinity. The question therefore isolates a finer issue than the leading logarithmic scale: whether the extra term required by known constructions is also forced by a lower bound, up to an additive constant. Erdős Problems #1016
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
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.