Answers are grounded in this paper and cite their sources.
One way to compare two graphs G₁, G₂ is to check whether there is some graph H in a graph class H, such that the number of homomorphisms from H to G₁ is not equal to that from H to G₂. This is the field of homomorphism distinguishability which has gained a lot of traction in recent years. In this paper, we study the case where H is the class of graphs of treewidth k. This has connections to important concepts in logic, machine learning, combinatorial optimization and proof complexity. In particular, Dvořák showed that G₁ and G₂ can be distinguished by a homomorphism count from a graph of treewidth k iff G₁ and G₂ are distinguishable by the k-dimensional Weisfeiler-Leman algorithm. While the relation between the iteration number of this algorithm and the depth of the tree-decomposition of a distinguishing graph is understood, our understanding of the size of H is limited. We show a 2^Ω(nk/2) lower bound on the size of a graph of treewidth k required to distinguish two graphs of order n. This bound is proved via a new combinatorial game along with a construction which uses a recent compression technique for CFI graphs. It is almost tight to the known 2^O(nᵏ⁺¹) upper bound and is an exponential improvement on the previous best known lower bound.
No takes yet. Share an insight, caveat, or question.
Lichter et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: