How large must a counterexample to Seymour's second-neighborhood conjecture be?
the best proved lower bound on the order of a counterexample to Seymour's conjecture
- steps
- 2
- by AI
- 1
- since
- 2001
The line is the frontier over time, climbing as the bound goes up: higher is better here. Filled dots are steps that moved it; muted dots are results that did not. Orange dots are catalog entries, results with AI in the loop. Hollow dots are candidates under review and never move the line.Grey dots along the bottom edge are results from before the quantity had a number, placed at the worst end because they have no value on this axis. Dots that would overlap are nudged sideways a few pixels. Hover a dot for its value and attribution.
About this frontier
Seymour conjectured in 1990 that every finite oriented graph has a vertex whose second out-neighbourhood is at least as large as its first, . It is open. Fisher proved it for tournaments in 1996, Kaneko and Locke for minimum out-degree at most six in 2001, and a line of work has settled dense graphs under conditions on the missing edges. Each such result forces any counterexample to be larger, so the size of the smallest possible counterexample is a number that only moves upward and would go to infinity if the conjecture were proved. This frontier tracks it.
Every step, newest first
| Date | Value | Who | Model | Status | Source |
|---|---|---|---|---|---|
| 13 Aug 2026 | Running the same n <= 2*delta + 2 result with out-degree at least eight, which needs the out-degree-7 case. That case is the catalog's other Seymour entry, an unreviewed preprint leaning on a CP-SAT computation, so this row is conditional on it and drawn as a candidate. Dated one day later to keep the staircase readable; both figures are in the same paper. | The same bound with the out-degree-7 case of Sadhukhan, Sandeep and Sen | ChatGPT 5.5 Pro | candidate unreviewed | entry |
| 12 Aug 2026 | best The conjecture holds for every oriented graph of order n = 2*delta + 2 with no condition on the missing edges, and with Fisher's tournament theorem for every n <= 2*delta + 2. With out-degree at least seven that puts a counterexample at order at least 17. Unconditional. | Jake Brukhman, with the GPT-5 family and Claude | GPT-5 family, Claude | historical unreviewed | entry |
| 2001 | Kaneko and Locke settled minimum out-degree at most six in 2001, so any counterexample has out-degree at least seven; with the dense-case results available then, that forced order at least 16. The figure is as the 2026 dense-case paper states it, naming 16 as the bound it improves. | Kaneko and Locke's out-degree bound with the earlier dense-case results | – | historical | source ↗ |
All three figures are stated in the dense-case paper (arXiv:2608.11530), read here: it names 16 as the bound it improves, 17 as its own unconditional consequence, and 19 as what follows if the out-degree-7 preprint stands. The 19 row is therefore conditional and is drawn as a candidate. Two other axes were rejected: the out-degree threshold gives only two rows, and the Chen-Shen-Yuster constant 0.657 has a longer history but neither entry moves it. No ceiling is drawn, because proving the conjecture would send this quantity to infinity.