e-space
Manchester Metropolitan University's Research Repository

    Generalised dualities and maximal finite antichains in the homomorphism order of relational structures

    Foniok, J, Nesetril, J and Tardif, C (2008) Generalised dualities and maximal finite antichains in the homomorphism order of relational structures. European Journal of Combinatorics, 29. ISSN 0195-6698

    [img]
    Preview

    Available under License Creative Commons Attribution Non-commercial No Derivatives.

    Download (207kB) | Preview

    Abstract

    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. Nešetřil, 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 homomorphisms 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.

    Impact and Reach

    Statistics

    Activity Overview
    6 month trend
    232Downloads
    6 month trend
    275Hits

    Additional statistics for this dataset are available via IRStats2.

    Altmetric

    Repository staff only

    Edit record Edit record