×

zbMATH — the first resource for mathematics

Cuts and flows of cell complexes. (English) Zbl 1333.05323
Authors’ abstract: We study the vector spaces and integer lattices of cuts and flows associated with an arbitrary finite CW complex, and their relationships to group invariants including the critical group of a complex. Our results extend to higher dimension the theory of cuts and flows in graphs, most notably the work of R. Bacher et al. [Bull. Soc. Math. Fr. 125, No. 2, 167–198 (1997; Zbl 0891.05062)]. We construct explicit bases for the cut and flow spaces, interpret their coefficients topologically, and give sufficient conditions for them to be integral bases of the cut and flow lattices. Second, we determine the precise relationships between the discriminant groups of the cut and flow lattices and the higher critical and cocritical groups with error terms corresponding to torsion (co)homology. As an application, we generalize a result of M. Kotani and T. Sunada [Adv. Appl. Math. 24, No. 2, 89–110 (2000; Zbl 1017.05038)] to give bounds for the complexity, girth, and connectivity of a complex in terms of Hermite’s constant.

MSC:
05E45 Combinatorial aspects of simplicial complexes
05C05 Trees
05C21 Flows in graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
11H06 Lattices and convex bodies (number-theoretic aspects)
11E39 Bilinear and Hermitian forms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Artin, M.: Algebra. Prentice-Hall, Englewood Cliffs (1991)
[2] Bacher, R; Harpe, P; Nagnibeda, T, The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France, 125, 167-198, (1997) · Zbl 0891.05062
[3] Baker, M; Norine, S, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math., 215, 766-788, (2007) · Zbl 1124.05049
[4] Biggs, NL, Chip-firing and the critical group of a graph, J. Algebr. Combin., 9, 25-45, (1999) · Zbl 0919.05027
[5] Biggs, N, The critical group from a cryptographic perspective, Bull. London Math. Soc., 39, 829-836, (2007) · Zbl 1126.05054
[6] Björner, A., Vergnas, M.L., Sturmfels, B., White, N., Ziegler, G.: Oriented Matroids. Encyclopedia of Mathematics and its Applications, vol. 46, 2nd edn. Cambridge University Press, Cambridge (1999)
[7] Bond, B., Levine, L.: Abelian Networks: Foundations and Examples. arXiv:1309.3445v1 [cs.FL] (2013).
[8] Catanzaro, M.J., Chernyak, V.Y., Klein, J.R.: Kirchhoff’s theorems in higher dimensions and Reidemeister torsion, Homol. Homotopy Appl. (in press) arXiv:1206.6783v2 [math.AT] (2012)
[9] Cohn, H; Kumar, A, Optimality and uniqueness of the Leech lattice among lattices, Ann. Math. (2), 170, 1003-1050, (2009) · Zbl 1213.11144
[10] Cordovil, R., Lindström, B.: Combinatorial Geometries, Encyclopedia of Mathematics and its Application. Simplicial matroids, vol. 29, pp. 98-113. Cambridge University Press, Cambridge (1987)
[11] D’Adderio, M; Moci, L, Arithmetic matroids, the Tutte polynomial and toric arrangements, Adv. Math., 232, 335-367, (2013) · Zbl 1256.05039
[12] Dhar, D, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64, 1613-1616, (1990) · Zbl 0943.82553
[13] Denham, Graham, The combinatorial Laplacian of the Tutte complex, J. Algebra, 242, 160-175, (2001) · Zbl 0982.05033
[14] Dodziuk, J., Patodi, V.K.: Riemannian structures and triangulations of manifolds, J. Indian Math. Soc. (N.S.) 40 (1976), no. 1-4, 1-52 (1977) · Zbl 0435.58004
[15] Duval, AM; Klivans, CJ; Martin, JL, Simplicial matrix-tree theorems, Trans. Am. Math. Soc., 361, 6073-6114, (2009) · Zbl 1207.05227
[16] Duval, AM; Klivans, CJ; Martin, JL, Cellular spanning trees and Laplacians of cubical complexes, Adv. Appl. Math., 46, 247-274, (2011) · Zbl 1227.05166
[17] Duval, AM; Klivans, CJ; Martin, JL, Critical groups of simplicial complexes, Ann. Comb., 17, 53-70, (2013) · Zbl 1263.05124
[18] Eckmann, B, Harmonische funktionen und randwertaufgaben in einem komplex, Comment. Math. Helv., 17, 240-255, (1945) · Zbl 0061.41106
[19] Fink, A., Moci, L.: Matroids over a ring, J. Eur. Math. Soc. (in press) arXiv:1209.6571v2 [math.CO] (2012) · Zbl 1332.05028
[20] Friedman, J, Computing Betti numbers via combinatorial Laplacians, Algorithmica, 21, 331-346, (1998) · Zbl 0911.57021
[21] Godsil, C., Royle, G.: Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207. Springer, New York (2001) · Zbl 0968.05002
[22] Haase, C; Musiker, G; Yu, J, Linear systems on tropical curves, Math. Z, 270, 1111-1140, (2012) · Zbl 1408.14201
[23] Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001) · Zbl 1044.55001
[24] Hungerford, T.W.: Algebra, Graduate Texts in Mathematics, vol. 73. Springer, New York (1974) · Zbl 0293.12001
[25] Kalai, G, Enumeration of \(\textbf{Q}\)-acyclic simplicial complexes, Israel J. Math., 45, 337-351, (1983) · Zbl 0535.57011
[26] Kotani, M; Sunada, T, Jacobian tori associated with a finite graph and its abelian covering graphs, Adv. Appl. Math., 24, 89-110, (2000) · Zbl 1017.05038
[27] Lagarias, J.: Point lattices, Handbook of Combinatorics, vol. 1. Elsevier, Amsterdam (1995)
[28] Lorenzini, DJ, A finite group attached to the Laplacian of a graph, Discret. Math., 91, 277-282, (1991) · Zbl 0755.05079
[29] Lyons, R, Random complexes and \(ℓ ^2\)-Betti numbers, J. Topol. Anal., 1, 153-175, (2009) · Zbl 1369.05107
[30] Merris, R, Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197-198, 143-176, (1994) · Zbl 0802.05053
[31] Oxley, J.: Matroid Theory. Oxford University Press, New York (1992) · Zbl 0784.05002
[32] Yi, S; Wagner, DG, The lattice of integer flows of a regular matroid, J. Comb. Theory Ser. B, 100, 691-703, (2010) · Zbl 1231.05064
[33] Tutte, WT, Lectures on matroids, J. Res. Nat. Bur. Stand. Sect. B, 69B, 1-47, (1965) · Zbl 0151.33801
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.