Combinatorial topology and the global dimension of algebras arising in combinatorics. (English) Zbl 1330.05166
Summary: In a highly influential paper, P. Bidigare et al. [Duke Math. J. 99, No. 1, 135–174 (1999; Zbl 0955.60043)] showed that a number of popular Markov chains are random walks on the faces of a hyperplane arrangement. Their analysis of these Markov chains took advantage of the monoid structure on the set of faces. This theory was later extended by Brown to a larger class of monoids called left regular bands. In both cases, the representation theory of these monoids played a prominent role. In particular, it was used to compute the spectrum of the transition operators of the Markov chains and to prove diagonalizability of the transition operators.{
}In this paper, we establish a close connection between algebraic and combinatorial invariants of a left regular band: we show that certain homological invariants of the algebra of a left regular band coincide with the cohomology of order complexes of posets naturally associated to the left regular band. For instance, we show that the global dimension of these algebras is bounded above by the Leray number of the associated order complex. Conversely, we associate to every flag complex a left regular band whose algebra has global dimension precisely the Leray number of the flag complex.
MSC:
| 05E15 | Combinatorial aspects of groups and algebras (MSC2010) |
| 16E10 | Homological dimension in associative algebras |
| 16G10 | Representations of associative Artinian rings |
| 52C35 | Arrangements of points, flats, hyperplanes (aspects of discrete geometry) |
| 05E45 | Combinatorial aspects of simplicial complexes |
Keywords:
global dimension; hereditary algebra; cohomology; classifying space; left regular band; hyperplane arrangements; order complex; Leray number; chordal graphCitations:
Zbl 0955.60043References:
| [1] | Abramenko, P., Brown, K. S.: Buildings. Grad. Texts in Math. 248, Springer, New York (2008) · Zbl 1214.20033 · doi:10.1007/978-0-387-78835-7 |
| [2] | Adams, W. W., Rieffel, M. A.: Adjoint functors and derived functors with an application to the cohomology of semigroups. J. Algebra 7, 25-34 (1967) · Zbl 0153.02901 · doi:10.1016/0021-8693(67)90065-8 |
| [3] | Aguiar, M., Mahajan, S.: Coxeter Groups and Hopf Algebras. Fields Inst. Monogr. 23, Amer. Math. Soc., Providence, RI (2006) · Zbl 1106.16039 |
| [4] | Aguiar, M., Mahajan, S.: Monoidal Functors, Species and Hopf Algebras. CRM Monogr. Ser. 29, Amer. Math. Soc., Providence, RI (2010) · Zbl 1209.18002 |
| [5] | Assem, I., Simson, D., Skowroński, A.: Elements of the Representation Theory of Associative Algebras. Vol. 1. London Math. Soc. Student Texts 65, Cambridge Univ. Press, Cambridge (2006) · Zbl 1092.16001 |
| [6] | Athanasiadis, C. A., Diaconis, P.: Functions of random walks on hyperplane arrangements. Adv. Appl. Math. 45, 410-437 (2010) · Zbl 1239.60071 · doi:10.1016/j.aam.2010.02.001 |
| [7] | Auslander, M., Reiten, I., Smalø, S. O.: Representation Theory of Artin Algebras. Cam- bridge Stud. Adv. Math. 36, Cambridge Univ. Press, Cambridge (1997) · Zbl 0834.16001 |
| [8] | Baues, H. J.: Algebraic Homotopy. Cambridge Stud. Adv. Math. 15, Cambridge Univ. Press, Cambridge (1989) · Zbl 1143.55001 |
| [9] | Benson, D. J.: Representations and Cohomology. I. 2nd ed., Cambridge Stud. Adv. Math. 30, Cambridge Univ. Press, Cambridge (1998) · Zbl 0908.20001 |
| [10] | Bestvina, M., Brady, N.: Morse theory and finiteness properties of groups. Invent. Math. 129, 445-470 (1997) · Zbl 0888.20021 · doi:10.1007/s002220050168 |
| [11] | Bidigare, T. P.: Hyperplane arrangement face algebras and their associated Markov chains. Ph.D. Thesis, Univ. of Michigan, ProQuest LLC, Ann Arbor, MI (1997) |
| [12] | Bidigare, P., Hanlon, P., Rockmore, D.: A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements. Duke Math. J. 99, 135-174 (1999) · Zbl 0955.60043 · doi:10.1215/S0012-7094-99-09906-4 |
| [13] | Björner, A.: Topological methods. In: Handbook of Combinatorics, Vol. 1, 2, Elsevier, Ams- terdam, 1819-1872 (1995) · Zbl 0851.52016 |
| [14] | Björner, A.: Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries. In: Building Bridges, Bolyai Soc. Math. Stud. 19, Springer, Berlin, 165-203 (2008) · Zbl 1158.60344 |
| [15] | Björner, A.: Note: Random-to-front shuffles on trees. Electron. Comm. Probab. 14, 36-41 (2009) · Zbl 1190.60059 |
| [16] | Björner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G. M.: Oriented Matroids. Encyclopedia Math. Appl. 46, Cambridge Univ. Press, Cambridge (1993) · Zbl 0773.52001 |
| [17] | Björner, A., Ziegler, G.: Combinatorial stratification of complex arrangements. J. Amer. Math. Soc. 5, 105-149 (1992) · Zbl 0754.52003 · doi:10.2307/2152753 |
| [18] | Bongartz, K.: Algebras and quadratic forms. J. London Math. Soc. (2) 28, 461-469 (1983) · Zbl 0532.16020 · doi:10.1112/jlms/s2-28.3.461 |
| [19] | Borceux, F.: Handbook of Categorical Algebra. 1. Encyclopedia Math. Appl. 50, Cambridge Univ. Press, Cambridge (1994) · Zbl 1143.18001 |
| [20] | Brown, K. S.: Buildings. Springer, New York (1989) · Zbl 0715.20017 |
| [21] | Brown, K. S.: Cohomology of Groups. Grad. Texts in Math. 87, Springer, New York (1994) · Zbl 0584.20036 |
| [22] | Brown, K. S.: Semigroups, rings, and Markov chains. J. Theoret. Probab. 13, 871-938 (2000) · Zbl 0980.60014 · doi:10.1023/A:1007822931408 |
| [23] | Brown, K. S.: Semigroup and ring theoretical methods in probability. In: Representations of Finite Dimensional Algebras and Related Topics in Lie Theory and Geometry, Fields Inst. Comm. 40, Amer. Math. Soc., Providence, RI, 3-26 (2004) · Zbl 1043.60055 |
| [24] | Brown, K. S., Diaconis, P.: Random walks and hyperplane arrangements. Ann. Probab. 26, 1813-1854 (1998) · Zbl 0938.60064 · doi:10.1214/aop/1022855884 |
| [25] | Bustamante, J. C.: The classifying space of a bound quiver. J. Algebra 277, 431-455 (2004) · Zbl 1081.16021 · doi:10.1016/j.jalgebra.2004.02.024 |
| [26] | Cartan, H., Eilenberg, S.: Homological Algebra. Princeton Landmarks in Math., Princeton Univ. Press, Princeton, NJ (1999) · Zbl 0933.18001 |
| [27] | Cartier, P., Foata, D.: Probl‘emes combinatoires de commutation et réarrangements. Lecture Notes in Math. 85, Springer, Berlin (1969) · Zbl 0186.30101 · doi:10.1007/BFb0079468 |
| [28] | Chung, F., Graham, R.: Edge flipping in graphs. Adv. Appl. Math. 48, 37-63 (2012) · Zbl 1234.05210 · doi:10.1016/j.aam.2011.06.002 |
| [29] | Cibils, C.: Cohomology of incidence algebras and simplicial complexes. J. Pure Appl. Algebra 56, 221-232 (1989) · Zbl 0683.16018 · doi:10.1016/0022-4049(89)90058-3 |
| [30] | Clifford, A. H.: Semigroups admitting relative inverses. Ann. of Math. (2) 42, 1037-1049 (1941) · Zbl 0063.00920 · doi:10.2307/1968781 |
| [31] | Clifford, A. H., Preston, G. B.: The Algebraic Theory of Semigroups. Vol. I. Math. Surveys 7, Amer. Math. Soc., Providence, RI (1961) · Zbl 0111.03403 |
| [32] | Cline, E., Parshall, B., Scott, L.: Finite-dimensional algebras and highest weight categories. J. Reine Angew. Math. 391, 85-99 (1988) · Zbl 0657.18005 |
| [33] | Cohen, D. E.: A monoid which is right F P\infty but not left F P1. Bull. London Math. Soc. 24, 340-342 (1992) · Zbl 0726.20044 · doi:10.1112/blms/24.4.340 |
| [34] | Diaconis, P.: From shuffling cards to walking around the building: an introduction to modern Markov chain theory. In: Proc. Int. Congress of Mathematicians, Vol. I (Berlin, 1998), Doc. Math. Extra Vol. I, 187-204 (1998) · Zbl 0902.60052 |
| [35] | Diekert, V., Rozenberg, G. (eds.): The Book of Traces. World Sci., River Edge, NJ (1995) |
| [36] | Dirac, G. A.: On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg 25, 71-76 (1961) · Zbl 0098.14703 · doi:10.1007/BF02992776 |
| [37] | Dochtermann, A., Engström, A.: Algebraic properties of edge ideals via combinatorial topology. Electron. J. Combin. 16, no. 2, res. paper 2, 24 pp. (2009) · Zbl 1161.13013 |
| [38] | Dorofeeva, M. P.: Hereditary and semi-hereditary monoids. Semigroup Forum 4, 301-311 (1972) · Zbl 0259.20059 · doi:10.1007/BF02570802 |
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.
