Attack log — Seymour's second-neighborhood conjecture

2026-08-17 — start

• Folder empty except PROBLEM.md. House: write only here; no git; cite what we beat; no invented dent.
• Conjecture (Seymour, ~1990; Dean–Latka 1995): every oriented graph has a vertex $v$ with $|N_2^+(v)|\ge|N_1^+(v)|$.
• Tonight: a certified new small-order census, a new reducible configuration with an independently checkable certificate, or a proof for another hereditary class. Isolated random-graph statistics are residue.

Published record (fetched tonight)

A Pisa graph (Halkiewicz) is a strongly connected oriented graph with $\Delta=\max_v\bigl(|N_2^+|-|N_1^+|\bigr)=0$. A Seymour-tight orientation (Guo–Kang–Zwaneveld) has every margin exactly 0; the strong ones are Pisa.

Halkiewicz Conjecture 5.1 says every Pisa graph has underlying graph $C_n$ or $K_n$ minus a matching. Their own $n=7$ table already lists 720 labeled Pisa graphs whose missing-edge graph is 2-regular — not a matching. Guo–Kang–Zwaneveld's directed cycle-square $\overrightarrow{C_7}^2$ is such an example. So the stated matching conjecture is already false at the order they computed; the live computational question they pose is the $n=8$ census (their open problem (3)).

Wikipedia still quotes Kaneko–Locke $n\le 15$. Brukhman (five days ago) is the current order bound if one accepts only refereed $\delta^+$ theorems.

Plan

1. Independently recompute Halkiewicz's labeled Pisa counts for $n\le 7$, and check the cycle-power / lex-product examples.
2. Certified census of Pisa graphs at $n=8$ (the first open order), with a replayable enumerator and a per-graph verifier. Classify underlying / missing graphs.
3. In parallel: try $n=2\delta+3$ (Brukhman says the same counting dies) or a missing-cycle class (not covered by Fidler–Yuster / Dara / Daamouch).
4. If the census does not finish or does not beat a published number, leave the residue and do not claim a bound.

Local PDFs: compute/refs/.

2026-08-17 — published constructions replayed

compute/check_known.py confirms Guo–Kang–Zwaneveld Lemma 2.1: $\overrightarrow{C_n}^k$ is Seymour-tight iff $2k<n$. In particular $\overrightarrow{C_7}^2$ is a Pisa graph whose missing graph is 2-regular, so Halkiewicz Conjecture 5.1 (underlying $C_n$ or $K_n$ minus a matching) is already false at the order they enumerated. Their own Table 2 lists those 720 graphs. The live question is the $n=8$ census and any genuine new class.

$\overrightarrow{C_8}^2$ and $C_4[E_2]$ are Pisa on 8 vertices with 3-regular missing graph.

2026-08-17 — labeled Pisa census $n\le 7$

compute/enum_pisa.c (OpenMP bitmask) independently reproduced Halkiewicz:

n=7 wall time 217s. New observation not in Halkiewicz: every Pisa graph on 7 vertices is Seymour-tight; on 6 vertices only 270/1050 are. All $n\le 7$ oriented graphs have $\Delta\ge 0$, as Kaneko–Locke already implies.

This is a replay, not a dent. n=8 labeled ($3^{28}$) is ~130 core-hours at this rate.

2026-08-17 — the click: Brukhman's next layer is Eulerian

Brukhman proves every oriented graph with $n\le 2\delta+2$ has a Seymour vertex. At $n=2\delta+3$ the same double count gives only $I\ge 3\ell$ and $Q\le \ell+n$, no contradiction.

If a counterexample at $n=2\delta+3$ is out-regular of degree $\delta$, then $|E|=n\delta$ and the missing graph has average degree 2. If it is also in-regular (Eulerian), the missing graph is a 2-factor and the Brukhman capacity bound is forced to equality:

• $|U(v)|=3$, $|N_2^+(v)|=\delta-1$ for every v
• $q(x)=2$, $P(x)$ is a directed 3-cycle inside the trap $T(x)$
• $P(x)$ dominates $T(x)\setminus P(x)$

Further: $N^-(v)\subseteq N_2(v)\cup U(v)$ with sizes $\delta$, $\delta-1$, 3 forces $U(v)=M(v)\cup\{\sigma(v)\}$ where $M(v)$ are the two missing neighbours and $\sigma(v)\to v$ is a fixed-point-free permutation (a 2-factor of directed cycles of length $\ge 3$). Then $P(x)$ always contains both missing neighbours of x. So the missing 2-factor has no 3-cycles (else those two plus $\sigma^{-1}(x)$ cannot form a tournament).

This is a finite, rigid obstruction. CP-SAT on the raw Eulerian constraints (no symmetry breaking) says the obstruction is empty for every $\delta$ we have finished:

δ=6 (n=15) is running. Independent Cadical replay of the same claim is in regular_dense_cnf.py.

This is not yet a general theorem. It is a certified finite-δ theorem: every Eulerian oriented graph with n=2δ+3 and δ≤5 has a Seymour vertex. Combined with Brukhman, every Eulerian oriented graph with n≤2δ+3 and δ≤5 is covered. The interesting range is δ≥7 (else Kaneko–Locke), so we still need δ=7 (n=17) or a human proof of the equality case.

2026-08-17 — n=8 types (the dent)

Kaneko–Locke already implies every Eulerian graph with $\delta\le 6$ has a Seymour vertex, so the Eulerian $n=2\delta+3$ SAT for $\delta\le 5$ is only a sanity check of Brukhman's equality layer, not a new bound. Cadical independently confirmed UNSAT for $\delta=2,3,4$ after a top_id bug made an earlier CNF trivially empty. $\delta=6$ OR-Tools timed out. That residue is documented; it does not beat Kaneko–Locke.

The live dent is the first order Halkiewicz left open.

CEGAR SAT, each witness rechecked by seymour.py bitmasks:

The last two feasible rows are irregular missing graphs. The $3^2 2^6$ witness has missing edges

{04,07,14,17,23,25,26,35,36}

i.e. a 4-cycle on $\{0,1,4,7\}$ plus $K_4-e$ on $\{2,3,5,6\}$. Margins (0,-1,0,0,-1,-1,0,0). This is forbidden by Halkiewicz Conjecture 5.1 and by the “regular missing edges” pattern that held for all 4080 labeled Pisa graphs on 7 vertices.

n=8 is also the first order with non-tight Pisa graphs that are not just $K_n$ minus a matching (n=6 already had non-tight matching-minus examples; n=7 had none).

geng -q 8 | enum_pisa_geng finished. 12346 unlabeled undirected graphs, $2.496\cdot 10^9$ orientations of representatives, 162 Pisa orientations, exactly seven missing-degree types:

Absent, and therefore not Pisa at this order: tournaments $0^8$; 4-regular missing; 6-regular missing; incomplete matchings $1^k 0^{8-k}$ for $k<8$. The last is a genuine n=8 phenomenon — n=6 has Pisa orientations of $K_6$ minus one or two edges.

Summary file: certs/pisa_n8_types.json. Every listed type has a bitmask-verified witness.

This is a certified new small-order census. It beats Halkiewicz's n=7 census (first new order) and both of his structural claims (matching conjecture; regular-missing pattern).

2026-08-17 — what is not claimed

• The full labeled n=8 count (that is $3^{28}$ and ~130 core-hours at the n=7 rate). The 162 figure is orientations of nauty representatives, not labeled graphs.
• A general proof of Eulerian $n=2\delta+3$.
• Any improvement of Kaneko–Locke $\delta\le 6$ or Brukhman $n\le 2\delta+2$.
• SSS $\delta=7$ was not rechecked.