Spectral gap of a Bayesian graph Laplacian

Definitions and mathematical statement

In a standard undirected rate model on $n\geq2$ vertices, let edge counts $N_{ij}(t)$ be independent Poisson processes with unknown rates $w^0_{ij}\geq0$. Under independent improper flat priors $dw_{ij}$ on $[0,\infty)$, the posterior at $t>0$ has independent edge weights with densities proportional to \[ w^{N_{ij}(t)}e^{-tw}\,dw, \] that is, Gamma shape $N_{ij}(t)+1$ and rate $t$. This is one explicit interpretation of the source's flat-prior construction; the actual prior/range conventions are not supplied.

For a weighted graph, the combinatorial Laplacian is $L_{ii}=\sum_{j\ne i}w_{ij}$ and $L_{ij}=-w_{ij}$ for $i\ne j$. Write $\operatorname{gap}(G)=\lambda_2(L)$ with eigenvalues in increasing order. The source does not explicitly distinguish this normalization from a normalized-walk gap.

Study $\operatorname{gap}(G(t))$ under the posterior random graph law. For large graphs, is it concentrated near its expectation under suitably weak hypotheses? Specify the concentration scale, conditional versus joint expectation, graph-size limit, and admissible true rate arrays. Also determine how long one must observe before the posterior gap is close to $\operatorname{gap}(G(\infty))$, including a bound in graph size, accuracy, and failure probability. In the rate-learning interpretation $G(\infty)$ is the true weighted graph after posterior collapse, but the record does not define it.

A collection of posterior distributions at different times does not by itself prescribe a coupling of sampled graphs into one stochastic process. The convergence mode, additive versus relative error, and treatment of a zero limiting gap are unspecified. No connectivity, degree lower bound, or rate regularity condition is silently imposed as the missing weak assumptions.

Short English statement

For graphs inferred from Poisson edge observations, establish large-graph concentration of the posterior Laplacian gap and determine the observation time needed to approximate its limiting value. Fix priors, normalization, coupling, and error criteria.

Sources

• David Aldous, Open problems, page identified as gap_ion.html in the maintained index, https://www.stat.berkeley.edu/~aldous/Research/OP/index.html; accessed 2026-07-29. The extraction includes HTML and linked primary PDF text but no separate PDF citation is supplied.
• The summary mentions Chung--Lu-type spectral models, graphon limits, and Bayesian graph inference as related areas without publication identifiers or results for this posterior process.
• Local registry data/unsolvedmath/problems.json, permanent UnsolvedMath ID $9700009$, source code catalogue entry, Spectral gap of a Bayesian graph Laplacian. Dataset attribution: Ulam AI and the UnsolvedMath Contributors.