The 4/3 diameter conjecture for Morgenstern Ramanujan graphs

At least 6 years old · documented by

Let qq be a prime power, let Fq\mathbb{F}_q be the finite field with qq elements, and let g∈Fq[t]g\in\mathbb{F}_q[t] satisfy gcd⁡(g,t(t−1))=1\gcd(g,t(t-1))=1. Let Xq,gX^{q,g} be the associated q+1q+1-regular Morgenstern Ramanujan graph. The 4/3 diameter conjecture. If qq is odd and gg is irreducible, then the diameter of Xq,gX^{q,g} is bounded from above by

(43+ε)log⁡q∣Xq,g∣+Oε(1).\left(\frac{4}{3}+\varepsilon\right)\log_q|X^{q,g}|+O_{\varepsilon}(1).

The conjecture is the graph-theoretic problem addressed by the paper and would improve the best currently known general diameter bound for these graphs.

References

Primary source

Naser T. Sardari and Masoud Zargar, “Ramanujan graphs and exponential sums over function fields”, arXiv:1909.07365 (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.