ALGEBRAIC COMBINATORICS

no. 3
Discrete cubical and path homologies of graphs
Barcelo, Hélène1; Greene, Curtis2; Jarrah, Abdul Salam3; Welker, Volkmar4
1 The Mathematical Sciences Research Institute, 17 Gauss Way, Berkeley, CA 94720, USA
2 Haverford College, Haverford, PA 19041, USA
3 Department of Mathematics and Statistics, American University of Sharjah, PO Box 26666, Sharjah, United Arab Emirates
4 Fachbereich Mathematik und Informatik Philipps-Universität 35032 Marburg, Germany
Algebraic Combinatorics, Volume 2 (2019) no. 3, pp. 417-437.

In this paper we study and compare two homology theories for (simple and undirected) graphs. The first, which was developed by Barcelo, Capraro, and White, is based on graph maps from hypercubes to the graph. The second theory was developed by Grigor’yan, Lin, Muranov, and Yau, and is based on paths in the graph. Results in both settings imply that the respective homology groups are isomorphic in homological dimension one. We show that, for several infinite classes of graphs, the two theories lead to isomorphic homology groups in all dimensions. However, we provide an example for which the homology groups of the two theories are not isomorphic at least in dimensions two and three. We establish a natural map from the cubical to the path homology groups which is an isomorphism in dimension one and surjective in dimension two. Again our example shows that in general the map is not surjective in dimension three and not injective in dimension two. In the process we develop tools to compute the homology groups for both theories in all dimensions.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.49
Classification: 05C99, 55U99
Keywords: Discrete cubical homology, path homology, homology of graphs
Barcelo, Hélène 1; Greene, Curtis 2; Jarrah, Abdul Salam 3; Welker, Volkmar 4

1 The Mathematical Sciences Research Institute, 17 Gauss Way, Berkeley, CA 94720, USA
2 Haverford College, Haverford, PA 19041, USA
3 Department of Mathematics and Statistics, American University of Sharjah, PO Box 26666, Sharjah, United Arab Emirates
4 Fachbereich Mathematik und Informatik Philipps-Universität 35032 Marburg, Germany
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2019__2_3_417_0,
     author = {Barcelo, H\'el\`ene and Greene, Curtis and Jarrah, Abdul Salam and Welker, Volkmar},
     title = {Discrete cubical and path homologies of graphs},
     journal = {Algebraic Combinatorics},
     pages = {417--437},
     publisher = {MathOA foundation},
     volume = {2},
     number = {3},
     year = {2019},
     doi = {10.5802/alco.49},
     mrnumber = {3968745},
     zbl = {07066882},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.49/}
}
TY  - JOUR
AU  - Barcelo, Hélène
AU  - Greene, Curtis
AU  - Jarrah, Abdul Salam
AU  - Welker, Volkmar
TI  - Discrete cubical and path homologies of graphs
JO  - Algebraic Combinatorics
PY  - 2019
SP  - 417
EP  - 437
VL  - 2
IS  - 3
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.49/
DO  - 10.5802/alco.49
LA  - en
ID  - ALCO_2019__2_3_417_0
ER  - 
%0 Journal Article
%A Barcelo, Hélène
%A Greene, Curtis
%A Jarrah, Abdul Salam
%A Welker, Volkmar
%T Discrete cubical and path homologies of graphs
%J Algebraic Combinatorics
%D 2019
%P 417-437
%V 2
%N 3
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.49/
%R 10.5802/alco.49
%G en
%F ALCO_2019__2_3_417_0
Barcelo, Hélène; Greene, Curtis; Jarrah, Abdul Salam; Welker, Volkmar. Discrete cubical and path homologies of graphs. Algebraic Combinatorics, Volume 2 (2019) no. 3, pp. 417-437. doi : 10.5802/alco.49. https://alco.centre-mersenne.org/articles/10.5802/alco.49/

[1] Babson, Eric; Barcelo, Hélène; de Longueville, Mark; Laubenbacher, Reinhard Homotopy theory of graphs, J. Algebr. Comb., Volume 24 (2006) no. 1, pp. 31-44 | DOI | MR | Zbl

[2] Barcelo, Hélène; Capraro, Valerio; White, Jacob A. Discrete homology theory for metric spaces, Bull. Lond. Math. Soc., Volume 46 (2014), pp. 889-905 | DOI | MR | Zbl

[3] Barcelo, Hélène; Kramer, Xenia; Laubenbacher, Reinhard; Weaver, Christopher Foundations of connectivity theory for simplicial complexes, Adv. Appl. Math., Volume 26 (2001), pp. 97-128 | DOI | MR | Zbl

[4] Diestel, Reinhard Graph theory, Graduate Texts in Mathematics, 173, Springer, 2000 | Zbl

[5] Federer, Herbert Lectures on algebraic topology, Brown University, 1962

[6] Grigor’yan, Alexander; Lin, Yong; Muranov, Yuri; Yau, Shing-Tung Homologies of path complexes and digraphs (2013) (https://arxiv.org/abs/1207.2834v4)

[7] Grigor’yan, Alexander; Lin, Yong; Muranov, Yuri; Yau, Shing-Tung Homotopy theory of digraphs, Pure Appl. Math. Q., Volume 10 (2014), pp. 619-674 | DOI | MR | Zbl

[8] Grigor’yan, Alexander; Lin, Yong; Muranov, Yuri; Yau, Shing-Tung Cohomology of digraphs and (undirected) graphs, Asian J. Math., Volume 19 (2015) no. 5, pp. 887-932 | DOI | MR | Zbl

[9] Hammack, Richard; Imrich, Wilfried; Klavžar, Sandi Handbook of product graphs, Discrete Mathematics and its Applications, CRC Press, 2011 | Zbl

[10] Märte, Julian Discrete Cubical Homology of Graphs, https://github.com/jmaerte/discrete_cubical_homology_of_graphs, 2017 (Software Package)

[11] Massey, William S. A basic course in algebraic topology, Graduate Texts in Mathematics, 127, Springer, 1991 | MR | Zbl

[12] Munkres, James R. Elements of algebraic topology, Advanced Book Program, Addison–Wesley Publishing Company, 1984 | MR | Zbl

[13] Rose, Donald J. Triangulated graphs and the elimination process, J. Math. Anal. Appl., Volume 32 (1970), pp. 597-609 | DOI | MR | Zbl

[14] Stanley, Richard P. Combinatorics and commutative algebra, Progress in Mathematics, 41, Birkhäuser, 1996 | MR | Zbl

Cited by Sources: