×

High-dimensional networks and spanning forests. (English) Zbl 1417.05193

Summary: High-dimensional networks are a topological generalization of electrical networks. As combinatorial invariants of electrical networks often require enumeration of trees, their high-dimensional analogues are also based on torsion-weighted enumeration of acyclic subcomplexes over the reals. In this paper, for a high-dimensional network with a current generator, we express a current vector and a voltage vector in terms of high-dimensional forests. To this end, we introduce a new simple method, an acyclization in codimension 1, for computing forest-numbers.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05E45 Combinatorial aspects of simplicial complexes
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
55U15 Chain complexes in algebraic topology
05C05 Trees
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
94C15 Applications of graph theory to circuits and networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Biggs, N., Algebraic potential theory on graphs, Bull. Lond. Math. Soc., 29, 6, 641-682 (1997)
[2] Bollobás, B., Modern Graph Theory, vol. 184 (2013), Springer Science & Business Media
[3] Catanzaro, M.; Chernyak, V.; Klein, J., Kirchhoff’s theorems in higher dimensions and Reidemeister torsion, Homol. Homotopy Appl., 17, 1, 165-189 (2015) · Zbl 1348.55013
[4] Catanzaro, M.; Chernyak, V.; Klein, J., A higher Boltzmann distribution, J. Appl. Comput. Topol., 1, 2, 215-240 (2017) · Zbl 1397.18034
[5] Duval, A.; Klivans, C.; Martin, J., Simplicial matrix-tree theorems, Trans. Am. Math. Soc., 361, 6073-6114 (2009) · Zbl 1207.05227
[6] Duval, A.; Klivans, C.; Martin, J., Cellular spanning trees and Laplacians of cubical complexes, Adv. Appl. Math., 46, 247-274 (2011) · Zbl 1227.05166
[7] Duval, A.; Klivans, C.; Martin, J., Cuts and flows of cell complexes, J. Algebraic Comb., 41, 4, 969-999 (2014) · Zbl 1333.05323
[8] Duval, A.; Klivans, C.; Martin, J., Simplicial and cellular trees, (Recent Trends in Combinatorics (2016), Springer: Springer Cham), 713-752 · Zbl 1354.05151
[9] Friedman, J., Computing Betti numbers via combinatorial Laplacians, Algorithmica, 21, 331-346 (1998) · Zbl 0911.57021
[10] Gantmacher, F., The Theory of Matrices, vol. 1 (1960), Chelsea: Chelsea New York
[11] Kalai, G., Enumeration of \(Q\)-acyclic simplicial complexes, Isr. J. Math., 45, 337-351 (1983) · Zbl 0535.57011
[12] Kim, H.; Kook, W., Logarithmic tree-numbers for acyclic complexes, Electron. J. Comb., 21, Article P1.50 pp. (2014) · Zbl 1300.05333
[13] Kook, W., Combinatorial Green’s function of a graph and applications to networks, Adv. Appl. Math., 46, 417-423 (2011) · Zbl 1222.05162
[14] Kook, W.; Lee, K., Simplicial networks and effective resistance, Adv. Appl. Math., 100, 71-86 (2018) · Zbl 1393.05316
[15] Lyons, R., Random complexes and \(l^2\)-Betti numbers, J. Topol. Anal., 1, 153-175 (2009) · Zbl 1369.05107
[16] Nerode, A.; Shank, H., An algebraic proof of Kirchhoff’s network theorem, Am. Math. Mon., 68, 244-247 (1961) · Zbl 0102.33902
[17] Roth, J., An application of algebraic topology to numerical analysis: on the existence of a solution to the network problem, Proc. Natl. Acad. Sci. USA, 41, 518-521 (1955) · Zbl 0068.32603
[18] Thomassen, C., Resistances and currents in infinite electrical networks, J. Comb. Theory, Ser. B, 49, 87-102 (1990) · Zbl 0706.94029
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.