← All problems

The two-round minimal percolating set conjecture

10 years old · traced to

Let Πq\Pi_q be a finite projective plane of order qq, let rr be the infection rate, and let tr(A)t_r(A) denote the percolation time of a percolating set AA. Two-round minimal percolating set conjecture. For each rr with

4≤r≤q,4\leq r\leq q,

there exists a minimal percolating set ArA_r with

tr(Ar)=2.t_r(A_r)=2.

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
  1. 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

Refreshed
Open · progress reported

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 r=2r=2, the minimum percolation time is 22 (Gerbner et al., 2016).
  • For r=3r=3, a six-point construction gives t3(Πq)=2t_3(\Pi_q)=2 for every admissible qq (Gerbner et al., 2016).
  • For 4≤r≤(q+7)/34\leq r\leq (q+7)/3, the paper constructs minimal sets with percolation time 33, not 22 (Gerbner et al., 2016).

November 7, 2026 community counterexample claim

A submitted argument claims that the conjecture fails for (q,r)=(5,5)(q,r)=(5,5) in PG(2,5)\mathrm{PG}(2,5), asserting that no inclusion-minimal percolating set has time 22. The claimed finite verification is unverified and has not been independently assessed.

Current status (as of November 2026): The cases r=2r=2 and r=3r=3 and the stated time-33 constructions are known; the full conjecture remains open, with an unverified submission claiming a counterexample at (q,r)=(5,5)(q,r)=(5,5).

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 solutionHide 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.