On the order of countable graphs

DOI10.1016/S0195-6698(03)00064-7MaRDI QIDQ1404996zbMATH OpenFDO

Authors J. Nešetřil, S. Shelah

Publication date 25 August 2003

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0404319

zbMATH Keywords

DensityPartially ordered setsRigid graphsUniversal graphs

Mathematics Subject Classification ID

Models with special properties (saturated, rigid, etc.) (03C50) Model theory of ordered structures; o-minimality (03C64) Applications of model theory (03C98) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorics of partially ordered sets (06A07)

Abstract: 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 and to the density problem for countable graphs.

Recommendations

• scientific article; zbMATH DE number 887777
• On the number of independent sets in graphs with fixed independence number
• scientific article; zbMATH DE number 3068973
• Arithmetically maximal independent sets in infinite graphs
• Independence and chromatic densities of graphs

Cites work

• A family of countable homogeneous graphs
• A rigid graph for every set
• Aspects of structural combinatorics. (Graph homomorphisms and their use)
• Chromatically optimal rigid graphs
• Color-families are dense
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Every finite graph is a full subgraph of a rigid graph
• High Chromatic Rigid Graphs II
• scientific article; zbMATH DE number 3650785 (Why is no real title available?)
• scientific article; zbMATH DE number 1341918 (Why is no real title available?)
• scientific article; zbMATH DE number 702561 (Why is no real title available?)
• scientific article; zbMATH DE number 3240401 (Why is no real title available?)
• Some universal graphs
• The Homomorphism Structure of Classes of Graphs
• Universal graphs and universal functions
• Universal graphs with forbidden subgraphs and algebraic closure
• Universal graphs without large bipartite subgraphs
• Universal Infinite Partially Ordered Sets
• Universal relational systems

Cited in

(17)

• A surprising permanence of old motivations (a not-so-rigid story)
• There is no universal countable random-free graph
• Increasing paths in countable graphs
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• On nowhere dense graphs
• On the tree-depth of random graphs
• Tree-depth, subgraph coloring and homomorphism bounds
• The countable character of uncountable graphs
• Counting homomorphisms to sparse graphs
• scientific article; zbMATH DE number 850765 (Why is no real title available?)
• scientific article; zbMATH DE number 887777 (Why is no real title available?)
• On treewidth and related parameters of random geometric graphs
• On low rank-width colorings
• Countable \(\alpha\)-extendable graphs
• Strongly \(n\)-e.c. graphs and independent distinguishing labellings
• Linear colouring of binomial random graphs
• On low tree-depth decompositions

This page was built for publication: On the order of countable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1404996)