# 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
##### Keywords:
Density; Partially ordered sets; Rigid graphs; Universal graphs
Full Text:
##### References:
  Cherlin, G.; Shelah, S.; Shi, N., Universal graphs with forbidden subgraphs and algebraic closure, Adv. appl. math., 22, 454-491, (1999) · Zbl 0928.03049  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  Babai, L.; Nešetřil, J., High chromatic rigid graphs II, Ann. discrete math., 15, 55-61, (1982) · Zbl 0502.05052  Ward Henson, C., A family of countable homogeneous graphs, Pacific J. math., 38, 69-83, (1971) · Zbl 0204.24103  Jónsson, B., Universal relational systems, Math. scand., 4, 193-208, (1956) · Zbl 0077.25302  Johnston, J.B., Universal infinite partially orderd sets, Proc. amer. math. soc., 7, 507-514, (1956) · Zbl 0071.05003  Kanamori, A., The higher infinite, ()  Komjáth, P.; Mekler, A.; Pach, J., Some universal graphs, Israel J. math., 64, 158-168, (1998) · Zbl 0672.05074  Komjáth, P.; Pach, J., Universal graphs without large bipartite subgraphs, Mathematika, 31, 282-290, (1984) · Zbl 0551.05057  Nešetřil, J., The homomorphism structure of classes of graphs, Combin. probab. comput., 8, 177-184, (1999) · Zbl 0922.05026  J. Nešetřil, The Coloring Poset and its On-Line Universality, KAM Series, 2000, pp. 2000-2458  J. Nešetřil, Universality and Homomorphism Order (in preparation)  Nešetřil, J., Aspects of structural combinatorics (graph homomorphisms and their use), Taiwanese J. math., 3, 4, 381-424, (1999) · Zbl 0939.05001  Nešetřil, J., A rigid graph for every set, J. graph theory, 39, 2, 108-110, (2002) · Zbl 1002.05068  Nešetřil, J.; Rödl, V., Chromatically optimal rigid graphs, J. combin. theory ser. B, 46, 133-141, (1989) · Zbl 0677.05031  Nešetřil, J.; Tardif, C., Density, (), 229-237 · Zbl 0931.05083  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  A. Pultr, V. Trnková, Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories, North-Holland, 1980 · Zbl 0418.18004  Rado, R., Universal graphs and universal functions, Acta arith., 9, 331-340, (1964) · Zbl 0139.17303  Welzl, E., Color families are dense, J. theoret. comput. sci., 17, 29-41, (1982) · Zbl 0482.68063  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.