Diameter Bounds and Finiteness of Graphs from Local Intersection Data

Source 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}{λ+2}$$ 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$, and $(s,c)\ne(4,3)$. 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.