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.
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 there are a round bound and a batch bound , depending only on the class and , with which Splitter wins the -game on every member.
Proof strategy
Take the quasi-wideness margins of the class at radius from the endorsed and put and . Splitter's strategy isolates, in each round, Connector's new vertex together with the still-active vertices of a chosen walk of length at most from every earlier Connector vertex to , taken in the arena that earlier round was played in — one vertex plus one path of at most vertices per round played, which is the bound . A play in which every Connector move still had an incident edge is recorded by ; 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 of at most vertices and a distance- independent set of at least of them. Pairing the rounds that selected a vertex of off chronologically gives 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 walks are pairwise disjoint and one of them avoids ; rebuilding it inside gives a walk of length at most between two distinct members of , contradicting the independence.
The round bound is , not the notes' : their own proof needs pairwise disjoint paths so that one avoids the separator, which is selected rounds. See the module docstring.