Boros, Caro, Füredi and Yuster's asymptotic conjecture for non-repeated cycle lengths

Let f2(n)f_2(n) denote the maximum, over all nn-vertex 2-connected graphs, of the number of cycle lengths that occur exactly once. The authors' conjecture is

limnf2(n)/n=1.\lim_{n\to \infty} f_2(n)/\sqrt{n} =1.

This conjecture asserts that the lower bound obtained from Sidon sequences is asymptotically tight. The known construction gives f2(n)no(n)f_2(n)\geq \sqrt{n}-o(\sqrt{n}), while the matching upper bound remains open.

Sources & referencesView supporting material

Primary source

Jie Ma and Tianchi Yang, “Non-repeated cycle lengths and Sidon sequences”, arXiv:2007.12513 (2020).

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.