Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
复制标题
对指数长问题的简短回答：同态对偶的极值方面
DOI：
10.1137/s0895480104445630
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Claude Tardif
中科院分区：
文献类型：
--
作者：
J. Nesetril;Claude Tardif
证明了存在一个常数$k$，使得对于每个$n\geq 1$，存在一个至少有$2^n$个顶点的有向核图$H_n$，使得一个有向图$G$是$H_n$可染的当且仅当每个至多有$kn\log(N)$个顶点的$G$的子图是$H_n$可染的.我们的例子表明，一般而言，关系结构的对偶在[J.Nesetril和C.Tardif，J.Combin的意义上]。理论系列。B，80(2000)，第80-97页]可以有超多项式的大小。本文给出的构造给出了这种构造的一个双指数上界。在这里，我们将其改进为指数上界。
We prove that there exists a constant $k$ such that for every $n \geq 1$ there exists a directed core graph $H_n$ with at least $2^n$ vertices such that a directed graph $G$ is $H_n$-colorable if and only if every subgraph of $G$ with at most $kn\log(n)$ vertices is $H_n$-colorable. Our examples show that in general the "duals of relational structures" in the sense of [J. Nesetril and C. Tardif, J. Combin. Theory Ser. B, 80 (2000), pp. 80-97] can have superpolynomial size. The construction given in this paper gives a double exponential upper bound for such a construction. Here we improve this to an exponential upper bound.