The cubic graph girth bound conjecture

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)log2ng(n).(2-\epsilon_0)\log_2 n \ge g(n).

The Moore bound gives only g(n)(2+on(1))log2ng(n)\leq (2+o_n(1))\log_2 n, while the best known lower bound is greater than 43log2n2\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.

Sources & referencesView supporting material

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.