Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
Jaroslav Nešetřil, Claude Tardif · SIAM Journal on Discrete Mathematics · 2005
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.