Limit laws for component-pruned sparse random graphs and percolated tori

Abstract

We prove an ${\mathrm{MSO}}_2$ zero-one law for a very sparse Erdős-Rényi graph after pruning by component order. Let $p_n=c_n/n$, where $c_n\to 0$, and delete every component of order less than $f(n)$, where $f(n)\to \infty$. If \[ f(n)\bigl(\log f(n)+\log(1/c_n)\bigr)=o(\log n), \] then the resulting graph satisfies a zero-one law for ${\mathrm{MSO}}_2$, with quantification over sets of vertices and sets of edges. The proof combines uniform component counts, an MSO Feferman-Vaught decomposition for disjoint unions, and semilinearity of the order spectra of MSO-definable classes of finite trees. We also show that the term $f(n)\log f(n)$ cannot simply be omitted: star components can occur at first-order-visible Poisson thresholds. We further establish first-order limit laws for bond percolation on the discrete torus $T_L^d$. In the two-sided subpolynomial regime, pruning below a sufficiently slow threshold yields a zero-one law. For the unpruned model in either one-sided polynomial regime, the reciprocal exponents $\hat{I}\pm =1/k$ are precisely the critical scales. At such a scale, an extended limit of $N{p}_N^k$ or $N{q}_N^k$ equal to $0$ or $\infty$ gives a zero-one law; a positive finite limit gives a convergence law but not a zero-one law; and the absence of an extended limit gives failure of convergence. Finally, ${\mathrm{MSO}}_1$ already detects the parity of the torus side length through bipartiteness, producing a natural obstruction to monadic convergence in a near-deterministic regime.

26 pages

Topics & keywords