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.

Revised : 2018-09-19

Accepted : 2018-11-12

Published online : 2019-06-06

DOI : https://doi.org/10.5802/alco.49

Classification: 05C99, 55U99

Keywords: Discrete cubical homology, path homology, homology of graphs

@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}, publisher = {MathOA foundation}, volume = {2}, number = {3}, year = {2019}, pages = {417-437}, doi = {10.5802/alco.49}, zbl = {07066882}, language = {en}, url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_3_417_0} }

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/item/ALCO_2019__2_3_417_0/

[1] Homotopy theory of graphs, J. Algebr. Comb., Volume 24 (2006) no. 1, pp. 31-44 | Article | MR 2245779 | Zbl 1108.05030

[2] Discrete homology theory for metric spaces, Bull. Lond. Math. Soc., Volume 46 (2014), pp. 889-905 | Article | MR 3262192 | Zbl 1308.55004

[3] Foundations of connectivity theory for simplicial complexes, Adv. Appl. Math., Volume 26 (2001), pp. 97-128 | Article | MR 1808443 | Zbl 0984.57014

[4] Graph theory, Springer, Graduate Texts in Mathematics, Volume 173 (2000) | Zbl 0945.05002

[5] Lectures on algebraic topology, Brown University (1962)

[6] Homologies of path complexes and digraphs (2013) (https://arxiv.org/abs/1207.2834v4 )

[7] Homotopy theory of digraphs, Pure Appl. Math. Q., Volume 10 (2014), pp. 619-674 | Article | MR 3324763 | Zbl 1312.05063

[8] Cohomology of digraphs and (undirected) graphs, Asian J. Math., Volume 19 (2015) no. 5, pp. 887-932 | Article | MR 3431683 | Zbl 1329.05132

[9] Handbook of product graphs, CRC Press, Discrete Mathematics and its Applications (2011) | Zbl 1283.05001

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

[11] A basic course in algebraic topology, Springer, Graduate Texts in Mathematics, Volume 127 (1991) | MR 1095046 | Zbl 0725.55001

[12] Elements of algebraic topology, Addison–Wesley Publishing Company, Advanced Book Program (1984) | MR 755006 | Zbl 0673.55001

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

[14] Combinatorics and commutative algebra, Birkhäuser, Progress in Mathematics, Volume 41 (1996) | MR 1453579 | Zbl 1157.13302