The pebble game characterization of Weisfeiler–Leman
Lax119563.GameCharacterization · concepts/Lax119563/GameCharacterization.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Cai, Fürer and Immerman, Immerman and Lander, and Hella: let , let be colored graphs, and let .
- If Spoiler wins within rounds, then -WL distinguishes and after at most rounds.
- If -WL distinguishes and after rounds, then Spoiler wins within rounds.
In particular, Duplicator wins if and only if -WL does not distinguish and .
Concept map
Evidence
This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.
1 distinguishesAfter_of_spoilerWinsWithin proven
2 duplicatorWins_iff proven
3 spoilerWinsWithin_of_distinguishesAfter proven
Lean source view on GitHub
| 1 | import Lax119563.WeisfeilerLeman |
| 2 | import Lax119563.PebbleGame |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: The pebble game characterization of Weisfeiler–Leman |
| 7 | type: theorem |
| 8 | --- |
| 9 | Cai, Fürer and Immerman, Immerman and Lander, and Hella: let , let be |
| 10 | colored graphs, and let . |
| 11 | |
| 12 | 1. If Spoiler wins within rounds, then -WL distinguishes |
| 13 | and after at most rounds. |
| 14 | 2. If -WL distinguishes and after rounds, then Spoiler wins |
| 15 | within rounds. |
| 16 | |
| 17 | In particular, Duplicator wins if and only if -WL does not |
| 18 | distinguish and . |
| 19 | -/ |
| 20 | |
| 21 | open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman Lax119563.PebbleGame |
| 22 | |
| 23 | namespace Lax119563.GameCharacterization |
| 24 | |
| 25 | /-- A win of Spoiler within `r` rounds of `BP_{k+1}(G, H)` yields a distinction by `k`-WL |
| 26 | after at most `r` rounds. -/ |
| 27 | axiom distinguishesAfter_of_spoilerWinsWithin {k : ℕ} (hk : 2 ≤ k) {G H : ColoredGraph} |
| 28 | {r : ℕ} (h : SpoilerWinsWithin (k + 1) r G H) : |
| 29 | ∃ r' ≤ r, DistinguishesAfter k r' G H |
| 30 | |
| 31 | /-- A distinction by `k`-WL after `r` rounds yields a win of Spoiler within `r + k` rounds |
| 32 | of `BP_{k+1}(G, H)`. -/ |
| 33 | axiom spoilerWinsWithin_of_distinguishesAfter {k : ℕ} (hk : 2 ≤ k) {G H : ColoredGraph} |
| 34 | {r : ℕ} (h : DistinguishesAfter k r G H) : |
| 35 | SpoilerWinsWithin (k + 1) (r + k) G H |
| 36 | |
| 37 | /-- Duplicator wins `BP_{k+1}(G, H)` if and only if `k`-WL does not distinguish `G` and `H`. -/ |
| 38 | axiom duplicatorWins_iff {k : ℕ} (hk : 2 ≤ k) (G H : ColoredGraph) : |
| 39 | DuplicatorWins (k + 1) G H ↔ ¬ Distinguishes k G H |
| 40 | |
| 41 | end Lax119563.GameCharacterization |
| 42 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments