The paper studies what logical properties large random graphs almost surely have or almost surely lack, a subject called "limit laws." The focus is on two models. The first is an extremely sparse random graph where edges are included with very low probability, and small connected pieces (components) are then deleted. The authors show that under a precise condition relating the deletion threshold to the graph size, every statement in a powerful logical language called MSO2 is either almost certainly true or almost certainly false in the resulting graph. This is called a zero-one law. The proof works by carefully counting components, breaking the graph into independent pieces, and using deep combinatorial facts about trees. The authors also show the condition is essentially tight: if you ignore a certain term in the condition, counterexamples arise from star-shaped components appearing at detectable thresholds.
The second model is bond percolation on a discrete grid (torus) in d dimensions, where edges are kept independently with some probability. The authors identify a precise hierarchy of critical probability scales, governed by a parameter k, at which the logical behavior of the graph changes dramatically. Depending on whether a key quantity involving the probability and grid size converges to zero, infinity, or a positive finite number, the graph either satisfies a zero-one law, a weaker convergence law, or no limit law at all. Pruning small components again restores a zero-one law in certain regimes.