The discrete fundamental group of the order complex of B n
Hélène Barcelo1
and Shelly Smith2
1Arizona State University Department of Mathematics \& Statistics Tempe AZ 85287-1804 USA
2Grand Valley State University Department of Mathematics Grand rapids MI 49401-9403 USA
2Grand Valley State University Department of Mathematics Grand rapids MI 49401-9403 USA
DOI: 10.1007/s10801-007-0094-z
Abstract
A few years ago Kramer and Laubenbacher introduced a discrete notion of homotopy for simplicial complexes. In this paper, we compute the discrete fundamental group of the order complex of the Boolean lattice. As it turns out, it is equivalent to computing the discrete homotopy group of the 1-skeleton of the permutahedron. To compute this group we introduce combinatorial techniques that we believe will be helpful in computing discrete fundamental groups of other polytopes. More precisely, we use the language of words, over the alphabet of simple transpositions, to obtain conditions that are necessary and sufficient to characterize the equivalence classes of cycles. The proof requires only simple combinatorial arguments. As a corollary, we also obtain a combinatorial proof of the fact that the first Betti number of the complement of the 3-equal arrangement is equal to 2 n - 3( n 2 - 5 n+8) - 1. This formula was originally obtained by Björner and Welker in 1995.
Pages: 399–421
Keywords: keywords permutahedron; Boolean lattice; homotopy groups; $A$-theory; subspace arrangements; symmetric group
Full Text: PDF
References
1. Babson, E., Barcelo, H., de Longueville, M., Laubenbacher, R.: Homotopy theory for graphs. J. Al- gebr. Comb. 24, 31-44 (2006)
2. Barcelo, H., Kramer, X., Laubenbacher, R., Weaver, C.: Foundations of a connectivity theory for simplicial complexes. Adv. Appl. Math. 26, 97-128 (2001)
3. Barcelo, H., Laubenbacher, R.: Perspectives on A-homotopy and its applications. Discrete Math. 298, 39-61 (2005)
4. Barcelo, H., Laubenbacher, R.: Graph theoretic tools for dynamic network analysis. Preprint (2005)
5. Björner, A.: personal communication
6. Björner, A.: Subspace arrangements. In: Proceedings of 1st European Congress of Mathematics, vol. I, Paris,
1992. Progress Mathematics, vol. 119, pp. 321-370. Birkhäuser, Basel (1994)
7. Björner, A., Lovász, L.: Linear decision trees, subspace arrangements and Möbius functions. J. Am. Math. Soc. 7, 677-706 (1994)
8. Björner, A., Wachs, M.: Shellable nonpure complexes and posets, I. Trans. Am. Math. Soc. 348, 1299-1327 (1996)
9. Björner, A., Welker, V.: The homology of “k-equal” manifolds and related partition lattices. Adv. Math. 110, 277-313 (1995)
10. Dochtermann, A.: Hom complexes and homotopy theory in the category of graphs. arXiv:math.CO/0605275v2
11. Dochtermann, A.: Homotopy groups of Hom complexes of graphs. arXiv:math.CO/0705.2620v1
12. Hanish, L., Martin, C., Fabes, R., Barcelo, H., Griffin, W.: The breadth of peer relationship among externalizing preschoolers: an illustration of the Q-connectivity method. Preprint (2006)
13. Kramer, X., Laubenbacher, R.: Combinatorial homotopy of simplicial complexes and complex information networks. In: Cox, D., Sturmfels, B. (eds.) Applications of Computational Algebraic Geometry. Proceedings of Symposia in Applied Mathematics, vol.
53. American Mathematical Society, Providence (1998)
14. Malle, G.: A homotopy theory for graphs. Glas. Mat. 18, 3-25 (1983)
15. Maurer, S.: Matroid basis graphs, I. J. Comb. Theory B 14, 216-240 (1973)
16. Smith, S.: A discrete homotopy theory for graphs, with applications to order complexes of lattices.
2. Barcelo, H., Kramer, X., Laubenbacher, R., Weaver, C.: Foundations of a connectivity theory for simplicial complexes. Adv. Appl. Math. 26, 97-128 (2001)
3. Barcelo, H., Laubenbacher, R.: Perspectives on A-homotopy and its applications. Discrete Math. 298, 39-61 (2005)
4. Barcelo, H., Laubenbacher, R.: Graph theoretic tools for dynamic network analysis. Preprint (2005)
5. Björner, A.: personal communication
6. Björner, A.: Subspace arrangements. In: Proceedings of 1st European Congress of Mathematics, vol. I, Paris,
1992. Progress Mathematics, vol. 119, pp. 321-370. Birkhäuser, Basel (1994)
7. Björner, A., Lovász, L.: Linear decision trees, subspace arrangements and Möbius functions. J. Am. Math. Soc. 7, 677-706 (1994)
8. Björner, A., Wachs, M.: Shellable nonpure complexes and posets, I. Trans. Am. Math. Soc. 348, 1299-1327 (1996)
9. Björner, A., Welker, V.: The homology of “k-equal” manifolds and related partition lattices. Adv. Math. 110, 277-313 (1995)
10. Dochtermann, A.: Hom complexes and homotopy theory in the category of graphs. arXiv:math.CO/0605275v2
11. Dochtermann, A.: Homotopy groups of Hom complexes of graphs. arXiv:math.CO/0705.2620v1
12. Hanish, L., Martin, C., Fabes, R., Barcelo, H., Griffin, W.: The breadth of peer relationship among externalizing preschoolers: an illustration of the Q-connectivity method. Preprint (2006)
13. Kramer, X., Laubenbacher, R.: Combinatorial homotopy of simplicial complexes and complex information networks. In: Cox, D., Sturmfels, B. (eds.) Applications of Computational Algebraic Geometry. Proceedings of Symposia in Applied Mathematics, vol.
53. American Mathematical Society, Providence (1998)
14. Malle, G.: A homotopy theory for graphs. Glas. Mat. 18, 3-25 (1983)
15. Maurer, S.: Matroid basis graphs, I. J. Comb. Theory B 14, 216-240 (1973)
16. Smith, S.: A discrete homotopy theory for graphs, with applications to order complexes of lattices.