Sh:1277

• Mirabi, M., & Shelah, S. Limit laws for component-pruned sparse random graphs and percolated tori. Preprint. arXiv: 2607.11033
• Abstract:
  Let G_D(n;r) be the random geometric graph obtained from n independent uniform points on the D-dimensional torus, with two vertices joined when their torus L^\infty-distance is at most r. We study first-order zero-one and convergence laws for this model in fixed-radius and sparse regimes.

  For fixed 0<r<1/2, we classify the first-order zero-one law. In dimension one the zero-one law follows from McColm’s theorem. In dimension two, adjacent twin pairs give the obstruction: their number converges to \text{Poisson}(1/(8r^2)). More generally, for fixed D the expected number of adjacent twin pairs is asymptotic to 2^{D-1-D^2}r^{-D(D-1)}n^{2-D}, so adjacent twins are critical exactly in dimension two. For every fixed D\ge3 and 0<r<1/2, we prove a different Poisson obstruction. Two disjoint D-cliques may have the same external common-neighborhood box; with a fixed first-order richness condition, the number of such rich box-twin pairs converges to a non-degenerate Poisson random variable. Consequently, for fixed 0<r<1/2, the first-order zero-one law holds precisely in dimension one.

  For shrinking radii, we prove a first-order convergence law at the first edge window. If n^2r_n^D\to a\in[0,\infty), then with high probability G_D(n;r_n) is a matching together with isolated vertices, the number of edges converges to \text{Poisson}(2^{D-1}a), and every first-order sentence has an explicit limiting probability determined by this Poisson matching limit. We also prove Poisson limits for isolated clique components: for each fixed k\ge2, if n^k r_n^{D(k-1)}\to a\in[0,\infty), then the number of connected components isomorphic to K_k converges to a Poisson random variable with an explicit geometric mean. Between consecutive component-size thresholds, if n^k r_n^{D(k-1)}\to\infty \quad\text{and}\quad n^{k+1}r_n^{Dk}\to0, then the graph has a deterministic saturated finite-component profile and satisfies a first-order zero-one law. Finally, for fixed D\ge3 and 1/4\le r<1/2, we prove a higher-arity thin-cell estimate of order 1/n for a definable common-neighborhood relation.

• Version 2026-07-17 (26p)

@article{Sh:1277,
 author = {Mirabi, Mostafa and Shelah, Saharon},
 title = {{Limit laws for component-pruned sparse random graphs and percolated tori}},
 note = {\href{https://arxiv.org/abs/2607.11033}{arXiv: 2607.11033}},
 arxiv_number = {2607.11033}
}