← 研踪 PaperTrailarXiv:2611.03579 · v1
An Almost-tight Size Lower Bound for Bounded Treewidth Homomorphism-Distinguishability
首次提交 2026-11-03 02:31
版本更新 2026-11-03 02:31
雷达观测 2026-11-04 23:41
摘要
One way to compare two graphs $G_1, G_2$ is to check whether there is some graph $H$ in a graph class $\mathcal{H}$, such that the number of homomorphisms from $H$ to $G_1$ is not equal to that from $H$ to $G_2$. 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 $\mathcal{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_1$ and $G_2$ can be distinguished by a homomorphism count from a graph of treewidth $k$ iff $G_1$ and $G_2$ 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 \emph{size} of $H$ is limited. We show a $2^{Ω(n^{k/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^{k+1})}$ upper bound and is an exponential improvement on the previous best known lower bound.
作者备注：66 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-03 02:31 · 最新观测版本
An Almost-tight Size Lower Bound for Bounded Treewidth Homomorphism-Distinguishability
One way to compare two graphs $G_1, G_2$ is to check whether there is some graph $H$ in a graph class $\mathcal{H}$, such that the number of homomorphisms from $H$ to $G_1$ is not equal to that from $H$ to $G_2$. 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 $\mathcal{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_1$ and $G_2$ can be distinguished by a homomorphism count from a graph of treewidth $k$ iff $G_1$ and $G_2$ 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 \emph{size} of $H$ is limited. We show a $2^{Ω(n^{k/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^{k+1})}$ upper bound and is an exponential improvement on the previous best known lower bound.
查看此版本解读 →查看此版本原文 ↗