Draft — mutable and not usable as a dependency; its citation marks the draft state.

Proof of `Splitter wins on nowhere dense classes`

groundedproofs/Lax3Proofs/SplitterWin.lean · lax-3

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Splitter wins on nowhere dense classes (Lemma 4.2 of Chapter 4 of the source lecture notes, Theorem 4.2 of Grohe–Kreutzer–Siebertz, in the isolation variant): on a nowhere dense class, for every radius rr there are a round bound and a batch bound mm, depending only on the class and rr, with which Splitter wins the (,m,r)(ℓ, m, r)-game on every member.

Proof strategy

Take the quasi-wideness margins N,sN, s of the class at radius rr from the endorsed Lax12.NowhereDenseUQW.uniformlyQuasiWideofnowhereDenseLax12.NowhereDenseUQW.uniformlyQuasiWide_of_nowhereDense and put :=N(2s+2)ℓ := N (2·s + 2) and m:=(r+1)m := ℓ · (r + 1). Splitter's strategy isolates, in each round, Connector's new vertex vv together with the still-active vertices of a chosen walk of length at most rr from every earlier Connector vertex to vv, taken in the arena that earlier round was played in — one vertex plus one path of at most r+1r + 1 vertices per round played, which is the bound mm. A play in which every Connector move still had an incident edge is recorded by ReachedReached; moves on isolated vertices end the play at once, since the ball around such a vertex is the vertex alone.

The whole content is that no play lasts rounds. Connector's vertices are then distinct vertices, so quasi-wideness returns a separator SS of at most ss vertices and a distance-rr independent set BB of at least 2s+22·s + 2 of them. Pairing the rounds that selected a vertex of BB off chronologically gives s+1s + 1 pairs, and for each the strategy's maintained walk between the pair's two vertices, in the older round's arena. Two ingredients replace the notes' "removed vertices are gone". Isolation is permanent: arenas only lose edges, so a vertex the strategy isolated in some round has no incident edge in any later arena. Distinct pairs' walks are disjoint: a vertex of an older pair's walk was isolated when that pair's newer round was played, while every vertex of a newer pair's walk carries an edge in an arena from strictly after that round. So the s+1s + 1 walks are pairwise disjoint and one of them avoids SS; rebuilding it inside deleteVertsGSdeleteVerts G S gives a walk of length at most rr between two distinct members of BB, contradicting the independence.

The round bound is N(2s+2)N (2·s + 2), not the notes' N(2s+1)N (2·s + 1): their own proof needs s+1s + 1 pairwise disjoint paths so that one avoids the separator, which is 2s+22·s + 2 selected rounds. See the module docstring.