A lower bound on the size of homomorphism witnesses
Lax119563.WitnessLowerBound · concepts/Lax119563/WitnessLowerBound.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Theorem. Let be fixed. For every there are some and -vertex colored graphs , distinguished by -WL, such that every colored graph with and satisfies .
By the homomorphism characterization of -WL, such graphs exist. The 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 Lax119563.ColoredHomomorphisms |
| 2 | import Lax119563.WeisfeilerLeman |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: A lower bound on the size of homomorphism witnesses |
| 7 | type: theorem |
| 8 | --- |
| 9 | **Theorem.** Let be fixed. For every there are some |
| 10 | and -vertex colored graphs , distinguished by -WL, such that |
| 11 | every colored graph with and |
| 12 | satisfies . |
| 13 | |
| 14 | By the homomorphism characterization of -WL, such graphs exist. The bound is tight up |
| 15 | to a logarithmic factor in the exponent. |
| 16 | |
| 17 | # Implementation notes |
| 18 | |
| 19 | The constant hidden in is made explicit: there is a , depending on |
| 20 | only, such that every such has at least vertices. |
| 21 | -/ |
| 22 | |
| 23 | open Lax119563.ColoredGraphs Lax119563.WeisfeilerLeman Lax119563.ColoredHomomorphisms |
| 24 | |
| 25 | namespace Lax119563.WitnessLowerBound |
| 26 | |
| 27 | /-- **Witness size lower bound.** For `k ≥ 3` there are arbitrarily large pairs of `n`-vertex |
| 28 | colored graphs which `k`-WL distinguishes, but which are distinguished by the homomorphism |
| 29 | counts of a colored graph of treewidth at most `k` only if it has at least |
| 30 | `2 ^ (n ^ (k - 1) / C)` vertices. -/ |
| 31 | axiom witness_lower_bound (k : ℕ) (hk : 3 ≤ k) : |
| 32 | ∃ C : ℕ, 0 < C ∧ ∀ n₀ : ℕ, ∃ n ≥ n₀, ∃ G₀ G₁ : ColoredGraph, |
| 33 | G₀.n = n ∧ G₁.n = n ∧ Distinguishes k G₀ G₁ ∧ |
| 34 | ∀ F : ColoredGraph, TreewidthAtMost F k → hom F G₀ ≠ hom F G₁ → |
| 35 | 2 ^ (n ^ (k - 1) / C) ≤ F.n |
| 36 | |
| 37 | end Lax119563.WitnessLowerBound |
| 38 |
Implementation notes
The constant hidden in is made explicit: there is a , depending on only, such that every such has at least vertices.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments