WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences. (English) Zbl 1074.05091
Summary: An evergreen theme in topological graph theory is the study of graph complexes [E. Balson and D. N. Kozlov, Proof of the Lovász conjecture, arXiv:math.CO/0402395, 2, 2004; J. Comb. Theory, Ser. A 25, 319–324 (1978); J. Matousek, Using the Borsuk-Ulam theorem, Lectures on topological methods in combinatorics and geometry (Springer Universitext, Berlin) (2003; Zbl 1016.05001); J. Matousek and G. M. Ziegler, Jahresber. Dtsch. Math.-Ver. 106, 71–90 (2004; Zbl 1063.05047)]. Many of these complexes are \(\mathbb{Z}_2\)-spaces and the associated \(\mathbb{Z}_2\)-index \(\text{Ind}_{\mathbb{Z}_2}(X)\) is an invariant of great importance for estimating the chromatic numbers of graphs. We introduce WI-posets (Definition 2) as intermediate objects and emphasize the importance of Bredon’s theorem (Theorem 9) which allows us to use standard tools of topological combinatorics for comparison of \(\mathbb{Z}_2\)-homotopy types of \(\mathbb{Z}_2\)-posets. Among the consequences of general results are known and new results about \(\mathbb{Z}_2\)-bomotopy types of graph complexes. It turns out that, in spite of great variety of approaches and definitions, all \(\mathbb{Z}_2\)-graph complexes associated to \(G\) can be viewed as avatars of the same object, as long as their \(\mathbb{Z}_2\)-homotopy types are concerned. Among the applications are a proof that each finite, free \(\mathbb{Z}_2\)-complex is a graph complex and an evaluation of \(\mathbb{Z}_2\)-homotopy types of complexes \(\text{Ind}(C_n)\) of independence sets in a cycle \(C_n\).
MSC:
| 05E25 | Group actions on posets, etc. (MSC2000) |
| 06A07 | Combinatorics of partially ordered sets |
Keywords:
Bredon’s theoremReferences:
| [1] | Alon, N.; Frankl, P.; Lovász, L., The chromatic number of Kneser hypergraphs, Trans. Amer. Math. Soc., 298, 359-370 (1986) · Zbl 0605.05033 |
| [2] | E. Babson, D.N. Kozlov, Topological obstructions to graph colorings, arXiv:math.CO/0305300.; E. Babson, D.N. Kozlov, Topological obstructions to graph colorings, arXiv:math.CO/0305300. · Zbl 1063.05041 |
| [3] | E. Babson, D.N. Kozlov, Complexes of graph homomorphisms, arXiv:math.CO/0310056, 1, 5 October 2003.; E. Babson, D.N. Kozlov, Complexes of graph homomorphisms, arXiv:math.CO/0310056, 1, 5 October 2003. · Zbl 1205.52009 |
| [4] | E. Babson, D.N. Kozlov, Proof of the Lovász conjecture, arXiv:math.CO/0402395, 2, 2004.; E. Babson, D.N. Kozlov, Proof of the Lovász conjecture, arXiv:math.CO/0402395, 2, 2004. |
| [5] | Björner, A., Topological methods, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), North-Holland: North-Holland Amsterdam) · Zbl 0851.52016 |
| [6] | G.E. Bredon, Equivariant cohomology theories, Lecture Notes in Mathematics, vol. 34, Springer, Berlin 1967.; G.E. Bredon, Equivariant cohomology theories, Lecture Notes in Mathematics, vol. 34, Springer, Berlin 1967. · Zbl 0162.27202 |
| [7] | P. Csorba, \( B_0(G) = \mathit{susp}(B(G))\); P. Csorba, \( B_0(G) = \mathit{susp}(B(G))\) |
| [8] | P. Csorba, Homotopy type of box complexes, April 28, 2004, preprint.; P. Csorba, Homotopy type of box complexes, April 28, 2004, preprint. · Zbl 1236.05067 |
| [9] | P. Csorba, C. Lange, I. Schurr, A. Wassmer, Box complexes, neighborhood complexes, and the chromatic number, arXiv:math.CO/0310339, 1, 21 October 2003.; P. Csorba, C. Lange, I. Schurr, A. Wassmer, Box complexes, neighborhood complexes, and the chromatic number, arXiv:math.CO/0310339, 1, 21 October 2003. · Zbl 1060.05029 |
| [10] | T. tom Dieck, Transformation Groups, De Gruyter Studies in Mathematics, vol. 8, Berlin, 1987.; T. tom Dieck, Transformation Groups, De Gruyter Studies in Mathematics, vol. 8, Berlin, 1987. · Zbl 0611.57002 |
| [11] | James, I. M.; Segal, G. B., On equivariant homotopy type, Topology, 17, 267-272 (1978) · Zbl 0403.57007 |
| [12] | Kozlov, D. N., Complexes of directed trees, J. Combin. Theory Ser. A, 88, 1, 112-122 (1999) · Zbl 0934.05041 |
| [13] | Kříž, I., Equivariant cohomology and lower bounds for chromatic numbers, Trans. Amer. Math. Soc., 33, 567-577 (1999) · Zbl 0756.05055 |
| [14] | Lovász, L., Kneser’s conjecture, chromatic number and homotopy, J. Combin. Theory Ser. A, 25, 319-324 (1978) · Zbl 0418.05028 |
| [15] | Matoušek, J., Using the Borsuk-Ulam Theorem, Lectures on Topological Methods in Combinatorics and Geometry (2003), Springer Universitext: Springer Universitext Berlin · Zbl 1016.05001 |
| [16] | J. Matoušek, G. Ziegler, Topological lower bounds for the chromatic number; A hierarchy, Jahresbericht der DMV 106 (2004) 71-90, arXiv:math.CO/0208072, v3, 2003.; J. Matoušek, G. Ziegler, Topological lower bounds for the chromatic number; A hierarchy, Jahresbericht der DMV 106 (2004) 71-90, arXiv:math.CO/0208072, v3, 2003. · Zbl 1063.05047 |
| [17] | R. Meshulam, Domination numbers and homology, J. Combin. Theory Ser. A 102 (2003) 321-330.; R. Meshulam, Domination numbers and homology, J. Combin. Theory Ser. A 102 (2003) 321-330. · Zbl 1030.05086 |
| [18] | Milgram, R. J.; Zvengrowski, P., An applications of principal bundles to coloring of graphs and hypergraphs, Rend. Circ. Mat. Palermo (, (2) Suppl., 161-167 (1994) · Zbl 0831.05030 |
| [19] | Quillen, D., Homotopy properties of the poset of nontrivial \(p\)-subgroups of a group, Adv. in Math., 28, 101-128 (1978) · Zbl 0388.55007 |
| [20] | Sarkaria, K. S., A generalized Kneser conjecture, J. Combin. Theory Ser. B, 49, 236-240 (1990) · Zbl 0714.05001 |
| [21] | Segal, G., Classifying spaces and spectral sequences, Publ. Math. I.H.E.S., 34, 105-112 (1968) · Zbl 0199.26404 |
| [22] | Spanier, E., Algebraic Topology (1966), McGraw-Hill: McGraw-Hill New York · Zbl 0145.43303 |
| [23] | Walker, J. W., From graphs to ortholattices to equivariant maps, J. Combin. Theory Ser. B, 35, 171-192 (1983) · Zbl 0509.05059 |
| [24] | Welker, V.; Ziegler, G. M.; Živaljević, R. T., Homotopy colimits—comparison lemmas for combinatorial applications, J. Reine Angew. Math., 509, 117-149 (1999) · Zbl 0995.55004 |
| [25] | Ziegler, G. M.; Živaljević, R. T., Homotopy types of subspace arrangements via diagrams of spaces, Math. Ann., 295, 527-548 (1993) · Zbl 0792.55002 |
| [26] | R. Živaljević, User’s guide to equivariant methods in combinatorics I and II, Publ. Inst. Math. Belgrade 59(73) (1996) 114-130 and 64(78) (1998) 107-132.; R. Živaljević, User’s guide to equivariant methods in combinatorics I and II, Publ. Inst. Math. Belgrade 59(73) (1996) 114-130 and 64(78) (1998) 107-132. · Zbl 0946.52001 |
| [27] | R. Živaljević, Topological methods, in: J.E. Goodman, J.O’Rourke (Eds.), Handbook of Discrete and Computational Geometry, new ed., CRC Press, Boca Raton, 2004.; R. Živaljević, Topological methods, in: J.E. Goodman, J.O’Rourke (Eds.), Handbook of Discrete and Computational Geometry, new ed., CRC Press, Boca Raton, 2004. · Zbl 1056.52001 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
