The cubic graph girth bound conjecture

At least 3 years old · documented by

Let g(n)g(n) denote the largest girth among all cubic graphs on nn vertices. Girth bound conjecture. There is a constant ϵ0>0\epsilon_0>0 such that

(2−ϵ0)log⁡2n≥g(n).(2-\epsilon_0)\log_2 n \ge g(n).

The Moore bound gives only g(n)≤(2+on(1))log⁡2ng(n)\leq (2+o_n(1))\log_2 n, while the best known lower bound is greater than 43log⁡2n−2\frac{4}{3}\log_2 n-2 for infinitely many explicitly constructed graphs. The conjecture proposes a uniform improvement to the leading constant in the upper bound.

References

Primary source

Aya Bernstine and Nati Linial, “An approach to the girth problem in cubic graphs”, arXiv:2206.14638 (2022).

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.