Boundedly exchangeable graphs

Abstract

An infinite jointly exchangeable adjacency matrix is a mixture of graphon models, and its graph is almost surely empty or dense; classical matrix exchangeability therefore excludes sparse nonempty graphs. We study a point-process alternative, graph processes, whose vertices are identified with the atoms of a locally finite point process on a Polish latent space and whose edges are drawn conditionally independently from a symmetric connection kernel $W$. For a Poisson graph process with diffuse $σ$-finite intensity, we show that its edge measure is jointly exchangeable as a random measure if and only if $W$ is essentially constant. Non-constant kernels therefore require a different exchangeability notion. We introduce bounded exchangeability, under which every nontrivial bounded restriction determines an infinite jointly exchangeable adjacency matrix that is unique in distribution, with an associated local graphon representation. We then study threshold models on homogeneous Riemannian manifolds, in which Poisson-distributed vertices are connected whenever their intrinsic distance is at most a fixed threshold. On every infinite-volume manifold in this class, the model is sparse, its empirical degree distribution converges to a Poisson law, and its limiting clustering coefficient depends on an additional geometric parameter that can vary while the limiting degree law is held fixed.

Disclosure

“tical applicability. Acknowledgements The authors acknowledge the use of the AI-assisted tools ChatGPT (OpenAI; several versions of GPT-5; accessed via chatgpt.com) and Claude (Anthropic; Claude 4.8 Opus and Claude 5 Sonnet, accessed via claude.ai). These tools were used to suggest improvements to wording and grammar, to flag possible minor errors or omissions in the mathematical exposition for subsequent independent review, and to assist with LaTeX table formatting and code u”

PDF page 31

Classification

Code generation, completion, or debugging

Multiplier

2

Verified

2026-08-22T18:20:42.398038Z

Structural counts