How a small majority takes over a sparse network

Suppose every person in a network holds one of two opinions. Once a day, everyone looks at their neighbors and adopts the local majority. If their neighborhood is tied, they keep their current opinion.

Assign the initial opinions by independent fair coin flips. Among \(N\) people, the two sides will typically differ by order \(\sqrt N\). Does that small imbalance disappear into local noise, or does the initial majority take over the network?

With Ashwin Sah, we prove that it takes over on a sparse random graph. In the model \(G\sim\mathbb G(N,p)\), each pair of vertices is connected independently with probability \(p\), so a vertex has about \(pN\) neighbors.

The result

Day 1 is the initial coloring; day \(k+1\) is obtained from day \(k\) by one simultaneous update. The probability is over both the graph and the initial opinions.

A vertex sees only a small part of the network. Yet those local votes amplify an initial advantage that is vanishingly small as a fraction of the population. The obstacle to proving this is that everyone uses the same graph every day: yesterday’s votes have already revealed information about the edges we need to analyze today.

The paper, a complete Lean formalization, and a proof atlas are now available. Getting them finished took four years, and the tools available for doing mathematics changed along the way.

How the proof was finished

I began working on this problem in 2022. Most of the proof was found between 2022 and 2024, and the manuscript then went through substantial human revision with Ashwin. By August 2025 we had a complete proof, written without AI assistance; human revisions continued into early 2026. Its organization still reflected the order in which the argument had been discovered, with many dependencies left implicit, which made it hard to audit.

From August 2025 through August 2026 we revised it with GPT‑5.5, GPT‑5.6, and Claude Fable: comparing versions, tracing dependencies, and rewriting. In the first days of September 2026 the paper was restructured along its logical dependencies rather than its discovery history and the whole argument was audited line by line; the audit resolved several minor issues in the original presentation.

Between September 6 and 10, GPT‑6 Astra formalized the entire proof in Lean. The literature inputs include the enumeration and edge-probability results of Liebenau and Wormald, formalized separately by Claude Fable in a single session pointed at the two papers. On September 12–13, we extended the proof and its formalization to cover every density up to \(p=1\) at once, using GPT‑6 Astra and Claude Fable, including a formalization of the argument of Fountoulakis, Kang, and Makai for dense graphs. The whole formalization depends only on Lean’s standard axioms.

We have preserved the manuscript as it stood in August 2025, before any AI assistance, as part of this release. It records the pre-AI state of the mathematics and makes it possible to see what changed during the final rewrite. It is complete as a proof but not as a paper: its bibliography was never assembled, and several relevant papers are not cited, as its own to-do note on the first page says.

1. 2022–2024The proof.
2. 2024 – Aug 2025Human revision. Complete manuscript, no AI.
3. Aug 2025 – Aug 2026Revision with GPT‑5.5, GPT‑5.6, Claude Fable.
4. Sept 1–5, 2026Restructure along dependencies; line-by-line audit; completed paper.
5. Sept 6–10, 2026Lean formalization (GPT‑6 Astra), Liebenau–Wormald formalized (Claude Fable), proof atlas.
6. Sept 12–13, 2026Extension to every density up to \(p=1\), using GPT‑6 Astra and Claude Fable, including the Fountoulakis–Kang–Makai argument for dense graphs.

After the change

The world this paper is released into is not the one it was started in. In the past two months, Claude Fable found a counterexample to the Jacobian conjecture; Claude wrote the first complete computer-checked proof of Fermat’s Last Theorem in eleven days; and an OpenAI system resolved the Navier–Stokes existence and smoothness problem, with a proof produced in 88 hours and its Lean formalization completed 17 hours later. None of this was plausible when I started.

I do not have a general verdict on what this means for mathematics. It has changed my own calculation about spending years on another proof. It also made it possible to finish this one as a paper, a complete Lean formalization, and an explanation that people can actually navigate.

I worked on this problem on and off for four years. For much of that time the proof existed as a long manuscript whose presentation I knew was not ready to publish. Most of the ideas in the proof were found before frontier models could do research mathematics; the complete August 2025 manuscript was written without them; the final version was completed after that changed.

I do not know whether I will work on another problem like this, but I wanted to finish this one properly.

Read the result

• The paper PDF, 86 pages.
• The proof atlas The paper statement by statement, proofs folded; each part links to its place in the paper, in the August 2025 manuscript, and in the Lean development.
• The Lean formalization Both theorems and their completion checks, in a dedicated public repository.
• The August 2025 manuscript PDF, 45 pages. The manuscript as it stood in August 2025.
• arXiv:2609.14957 The paper on arXiv.

The theorem

For the proof discussion below, take \(p=\Theta(N^{-\theta})\). This is the sparse regime where the multi-day argument is needed. The theorem itself is uniform over the full displayed interval: the paper makes the sparse estimates uniform in \(p\), then uses the estimates of Fountoulakis, Kang, and Makai for the denser range.

The theorem allows any placement of the initial \(+1\) vertices. Only their number matters. For random opinions, the initial lead is usually of order \(\sqrt N\): the probability of a lead smaller than \(a\sqrt N\) can be made small by choosing \(a\) small, and that of a lead larger than \(b\sqrt N\) by choosing \(b\) large. Apply the theorem to the color that leads, with a fixed \(T\) large enough to cover these bounds, to obtain the corollary.

Benjamini, Chan, O’Donnell, Tamuz, and Tan conjectured in 2014 that random initial opinions reach near-unanimity whenever \(pN\to\infty\). Subsequent work proved unanimity on progressively sparser graphs. Our result proves unanimity whenever \(pN\ge N^\varepsilon\) for any fixed \(\varepsilon>0\). This does not fully resolve the conjecture: it remains open when the average degree tends to infinity more slowly than every positive power of \(N\), for example when \(pN=\log N\).

These proofs share a shape. They control a small number of early days directly and then enter a regime where graph expansion forces consensus. As the graph becomes sparser, the random initial imbalance needs more days before it is large enough for that final argument. Reaching densities below \(N^{-2/3}\) therefore requires following the conditioned dynamics for more days, and the number of days needed grows without bound as \(\theta\to1\). Our method follows the process for an arbitrary fixed number of days. That is what lets \(\theta\) approach \(1\).

If the randomness were refreshed every day

There is an easy calculation that predicts the theorem.

Suppose the current opinion classes have sizes \(\tfrac{N+\Delta}{2}\) and \(\tfrac{N-\Delta}{2}\), so the current majority lead is \(\Delta\). If we sampled a fresh random graph for the next update, a typical vertex would compare

Up to a constant, each update multiplies the lead by the square root of the average degree. With \(p=N^{-\theta}\) we have \(\sqrt{pN}=N^{(1-\theta)/2}\), so starting from the random scale \(\Delta\asymp\sqrt N\) we should need about \(1/(1-\theta)\) updates before the lead is of order \(N\). If the graph were independently resampled after every update, we could repeat essentially this calculation each day, and the theorem would be an exercise.

But the graph is not resampled.

The same graph, one day later

The day-2 opinions reveal information about the edges of \(G\). A vertex ended up on one side because one combination of its degrees exceeded another. When we compute day 3, we are no longer looking at an untouched Erdős–Rényi graph: we are looking at the original graph conditioned on all of those degree inequalities. Each new day adds another layer of conditioning on the same edges. The easy calculation still predicts what should happen, but it can no longer simply be repeated.

We deal with this by choosing what to remember. After \(k\) recorded days, partition the vertices into the \(2^k\) classes with a common opinion history: one class contains the vertices that were \(+,-,+,\ldots\), another the vertices that were \(-,-,+,\ldots\). The state of the process on day \(k\) is this partition together with, for every vertex, its number of neighbors in every class. It determines the exact number of edges inside each class and between each pair of classes, and it determines the entire history of the process. It does not determine the graph.

What it does determine is the law of the graph. Conditioned on the state, \(G\) is a uniformly random graph with the prescribed degrees, independently on each of the

block pairs: a uniform graph with given degree sequence inside each class, and a uniform bipartite graph with given side degrees between each pair of classes. Nothing else about \(G\) is known, and nothing else is needed: the next day’s opinions are read off from the degrees, and the sequence of states is a Markov chain whose transition rule does not depend on \(p\) or on the initial coloring. Each day, in effect, the graph is resampled after all, but from a degree-constrained ensemble rather than from \(\mathbb G(N,p)\).

The history partition grows exponentially with the number of days. We can analyze any fixed number of days because this finite collection of degree-constrained ensembles records exactly the information that matters.

Recovering randomness after conditioning

A uniformly random graph with a prescribed degree sequence is a rigid object, but it is not an arbitrary one. The engine of the proof is the asymptotic enumeration of graphs by degree sequence, begun by McKay and Wormald for dense graphs, extended to the bipartite case by Canfield, Greenhill, and McKay, and completed across all densities by Liebenau and Wormald, including the bipartite case. Their formulas say that the degree sequence of a random graph with a given number of edges behaves like a sequence of nearly independent binomial variables conditioned on their sum.

There is a useful analogy with statistical mechanics. A microcanonical ensemble fixes a conserved quantity, such as energy, exactly. A canonical ensemble lets it fluctuate and chooses a parameter, such as temperature, to give the right mean. Here edge totals play the role of energy. Adjusting the binomial probabilities plays the role of choosing the temperature.

To use that idea, retain the history partition and the edge totals, but let the individual degrees vary. For a vertex \(x\) in history class \(s\), write \(\mathbf d[x,t]\) for its number of neighbors in class \(t\), \(n[t]\) for that class’s size, and \(m[s,t]\) for the total of those degrees over \(x\in V_s\).

This is an equivalence-of-ensembles strategy, with a quantitative cost. Matching totals in expectation makes the independent model useful; it does not remove the need to impose them exactly. We prove that this final conditioning is not too rare, so concentration estimates survive it. That is how randomness becomes usable again after several days of degree constraints.

This strategy has a direct lineage, and the paper stands on it.

1. 1990–2008McKay and Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of \(\mathbb G(N,p)\) as nearly independent binomials. Canfield, Greenhill, and McKay. The bipartite enumeration formula in the dense range.
2. 2017, 2020Liebenau and Wormald. The enumeration formula for all densities, and the bipartite and directed versions. This is what makes the sparse regime reachable.
3. 2021Ferber, Kwan, Narayanan, Sah, Sawhney, Friendly bisections of random graphs. Enumeration applied to a stochastic process driven by degree information.
4. 2021Sah and Sawhney, Majority dynamics: the power of one. Iterated degree revelation and degree-constrained graph models for majority dynamics in the dense regime. The paper suggests that the Liebenau–Wormald formulas might allow substantially sparser analysis.
5. 2026This paper. The program carried through the complete multi-day, multi-history conditioned system, for an arbitrary fixed number of days.

Tracking the lead along a deterministic reference

The binomial comparison gives a detailed prediction for one day: how each history class splits, and how many edges run between the new classes. To follow many days, we must show that these predictions remain valid after each successive update.

Start the finite binomial formulas from balanced initial data. At each step, solve for the tilts that match the edge totals, compute the next sizes and totals, and round the sizes. On day \(k\), the resulting deterministic reference consists of

for opinion histories \(s,t\) of length \(k\): class sizes, edge totals, and tilts, respectively. These quantities depend on \(N\) and \(p\). Their evolution is the paper’s idealized process, a deterministic sequence of arrays rather than the trajectory of a random graph.

The Gaussian system describes its leading terms. It gives limiting class proportions \(\nu[s]\), edge-density corrections \(\mu[s,t]\), and Gaussian mean parameters \(\gamma[s,t]\), all defined by a recursion independent of \(N\) and \(p\). But even an accurate estimate \(\widetilde n[s]\approx N\nu[s]\) is too coarse for our purpose: its error can exceed the entire majority lead.

So we keep the finite reference and track the effect of the initial imbalance as a shift away from it. If the initial lead is \(2\tau\sqrt N+O(1)\), the statement we prove, with high probability on each day in the perturbative phase, is

The coefficients \(\varepsilon[s]\) come from the linear response of the Gaussian system. The baseline is the full finite process; only the response is replaced by its leading approximation.

Why can this small shift be detected? The finite reference has exact color symmetry: \(\widetilde n[s]=\widetilde n[\bar s]\), where \(\bar s\) reverses every opinion in the history. When we sum the class sizes to find the lead, the reference terms cancel exactly. The response terms reinforce each other: within every old history class, the child ending in \(+1\) has a positive response and the child ending in \(-1\) a negative one. This coherence follows from a projection argument in Gaussian space.

Making this expansion persist is the hard part. Along this particular perturbed reference, we prove that the next edge totals again admit the required tilts, that all the conditioning and regularity estimates still apply, and that the next sizes and totals match the next perturbed prediction. The errors must stay smaller than the growing signal. This closes the induction for the full finite system and its bias correction; the Gaussian recursion supplies the coefficients that make it work.

Thus, with high probability, each fixed update within the perturbative phase amplifies the lead by a factor of order \(\sqrt{pN}\):

The constant \(c_k\) is determined by the response coefficients \(\varepsilon[s]\) on days \(k\) and \(k+1\); coherence guarantees that it is positive. The fresh-graph calculation predicts the right growth scale, but \(c_k\) need not equal its constant \(\sqrt{2/\pi}\).

From amplification to unanimity

Once the lead is large enough, a shorter argument finishes the proof. During the expansion phase, the argument above follows the process until the initial \(\sqrt N\)-scale lead has been amplified to order at least \(\frac{N}{\sqrt{pN}}\log N\), after \(O(1/(1-\theta))\) days in the sparse regime \(p=\Theta(N^{-\theta})\). At that point a deterministic argument based on the pseudorandomness of \(G\), in the form used by Chakraborti, Kim, Lee, and Tran, takes over: one further day reduces the minority to a small fraction of the vertices, and each subsequent day contracts it by a factor of order \(1/(pN)\), until no minority vertex remains.

Most of the proof is devoted to showing that heavily conditioned randomness continues to behave as predicted. The contraction argument is much shorter to write down, although both phases take order \(1/(1-\theta)\) days.

Sources and formalization notes

One correction to a printed formula. Theorem 1.6 of Liebenau and Wormald (2017) gives the probability of a single edge in a random graph with given degrees; as displayed, it omits two terms linear in the degree deviations that appear in the full expansion in the body of their paper. We use the full expansion, and our theorem is unaffected. This came out of the formalization.

References

1. I. Benjamini, S.-O. Chan, R. O’Donnell, O. Tamuz, L.-Y. Tan. Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs. Stochastic Process. Appl. 126 (2016), 2719–2733. arXiv:1405.2486 · doi
2. N. Fountoulakis, M. Kang, T. Makai. Resolution of a conjecture on majority dynamics: rapid stabilization in dense random graphs. Random Structures Algorithms 57 (2020), 1134–1156. arXiv:1910.05820 · doi
3. D. Chakraborti, J. H. Kim, J. Lee, T. Tran. Majority dynamics on sparse random graphs. Random Structures Algorithms 63 (2023), 171–191. arXiv:2105.12709 · doi
4. J. H. Kim, B. Tran. A new density limit for unanimity in majority dynamics on random graphs. arXiv:2503.07447 (2025).
5. S. Jaffe. A new bound in majority dynamics on random graphs. arXiv:2503.14401 (2025).
6. B. D. McKay, N. C. Wormald. Asymptotic enumeration by degree sequence of graphs of high degree. European J. Combin. 11 (1990), 565–580. doi
7. B. D. McKay, N. C. Wormald. The degree sequence of a random graph. I. The models. Random Structures Algorithms 11 (1997), 97–117.
8. E. R. Canfield, C. Greenhill, B. D. McKay. Asymptotic enumeration of dense 0-1 matrices with specified line sums. J. Combin. Theory Ser. A 115 (2008), 32–66. arXiv:math/0606496 · doi
9. A. Liebenau, N. Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph. J. Eur. Math. Soc. 26 (2024), 1–40. arXiv:1702.08373 (2017) · doi
10. A. Liebenau, N. Wormald. Asymptotic enumeration of digraphs and bipartite graphs by degree sequence. Random Structures Algorithms 62 (2023), 259–286. arXiv:2006.15797 (2020) · doi
11. A. Ferber, M. Kwan, B. Narayanan, A. Sah, M. Sawhney. Friendly bisections of random graphs. arXiv:2105.13337 (2021).
12. A. Sah, M. Sawhney. Majority dynamics: the power of one. arXiv:2105.13301 (2021).
13. L. Alpöge, with Claude Fable 5. A counterexample to the Jacobian conjecture in dimension three, July 2026. report · J. Levinson’s expository note
14. Anthropic. Formalizing Fermat’s Last Theorem, September 2026. anthropic.com · repository
15. OpenAI. On the Navier–Stokes Millennium Prize Problem, September 2026. openai.com