zbMATH — the first resource for mathematics

Duality theorems for finite structures (characterising gaps and good characterisations). (English) Zbl 1024.05078
Summary: We provide a correspondence between the subjects of duality and density in classes of finite relational structures. The purpose of duality is to characterise the structures \(C\) that do not admit a homomorphism into a given target \(B\) by the existence of a homomorphism from a structure \(A\) into \(C\). Density is the order-theoretic property of containing no covers (or “gaps”). We show that the covers in the skeleton of a category of finite relational models correspond naturally to certain instances of duality statements, and we characterise these covers.

05C75 Structural characterization of families of graphs
08A02 Relational systems, laws of composition
68R05 Combinatorics in computer science
Full Text: DOI
[1] Duffus, D.; Sauer, N., Lattices arising in categorical investigations of Hedetniemi’s conjecture, Discrete math., 152, 125-139, (1996) · Zbl 0853.06006
[2] Edmonds, J., Paths, trees and flowers, Canad. J. math., 17, 449-467, (1965) · Zbl 0132.20903
[3] Frucht, R., Herstellung von graphen mit vorgegebener abstrakter gruppe, Compositio math., 6, 239-250, (1938) · JFM 64.0596.02
[4] Hedrlı́n, Z.; Pultr, A., Symmetric relations (undirected graphs) with given semigroups, Monatsh. math., 69, 318-322, (1965) · Zbl 0139.24803
[5] Hell, P.; Nešetřil, J., On the complexity of H-coloring, J. combin. theory ser. B, 49, 92-110, (1990) · Zbl 0639.05023
[6] Hell, P.; Nešetřil, J.; Zhu, X., Duality and polynomial testing of tree homomorphisms, Trans. amer. math. soc., 348, 1281-1297, (348) · Zbl 0877.05055
[7] Hochstätter, W.; Nešetřil, J., Comment. math. univ. carolin., 40, 557-592, (1999)
[8] Komárek, P., Good characterizations of graphs, (1988), Charles University Prague
[9] Lovász, L., Operations with structures, Acta math. acad. sci. hungar, 321-328, (1967) · Zbl 0174.01401
[10] Nešetřil, J., Structure of graph homomorphisms, J. combin. probab. comput., 8, 177-184, (1999) · Zbl 0922.05026
[11] Nešetřil, J.; Pultr, A., On classes of relations and graphs determined by subobjects and factorobjects, Discrete math., 22, 287-300, (1978) · Zbl 0388.05039
[12] J. Nešetřil, and, C. Tardif, Density via duality, preprint, 1998.
[13] J. Nešetřil, and, C. Tardif, A new proof of the density of directed and undirected graphs, preprint, 1998.
[14] Nešetřil, J.; Zhu, X., Path homomorphisms, Math. proc. Cambridge philos. soc., 120, 207-220, (1996) · Zbl 0857.05057
[15] Pultr, A.; Trnková, V., Combinatorial, algebraical and topological structures, (1980), North-Holland Amsterdam
[16] Tardif, C., Fractional multiples of graphs and the density of vertex-transitive graphs, J. algebraic combin., 10, 61-68, (1999) · Zbl 0931.05035
[17] Welzl, E., Color-families are dense, J. theoret. comput. sci., 17, 29-41, (1982) · Zbl 0482.68063
[18] Welzl, E., Symmetric graphs and interpretations, J. combin. theory ser. B, 37, 235-244, (1984) · Zbl 0547.05058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.