Diameter Bounds and Finiteness of Graphs from Local Intersection Data
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 diam(G)≤4+8logk/(λ+2) when μ>2 and k≥3λ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 diam(G)≤2k/(λ+2). We confirm this bound when μ>λ+1 and give counterexamples to the conjecture with μ=λ. For amply regular graphs with μ≥λ and μ>1, we obtain diam(G)≤ 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)≠(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 𝒮-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.
Related
- Co-intersection graphs of nonabelian finite simple groups have diameter two
- A priori bounds for geodesic diameter. Part III. A Sobolev–Poincaré inequality and applications to a variety of geometric variational problems
- Intersection Orbital Graphs of Permutation Groups and Reconstruction of Simple Groups
- Finiteness of Non-decomposable Critically Frustrated Signed Graphs
- Normal approximation for subgraph counts in random intersection graphs: the case of cliques
BibTeX
@misc{chen2026diameter,
title = {{Diameter Bounds and Finiteness of Graphs from Local Intersection Data}},
author = {Kaizhe Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36620},
eprint = {2610.36620},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36620},
}
RIS
TY - UNPB
TI - Diameter Bounds and Finiteness of Graphs from Local Intersection Data
AU - Kaizhe Chen
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.36620
UR - https://arxiv.org/abs/2610.36620
AB - 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 diam(G)≤4+8logk/(λ+2) when μ>2 and k≥3λ^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 diam(G)≤2k/(λ+2). We confirm this bound when μ>λ+1 and give counterexamples to the conjecture with μ=λ. For amply regular graphs with μ≥λ and μ>1, we obtain diam(G)≤ 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)≠(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 𝒮-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.
ER -