← All problems

Erdős Problem #1016 — Minimum excess of pancyclic graphs

55 years old · traced to

For each integer n≥3n\geq 3, let h(n)h(n) be the least integer hh for which there is a graph GG with nn vertices and n+hn+h edges that contains a cycle of every length from 33 through nn. Thus GG must contain, for each integer kk with 3≤k≤n3\leq k\leq n, a cycle having exactly kk vertices (equivalently, kk edges); such a graph is called pancyclic. The problem is to estimate this minimum excess h(n)h(n) and, in particular, to determine whether an absolute constant CC exists such that, for all n≥3n\geq3,

h(n)≥log⁡2n+log⁡∗n−C,h(n)\geq \log_2 n+\log_* n-C,

where log⁡∗n\log_* n is the least number of repeated base-22 logarithms needed to reach a value at most 11. Changing the convention for log⁡∗n\log_* n 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 h(n)h(n) measures the additional edges beyond the nn 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 log⁡2n\log_2 n, 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 h(n)−log⁡2nh(n)-\log_2 n tends to infinity. The question therefore isolates a finer issue than the leading logarithmic scale: whether the extra log⁡∗n\log_* n term required by known constructions is also forced by a lower bound, up to an additive constant. Erdős Problems #1016

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.