Anstee–Sali forbidden-configuration exponent conjecture
Follow the latest progress by email.
The Anstee–Sali conjecture predicts forb(n,F)=Θ(n^(X(F)−1)), relating the largest F-free configuration to its product exponent X(F). The r-extensions of the four-cycle, for r≥4, are a proposed counterexample family.
Why it matters and what counts as progress
Why it matters: The proposed exponent links forbidden matrix configurations to a product construction; a larger family exposes a limit of that prediction.
What counts as progress: Construct configurations exceeding the predicted exponent, or prove matching bounds for further forbidden configurations.
How the problem developed
Richard P. Anstee and Attila Sali Conjectured that the forbidden-configuration extremal count is governed by the exponent defined by the product construction for simple zero-one matrices.
- 2015 · Partial result [2]
Diana Raggi Showed computational hardness for determining the exponent predicted by the conjectural framework; this did not disprove the asymptotic formula.
- 26 Sept 2026 · Counterexample [3]
Richard P. Anstee, Attila Sali and Pei Wu Proved forb(n, 1_{r−2}×C₄)=Θ(n^{r−1/2}) for r≥4, giving a family of counterexamples to the 2005 exponent conjecture.
AI contribution
Forbidding r-extension of C₄ — a counterexample of the Anstee–Sali conjecture
For each r≥4, the r-extension of the four-cycle has product exponent X(F)=r but admits Ω(n^(r−1/2)) F-free configurations, exceeding the conjectured exponent r−1. The AI-origin contribution is identifying this counterexample family.
Sources
Website timeline
Publication dates and editorial changes.