Homomorphism witnesses from rounds
Lax119563.WitnessFromRounds · concepts/Lax119563/WitnessFromRounds.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Theorem. Let and , and let be colored graphs. If -WL distinguishes and after rounds, then some colored graph with and
satisfies .
Concept map
Lean source view on GitHub
| 1 | import Lax119563.ColoredHomomorphisms |
| 2 | import Lax119563.WeisfeilerLeman |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Homomorphism witnesses from rounds |
| 7 | type: theorem |
| 8 | --- |
| 9 | **Theorem.** Let and , and let be colored graphs. If -WL |
| 10 | distinguishes and after rounds, then some colored graph with |
| 11 | and |
| 12 | |
| 13 | satisfies . |
| 14 | -/ |
| 15 | |
| 16 | open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman Lax119563.ColoredHomomorphisms |
| 17 | |
| 18 | namespace Lax119563.WitnessFromRounds |
| 19 | |
| 20 | /-- A distinction by `k`-WL after `r` rounds is witnessed by the homomorphism counts of a |
| 21 | colored graph of treewidth at most `k` with at most `k (k M) ^ r` vertices, where |
| 22 | `M = |V(G)| ^ k + |V(H)| ^ k`. -/ |
| 23 | axiom witness_from_rounds {k : ℕ} (hk : 2 ≤ k) {r : ℕ} {G H : ColoredGraph} |
| 24 | (h : DistinguishesAfter k r G H) : |
| 25 | ∃ F : ColoredGraph, TreewidthAtMost F k ∧ |
| 26 | F.n ≤ k * (k * (G.n ^ k + H.n ^ k)) ^ r ∧ hom F G ≠ hom F H |
| 27 | |
| 28 | end Lax119563.WitnessFromRounds |
| 29 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments