While this submission is a draft, it cannot be used by other submissions.

An upper bound on the size of homomorphism witnesses for uncolored graphs

Lax119563.UncoloredWitnessUpperBound · concepts/Lax119563/UncoloredWitnessUpperBound.lean · lax-119563

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Corollary

    Corollary. Let k≥2k \geq 2, and let G,HG, H be graphs with at most nn vertices each that are not homomorphism indistinguishable over the class Tk\mathcal T_k of graphs of treewidth at most kk. Then some graph F∈TkF \in \mathcal T_k with hom⁡(F,G)≠hom⁡(F,H)\hom(F, G) \neq \hom(F, H) satisfies ∣V(F)∣≤2Ok(nk−1log⁡n)|V(F)| \leq 2^{O_k(n^{k-1} \log n)}.

    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
    7 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Lean source view on GitHub

    1import Mathlib.Data.Nat.Log
    2import Lax871432.HomomorphismIndistinguishability
    3import Lax119563.TreewidthClasses
    4
    5/-!
    6---
    7title: An upper bound on the size of homomorphism witnesses for uncolored graphs
    8type: corollary
    9---
    10**Corollary.** Let k≥2k \geq 2, and let G,HG, H be graphs with at most nn vertices each that
    11are not homomorphism indistinguishable over the class Tk\mathcal T_k of graphs of treewidth at
    12most kk. Then some graph F∈TkF \in \mathcal T_k with hom⁡(F,G)≠hom⁡(F,H)\hom(F, G) \neq \hom(F, H) satisfies
    13∣V(F)∣≤2Ok(nk−1log⁡n)|V(F)| \leq 2^{O_k(n^{k-1} \log n)}.
    14
    15This is the witness size upper bound for colored graphs, applied to graphs all of whose
    16vertices have the same color, and phrased in terms of homomorphism indistinguishability.
    17
    18# Implementation notes
    19
    20Homomorphism counts and homomorphism indistinguishability G≡FHG \equiv_{\mathcal F} H are those
    21of `Lax871432`. As there, witnesses are graphs on vertex sets {0,…,m−1}\{0, \dots, m - 1\}. On graphs
    22all 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
    25constant hidden in OkO_k is made explicit as in the colored statement.
    26-/
    27
    28open Lax871432.HomomorphismCounts Lax871432.HomomorphismIndistinguishability
    29 Lax119563.TreewidthClasses
    30
    31namespace Lax119563.UncoloredWitnessUpperBound
    32
    33/-- **Witness size upper bound for uncolored graphs.** If graphs `G` and `H` with at most `n`
    34vertices 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)`
    36vertices has different numbers of homomorphisms to `G` and to `H`. -/
    37axiom 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
    44end Lax119563.UncoloredWitnessUpperBound
    45
    Show Proof

    Implementation notes

    Homomorphism counts and homomorphism indistinguishability G≡FHG \equiv_{\mathcal F} H are those of Lax871432Lax871432. As there, witnesses are graphs on vertex sets {0,…,m−1}\{0, \dots, m - 1\}. On graphs all of whose vertices have the same color, these homomorphism counts and the class Lax119563.TreewidthClasses.treewidthClassLax119563.TreewidthClasses.treewidthClass agree with the colored notions of Lax119563.ColoredHomomorphismsLax119563.ColoredHomomorphisms. The constant hidden in OkO_k is made explicit as in the colored statement.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…