Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
复制标题
DOI：
10.1016/j.ejc.2007.11.017
复制
发表时间：
2008-05-01
影响因子：
1
通讯作者：
Tardif, Claude
中科院分区：
文献类型：
--
作者：
Foniok, Jan;Nesetril, Jaroslav;Tardif, Claude
本文的动机有三个方面。首先，我们研究了有向图的同态序的连通性，更一般地，对于关系结构。与无向图的同态序（没有非平凡的有限极大反链）相反，有向图的序有任意大小的有限极大反链。本文明确地给出了有向图的同态序中的所有极大反链，令人惊奇的是，这些极大反链对应于广义对偶。广义对偶的概念在这里被定义为有限对偶概念的扩展，在[J. Nesetril，C。Tardif，有限结构的对偶定理（特征间隙和良好特征），J. Combin。理论系列B 80（1）（2000）80-97]。在引用的论文的结果的基础上，我们充分证明了广义对偶性。看来这些对偶性是由禁止来自有限的森林集合（而不是树）的同态决定的。Atserias，关于有向图着色问题和树宽对偶，在：第21届IEEE计算机科学逻辑研讨会论文集，LICS'06，IEEE计算机协会，2006; B。拉罗斯角洛滕角Tardif，一阶约束满足问题的表征，在：第21届IEEE计算机科学逻辑研讨会论文集，LICS'06，IEEE计算机协会，2006; V. Dalmau，A. Krokhin，B. Larose，First-order definable retraction problems for posets and reflexive graphs，in：Proceedings of the 19 th IEEE Symposium on Logic in Computer Science，LICS'04，IEEE Computer Society，2004 [5]]我们将讨论一阶可定义的“广义”约束满足问题（这里也定义）。这些又仅仅是对应于同态序中的有限极大反链的广义对偶。(c)2007爱思唯尔有限公司版权所有。
The motivation for this paper is threefold. First, we study the connectivity properties of the homomorphism order of directed graphs, and more generally for relational structures. As opposed to the homomorphism order of undirected graphs (which has no non-trivial finite maximal antichains), the order of directed graphs has finite maximal antichains of any size. In this paper, we characterise explicitly all maximal antichains in the homomorphism order of directed graphs.Quite surprisingly, these maximal antichains correspond to generalised dualities. The notion of generalised duality is defined here in full generality as an extension of the notion of finitary duality, investigated in [J. Nesetril, C. Tardif, Duality theorems for finite structures (characterising gaps and good characterisations), J. Combin. Theory Ser. B 80 (1) (2000) 80-97]. Building Upon the results of the cited paper, we fully characterise the generalised dualities. It appears that these dualities are determined by forbidding homomorphism from a finite set of forests (rather than trees).Finally, in the spirit of [A. Atserias, On digraph coloring problems and treewidth duality, in: Proceedings of the 21st IEEE Symposium on Logic in Computer Science, LICS'06, IEEE Computer Society, 2006; B. Larose, C. Loten, C. Tardif, A characterisation of first-order constraint satisfaction problems, in: Proceedings of the 21st IEEE Symposium on Logic in Computer Science, LICS'06, IEEE Computer Society, 2006; V. Dalmau, A. Krokhin, B. Larose, First-order definable retraction problems for posets and reflexive graphs, in: Proceedings of the 19th IEEE Symposium on Logic in Computer Science, LICS'04, IEEE Computer Society, 2004 [5]] we shall characterise "generalised" constraint satisfaction problems (defined also here) that are first-order definable. These are again just generalised dualities corresponding to finite maximal antichains in the homomorphism order. (c) 2007 Elsevier Ltd. All rights reserved.