An upper bound on the size of homomorphism witnesses for uncolored graphs
Lax119563.UncoloredWitnessUpperBound · concepts/Lax119563/UncoloredWitnessUpperBound.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Corollary
Corollary. Let , and let be graphs with at most vertices each that are not homomorphism indistinguishable over the class of graphs of treewidth at most . Then some graph with satisfies .
This is the witness size upper bound for colored graphs, applied to graphs all of whose vertices have the same color, and phrased in terms of homomorphism indistinguishability.
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 Lax871432.HomomorphismIndistinguishability |
| 3 | import Lax119563.TreewidthClasses |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: An upper bound on the size of homomorphism witnesses for uncolored graphs |
| 8 | type: corollary |
| 9 | --- |
| 10 | **Corollary.** Let , and let be graphs with at most vertices each that |
| 11 | are not homomorphism indistinguishable over the class of graphs of treewidth at |
| 12 | most . Then some graph with satisfies |
| 13 | . |
| 14 | |
| 15 | This is the witness size upper bound for colored graphs, applied to graphs all of whose |
| 16 | vertices have the same color, and phrased in terms of homomorphism indistinguishability. |
| 17 | |
| 18 | # Implementation notes |
| 19 | |
| 20 | Homomorphism counts and homomorphism indistinguishability are those |
| 21 | of `Lax871432`. As there, witnesses are graphs on vertex sets . On graphs |
| 22 | all of whose vertices have the same color, these homomorphism counts and the class |
| 23 | `Lax119563.TreewidthClasses.treewidthClass` agree with the colored notions of |
| 24 | `Lax119563.ColoredHomomorphisms`. The |
| 25 | constant hidden in is made explicit as in the colored statement. |
| 26 | -/ |
| 27 | |
| 28 | open Lax871432.HomomorphismCounts Lax871432.HomomorphismIndistinguishability |
| 29 | Lax119563.TreewidthClasses |
| 30 | |
| 31 | namespace Lax119563.UncoloredWitnessUpperBound |
| 32 | |
| 33 | /-- **Witness size upper bound for uncolored graphs.** If graphs `G` and `H` with at most `n` |
| 34 | vertices each are not homomorphism indistinguishable over the graphs of treewidth at most |
| 35 | `k`, then some graph of treewidth at most `k` with at most `2 ^ (C n ^ (k - 1) log₂ n)` |
| 36 | vertices has different numbers of homomorphisms to `G` and to `H`. -/ |
| 37 | axiom uncolored_witness_upper_bound (k : ℕ) (hk : 2 ≤ k) : |
| 38 | ∃ C : ℕ, ∀ n : ℕ, 2 ≤ n → |
| 39 | ∀ {V W : Type} [Fintype V] [Fintype W] (G : SimpleGraph V) (H : SimpleGraph W), |
| 40 | Fintype.card V ≤ n → Fintype.card W ≤ n → ¬ (G ≡[treewidthClass k] H) → |
| 41 | ∃ (m : ℕ) (F : SimpleGraph (Fin m)), (treewidthClass k).Mem F ∧ |
| 42 | homCount F G ≠ homCount F H ∧ m ≤ 2 ^ (C * n ^ (k - 1) * Nat.log 2 n) |
| 43 | |
| 44 | end Lax119563.UncoloredWitnessUpperBound |
| 45 |
Implementation notes
Homomorphism counts and homomorphism indistinguishability are those of . As there, witnesses are graphs on vertex sets . On graphs all of whose vertices have the same color, these homomorphism counts and the class agree with the colored notions of . The constant hidden in is made explicit as in the colored statement.
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