{"id":"arxiv/2607.11033","url":"https://arxiv.org/abs/2607.11033","tags":["math.LO","math.CO","math.PR"],"score":0,"title":"Limit laws for component-pruned sparse random graphs and percolated tori","domain":"math.LO","source":"arxiv","authors":["Mostafa Mirabi","Saharon Shelah"],"reviews":0,"subject":"math.LO","summary":"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\\to0$, 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.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-13","reactions":{}}