| Title:
|
Antichains in the homomorphism order of graphs (English) |
| Author:
|
Duffus, D. |
| Author:
|
Erdös, P. L. |
| Author:
|
Nešetřil, J. |
| Author:
|
Soukup, L. |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
48 |
| Issue:
|
4 |
| Year:
|
2007 |
| Pages:
|
571-583 |
| . |
| Category:
|
math |
| . |
| Summary:
|
Let $\Bbb G$ and $\Bbb 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 $\Bbb G$ and in $\Bbb D$. The splitting maximal antichains give infinite versions of dualities for graphs and for directed graphs. (English) |
| Keyword:
|
partially ordered set |
| Keyword:
|
homomorphism order |
| Keyword:
|
duality |
| Keyword:
|
antichain |
| Keyword:
|
splitting property |
| MSC:
|
05C99 |
| MSC:
|
06A07 |
| idZBL:
|
Zbl 1199.06008 |
| idMR:
|
MR2375159 |
| . |
| Date available:
|
2009-05-05T17:04:50Z |
| Last updated:
|
2012-05-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119681 |
| . |
| Reference:
|
[1] Ahlswede R., Erdös P.L., Graham N.: A splitting property of maximal antichains.Combinatorica 15 (1995), 475-480. MR 1364020 |
| Reference:
|
[2] Duffus D., Sands B.: Minimum sized fibres in distributive lattices.J. Austral. Math. Soc. 70 (2001), 337-350. Zbl 1019.06002, MR 1829963 |
| Reference:
|
[3] Duffus D., Sands B.: Splitting numbers of grids.Electron. J. Combin. 12 (2005), #R17. Zbl 1060.06005, MR 2134180 |
| Reference:
|
[4] Džamonja M.: A note on the splitting property in strongly dense posets of size $\aleph_0$.Rad. Mat. 8 (1992/98), 321-326. MR 1690735 |
| Reference:
|
[5] Erdös P.: Graph theory and probability.Canad. J. Math. 11 (1959), 34-38. MR 0102081 |
| Reference:
|
[6] Erdös P., Hajnal A.: On chromatic number of graphs and set systems.Acta Math. Hungar. 17 (1966), 61-99. MR 0193025 |
| Reference:
|
[7] Erdös P., Rényi A.: On random graphs I.Publ. Math. Debrecen 6 (1959), 290-297. MR 0120167 |
| Reference:
|
[8] Erdös P.L.: Splitting property in infinite posets.Discrete Math. 163 (1997), 251-256. MR 1428578 |
| Reference:
|
[9] Erdös P.L., Soukup L.: How to split antichains in infinite posets.Combinatorica 27 2 (2007), 147-161. Zbl 1136.06002, MR 2321920 |
| Reference:
|
[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. MR 2408365 |
| Reference:
|
[11] Hell P., Nešetřil J.: Graphs and Homomorphisms.Oxford University Press, Oxford, 2004. MR 2089014 |
| Reference:
|
[12] Nešetřil J.: Sparse incomparability for relational structures.in preparation. |
| Reference:
|
[13] Nešetřil J., Ossona de Mendez P.: Cuts and bounds.Discrete Math. 302 1-3 (2005), 211-224. MR 2179644 |
| Reference:
|
[14] Nešetřil J., Pultr A.: On classes of relations and graphs determined by subobjects and factorobjects.Discrete Math. 22 (1978), 287-300. MR 0522724 |
| Reference:
|
[15] Nešetřil J., V. Rödl V.: Chromatically optimal rigid graphs.J. Combin. Theory Ser. (B) 46 (1989), 133-141. MR 0992987 |
| Reference:
|
[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. Zbl 1024.05078, MR 1778201 |
| Reference:
|
[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. Zbl 1057.05036, MR 2070160 |
| Reference:
|
[18] Nešetřil J., Zhu X.: On sparse graphs with given colorings and homomorphisms.J. Combin. Theory Ser. (B) 90 (2004), 161-172. Zbl 1033.05044, MR 2041324 |
| Reference:
|
[19] Pultr A., Trnková V.: Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories.North-Holland, Amsterdam, 1980. MR 0563525 |
| Reference:
|
[20] Welzl E.: Color families are dense.Theoret. Comput. Sci. 17 (1982), 29-41. Zbl 0482.68063, MR 0644791 |
| . |
