×

zbMATH — the first resource for mathematics

On the order of countable graphs. (English) Zbl 1030.03028
Summary: A set of graphs is said to be independent if there is no homomorphism between distinct graphs from the set. We consider the existence problems related to the independent sets of countable graphs. While the maximal size of an independent set of countable graphs is \(2^\omega\) the On Line problem of extending an independent set to a larger independent set is much harder. We prove here that singletons can be extended (“partnership theorem”). While this is the best possible in general, we give structural conditions which guarantee independent extensions of larger independent sets.
This is related to universal graphs, rigid graphs (where we solve a problem posed by the first author and V. Rödl [J. Comb. Theory, Ser. B 46, 133-141 (1989; Zbl 0677.05031)] and to the density problem for countable graphs.

MSC:
03C50 Models with special properties (saturated, rigid, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C15 Coloring of graphs and hypergraphs
03C98 Applications of model theory
06A07 Combinatorics of partially ordered sets
03C64 Model theory of ordered structures; o-minimality
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Cherlin, G.; Shelah, S.; Shi, N., Universal graphs with forbidden subgraphs and algebraic closure, Adv. appl. math., 22, 454-491, (1999) · Zbl 0928.03049
[2] Chvátal, V.; Hell, P.; Kučera, L.; Nešetřil, J., Every finite graph is a full subgraph of a rigid graph, J. combin. theory, 11, 3, 184-286, (1971) · Zbl 0231.05107
[3] Babai, L.; Nešetřil, J., High chromatic rigid graphs II, Ann. discrete math., 15, 55-61, (1982) · Zbl 0502.05052
[4] Ward Henson, C., A family of countable homogeneous graphs, Pacific J. math., 38, 69-83, (1971) · Zbl 0204.24103
[5] Jónsson, B., Universal relational systems, Math. scand., 4, 193-208, (1956) · Zbl 0077.25302
[6] Johnston, J.B., Universal infinite partially orderd sets, Proc. amer. math. soc., 7, 507-514, (1956) · Zbl 0071.05003
[7] Kanamori, A., The higher infinite, ()
[8] Komjáth, P.; Mekler, A.; Pach, J., Some universal graphs, Israel J. math., 64, 158-168, (1998) · Zbl 0672.05074
[9] Komjáth, P.; Pach, J., Universal graphs without large bipartite subgraphs, Mathematika, 31, 282-290, (1984) · Zbl 0551.05057
[10] Nešetřil, J., The homomorphism structure of classes of graphs, Combin. probab. comput., 8, 177-184, (1999) · Zbl 0922.05026
[11] J. Nešetřil, The Coloring Poset and its On-Line Universality, KAM Series, 2000, pp. 2000-2458
[12] J. Nešetřil, Universality and Homomorphism Order (in preparation)
[13] Nešetřil, J., Aspects of structural combinatorics (graph homomorphisms and their use), Taiwanese J. math., 3, 4, 381-424, (1999) · Zbl 0939.05001
[14] Nešetřil, J., A rigid graph for every set, J. graph theory, 39, 2, 108-110, (2002) · Zbl 1002.05068
[15] Nešetřil, J.; Rödl, V., Chromatically optimal rigid graphs, J. combin. theory ser. B, 46, 133-141, (1989) · Zbl 0677.05031
[16] Nešetřil, J.; Tardif, C., Density, (), 229-237 · Zbl 0931.05083
[17] Nešetřil, J.; Tardif, C., Duality theorems for finite structures (characterizing gaps and good characterizations), J. combin. theory ser. B, 80, 80-97, (2000) · Zbl 1024.05078
[18] A. Pultr, V. Trnková, Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories, North-Holland, 1980 · Zbl 0418.18004
[19] Rado, R., Universal graphs and universal functions, Acta arith., 9, 331-340, (1964) · Zbl 0139.17303
[20] Welzl, E., Color families are dense, J. theoret. comput. sci., 17, 29-41, (1982) · Zbl 0482.68063
[21] Vopěnka, P.; Pultr, A.; Hedrlı́n, Z., A rigid relation exists on any set, Comment. math. univ. carolin., 6, 149-155, (1965) · Zbl 0149.01402
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.