Antichains in the homomorphism order of graphs

Dwight Duffus; Peter, L. Erdös; Jaroslav Nešetřil; Lajos Soukup

Commentationes Mathematicae Universitatis Carolinae (2007)

  • Volume: 48, Issue: 4, page 571-583
  • ISSN: 0010-2628

Abstract

top
Let 𝔾 and 𝔻 , respectively, denote the partially ordered sets of homomorphism classes of finite undirected and directed graphs, respectively, both ordered by the homomorphism relation. Order theoretic properties of both have been studied extensively, and have interesting connections to familiar graph properties and parameters. In particular, the notion of a duality is closely related to the idea of splitting a maximal antichain. We construct both splitting and non-splitting infinite maximal antichains in 𝔾 and in 𝔻 . The splitting maximal antichains give infinite versions of dualities for graphs and for directed graphs.

How to cite

top

Duffus, Dwight, et al. "Antichains in the homomorphism order of graphs." Commentationes Mathematicae Universitatis Carolinae 48.4 (2007): 571-583. <http://eudml.org/doc/250192>.

@article{Duffus2007,
abstract = {Let $\mathbb \{G\}$ and $\mathbb \{D\}$, respectively, denote the partially ordered sets of homomorphism classes of finite undirected and directed graphs, respectively, both ordered by the homomorphism relation. Order theoretic properties of both have been studied extensively, and have interesting connections to familiar graph properties and parameters. In particular, the notion of a duality is closely related to the idea of splitting a maximal antichain. We construct both splitting and non-splitting infinite maximal antichains in $\mathbb \{G\}$ and in $\mathbb \{D\}$. The splitting maximal antichains give infinite versions of dualities for graphs and for directed graphs.},
author = {Duffus, Dwight, Erdös, Peter, L., Nešetřil, Jaroslav, Soukup, Lajos},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {partially ordered set; homomorphism order; duality; antichain; splitting property; partially ordered set; homomorphism order; duality; antichain; splitting property},
language = {eng},
number = {4},
pages = {571-583},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Antichains in the homomorphism order of graphs},
url = {http://eudml.org/doc/250192},
volume = {48},
year = {2007},
}

TY - JOUR
AU - Duffus, Dwight
AU - Erdös, Peter, L.
AU - Nešetřil, Jaroslav
AU - Soukup, Lajos
TI - Antichains in the homomorphism order of graphs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2007
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 48
IS - 4
SP - 571
EP - 583
AB - Let $\mathbb {G}$ and $\mathbb {D}$, respectively, denote the partially ordered sets of homomorphism classes of finite undirected and directed graphs, respectively, both ordered by the homomorphism relation. Order theoretic properties of both have been studied extensively, and have interesting connections to familiar graph properties and parameters. In particular, the notion of a duality is closely related to the idea of splitting a maximal antichain. We construct both splitting and non-splitting infinite maximal antichains in $\mathbb {G}$ and in $\mathbb {D}$. The splitting maximal antichains give infinite versions of dualities for graphs and for directed graphs.
LA - eng
KW - partially ordered set; homomorphism order; duality; antichain; splitting property; partially ordered set; homomorphism order; duality; antichain; splitting property
UR - http://eudml.org/doc/250192
ER -

References

top
  1. Ahlswede R., Erdös P.L., Graham N., A splitting property of maximal antichains, Combinatorica 15 (1995), 475-480. (1995) MR1364020
  2. Duffus D., Sands B., Minimum sized fibres in distributive lattices, J. Austral. Math. Soc. 70 (2001), 337-350. (2001) Zbl1019.06002MR1829963
  3. Duffus D., Sands B., Splitting numbers of grids, Electron. J. Combin. 12 (2005), #R17. (2005) Zbl1060.06005MR2134180
  4. Džamonja M., A note on the splitting property in strongly dense posets of size ℵ 0 , Rad. Mat. 8 (1992/98), 321-326. (1992/98) MR1690735
  5. Erdös P., Graph theory and probability, Canad. J. Math. 11 (1959), 34-38. (1959) MR0102081
  6. Erdös P., Hajnal A., On chromatic number of graphs and set systems, Acta Math. Hungar. 17 (1966), 61-99. (1966) MR0193025
  7. Erdös P., Rényi A., On random graphs I, Publ. Math. Debrecen 6 (1959), 290-297. (1959) MR0120167
  8. Erdös P.L., Splitting property in infinite posets, Discrete Math. 163 (1997), 251-256. (1997) MR1428578
  9. Erdös P.L., Soukup L., How to split antichains in infinite posets, Combinatorica 27 2 (2007), 147-161. (2007) Zbl1136.06002MR2321920
  10. Foniok J., Nešetřil J., Tardif C., Generalized dualities and maximal finite antichains in the homomorphism order of relational structures, to appear in European J. Combin.; extended abstract in Lecture Notes in Comput. Sci. 4271, Springer, Berlin, 2006, pp.27-36. MR2408365
  11. Hell P., Nešetřil J., Graphs and Homomorphisms, Oxford University Press, Oxford, 2004. MR2089014
  12. Nešetřil J., Sparse incomparability for relational structures, in preparation. 
  13. Nešetřil J., Ossona de Mendez P., Cuts and bounds, Discrete Math. 302 1-3 (2005), 211-224. (2005) MR2179644
  14. Nešetřil J., Pultr A., On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math. 22 (1978), 287-300. (1978) MR0522724
  15. Nešetřil J., V. Rödl V., Chromatically optimal rigid graphs, J. Combin. Theory Ser. (B) 46 (1989), 133-141. (1989) MR0992987
  16. Nešetřil J., Tardif C., Duality theorems for finite structures (characterising gaps and good characterisations), J. Combin. Theory Ser. (B) 80 (2000), 80-97. (2000) Zbl1024.05078MR1778201
  17. Nešetřil J., Tardif C., On maximal finite antichains in the homomorphism order of directed graphs, Discuss. Math. Graph Theory 23 (2003), 325-332. (2003) Zbl1057.05036MR2070160
  18. Nešetřil J., Zhu X., On sparse graphs with given colorings and homomorphisms, J. Combin. Theory Ser. (B) 90 (2004), 161-172. (2004) Zbl1033.05044MR2041324
  19. Pultr A., Trnková V., Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories, North-Holland, Amsterdam, 1980. MR0563525
  20. Welzl E., Color families are dense, Theoret. Comput. Sci. 17 (1982), 29-41. (1982) Zbl0482.68063MR0644791

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.