Paperlane

no. 12 · Tuesday 10 November 2026

Diameter Bounds and Finiteness of Graphs from Local Intersection Data

Kaizhe Chen

math.CO · v2

Abstract

We extend the Bakry–Émery curvature framework on graphs, broadening its applications and strengthening the resulting diameter bounds. We study diameter bounds and finiteness for amply regular graphs, distance-regular graphs, $(s,c,a,k)$-graphs, and locally strongly regular graphs. In particular, for an amply regular graph with parameters $(v,k,λ,μ)$, we prove that \[{\rm{diam}}(G)\le4+8\log\frac{k}{\max\{λ,μ\}}\] when $μ>2$ and $k\ge3λ^2/μ$, improving the previous linear bound $4k/(λ+4)$ to a logarithmic bound. We also address several related conjectures. In their monograph \emph{Distance-Regular Graphs}, Brouwer, Cohen, and Neumaier conjectured that every amply regular graph with $μ>1$, except the icosahedron, satisfies ${\rm{diam}}(G)\le2k/(λ+2)$. We confirm this bound when $μ>λ+1$ and give counterexamples to the conjecture with $μ=λ$. For amply regular graphs with $μ\geλ$ and $μ>1$, we obtain ${\rm{diam}}(G)\le 2k/μ+1$. This proves the Qiao–Park–Koolen conjecture. In 1983, Terwilliger conjectured that every $(s,c,a,k)$-graph with $c>1$ is finite. We prove this conjecture when ``$s>2$, $c>2$, $(s,c)\ne(4,3)$'' and when ``$s=2$, $c>7$''. Moreover, we prove Weetman's finiteness conjecture for locally strongly regular graphs when the local parameter $μ>1$, and disprove his stronger conjecture that every strongly regular graph is an $\mathscr{S}$-graph. We also prove that every graph whose local graphs all have rank 3 is finite, which in particular proves a conjecture of Soicher in 1992.

fields
Combinatorics
pdf ↗ page arXiv:2610.36620 ↗