An upper bound on the size of homomorphism witnesses
Lax119563.WitnessUpperBound · concepts/Lax119563/WitnessUpperBound.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Corollary
Corollary. Let , and let be colored graphs with at most vertices each that are distinguished by -WL. Then some colored graph with and satisfies .
Together with the witness size lower bound, this shows that the lower bound is tight up to a logarithmic factor in the exponent.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Mathlib.Data.Nat.Log |
| 2 | import Lax119563.ColoredHomomorphisms |
| 3 | import Lax119563.WeisfeilerLeman |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: An upper bound on the size of homomorphism witnesses |
| 8 | type: corollary |
| 9 | --- |
| 10 | **Corollary.** Let , and let be colored graphs with at most vertices |
| 11 | each that are distinguished by -WL. Then some colored graph with |
| 12 | and satisfies |
| 13 | . |
| 14 | |
| 15 | Together with the witness size lower bound, this shows that the lower bound is tight up to a |
| 16 | logarithmic factor in the exponent. |
| 17 | |
| 18 | # Implementation notes |
| 19 | |
| 20 | The constant hidden in is made explicit: there is a , depending on only, such |
| 21 | that for all a witness with at most |
| 22 | vertices exists. |
| 23 | -/ |
| 24 | |
| 25 | open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman Lax119563.ColoredHomomorphisms |
| 26 | |
| 27 | namespace Lax119563.WitnessUpperBound |
| 28 | |
| 29 | /-- **Witness size upper bound.** If `k`-WL distinguishes colored graphs `G` and `H` with at |
| 30 | most `n` vertices each, then so do the homomorphism counts of a colored graph of treewidth at |
| 31 | most `k` with at most `2 ^ (C n ^ (k - 1) log₂ n)` vertices. -/ |
| 32 | axiom witness_upper_bound (k : ℕ) (hk : 2 ≤ k) : |
| 33 | ∃ C : ℕ, ∀ n : ℕ, 2 ≤ n → ∀ G H : ColoredGraph, G.n ≤ n → H.n ≤ n → |
| 34 | Distinguishes k G H → |
| 35 | ∃ F : ColoredGraph, TreewidthAtMost F k ∧ hom F G ≠ hom F H ∧ |
| 36 | F.n ≤ 2 ^ (C * n ^ (k - 1) * Nat.log 2 n) |
| 37 | |
| 38 | end Lax119563.WitnessUpperBound |
| 39 |
Implementation notes
The constant hidden in is made explicit: there is a , depending on only, such that for all a witness with at most vertices exists.
Used by
none
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments