The two-round minimal percolating set conjecture
Let be a finite projective plane of order , let be the infection rate, and let denote the percolation time of a percolating set . Two-round minimal percolating set conjecture. For each with
there exists a minimal percolating set with
This asserts the existence of minimal percolating configurations that infect the entire plane in exactly two rounds throughout the stated range. The source gives a construction and proof around the conjecture, but the supplied parser status is unresolved.
References
- Dániel Gerbner, Balázs Keszegh, Gábor Mészáros, Balázs Patkós and Máté Vizer, “Line Percolation in Finite Projective Planes”, arXiv:1608.00531 (2016).
Progress summary
The published problem was unresolved, but an unverified submission now claims a counterexample at the boundary, so the general question is not settled.
Gerbner, Keszegh, Mészáros, Patkós, and Vizer introduced the conjecture in their 2016 paper, asking whether every allowed infection rate admits a minimal configuration that finishes in exactly two rounds.
Known results
- Minimal percolating sets cannot finish in one round (Gerbner et al., 2016).
- For , the minimum percolation time is (Gerbner et al., 2016).
- For , a six-point construction gives for every admissible (Gerbner et al., 2016).
- For , the paper constructs minimal sets with percolation time , not (Gerbner et al., 2016).
November 7, 2026 community counterexample claim
A submitted argument claims that the conjecture fails for in , asserting that no inclusion-minimal percolating set has time . The claimed finite verification is unverified and has not been independently assessed.
Current status (as of November 2026): The cases and and the stated time- constructions are known; the full conjecture remains open, with an unverified submission claiming a counterexample at .
Sources
Solutions 1
Conjecture 20 fails at the allowed boundary (q,r) = (5,5): in PG(2,5) no inclusion-minimal percolating set has percolation time 2 at threshold 5.See full solution
The counterinstance is the projective plane PG(2,5), threshold 5, with synchronous updates and inclusion-minimality. The proof reduces minimality to closed deletion separators, normalizes a noncollinear triple, and checks a reverse-unit-propagation refutation of the finite formula. The paper specifies the geometric-to-Boolean bridge and the unconditional Lean endpoint. This refutes the read arXiv statement; the journal version was not read.
Result and scope: Conjecture 20 fails at the allowed boundary (q,r) = (5,5): in PG(2,5) no inclusion-minimal percolating set has percolation time 2 at threshold 5.
Complete proof and verification sources: No two-round minimal line-percolating set in PG(2,5): a counterexample to Conjecture 20 of Gerbner-Keszegh-Meszaros-Patkos-Vizer (arXiv:1608.00531) · PDF.
The paper page includes the supplementary proof-source JSON attachments (download all three parts) and extract_sources.py, which reconstruct the archived proof and verification sources. The linked paper gives the complete rigorous argument and specifies exactly which statements are formalized.
This is an AI-assisted research preprint. Internal review is not external journal peer review; bounded prior-art searches do not certify worldwide priority. See the paper for the source, interpretation, formalization, and trust limitations.