discretepapers

This page is a repository of papers that study discrete mathematical structures like graphs and simplicial complexes using tools of algebraic topology: namely homology and homotopy groups. It will be updated occasionally.

Graph Homotopy and Homology

In this section we look at various ways of obtaining homotopy and homology theories from graphs.

X-Homotopy Theory

We obtain a space from a simple, undirected graph \(G\) by looking at the simplicial complex \(\text{Cl}(G)\), called its clique complex. We can study important combinatorial properties of the graph \(G\) using the homotopy and homology of various constructions of its clique complex. For example, in 1978 Lovász proved Kneser’s conjecture by obtaining the chromatic number of the family of Kneser graphs. This began the area of topological combinatorics. He did this by finding a lower bound on the chromatic number of a graph in terms of the homotopy connectivity of \(\text{Cl}(G^{K_2})\). For more on this check out Lovász’s original paper, this survey by Mark de Longueville, this paper on the state-of-the-art regarding these ideas and Dochtermann’s paper (Remark 3.6) displaying the connection of Hom complexes with clique complexes.

(2009) Hom complexes and homotopy theory in the category of graphs by Anton Dochtermann
  • European Journal of Combinatorics 30.2 (2009): 490-509 (link)
  • This is the paper that starts \(\times\)-homotopy theory of undirected, simple loop graphs (graphs with at most one loop at each vertex, at most one edge between any two vertices), evolving out of the study of the Hom complex of loop graphs by Babson, Kozlov, Csorba, Matsushita amongst many others.
(2009) Homotopy groups of Hom complexes of graphs by Anton Dochtermann
  • Journal of Combinatorial Theory, Series A 116.1 (2009): 180-194. (link)
(2017) Box Complexes and Homotopy Theory of Graphs by Takahiro Matsushita
  • Homology, Homotopy and Applications, vol. 19(2), 2017, pp.175–197 (link)
  • In this paper, Matsushita crafts two model structures on the category of loop graphs \( \mathbf{Gr}_\ell \). One of these model structures is Quillen equivalent to the classical Quillen model structure on spaces, and the other is Quillen equivalent to a \(\mathbb{Z}_2\)-equivariant version of the classical model structure on spaces. In my paper below, I show that the former model structure is actually right transferred from spaces, and factors through a model structure on reflexive graphs and on simplicial complexes, showing they are all Quillen equivalent.
(2025) Thomason-Type Model Structures on Simplicial Complexes and Graphs by Emilio Minichiello

A-Homotopy Theory

In A-homotopy theory, we craft a space from a simple, undirected graph by probing it with cubes. This theory was developed predominantly by Hélène Barcelo and her collaborators in the early 2000s, inspired by earlier work of Atkins studying networks using simplicial complexes.

(2001) Foundations of a Connectivity Theory for Simplicial Complexes by Hélène Barcelo, Xenia Kramer, Reinhard Laubenbacher and Christopher Weaver.
  • Advances in Applied Mathematics 26, no. 2 (2001): 97–128. (link)
  • I consider this to be the first paper in A-homotopy theory, even though it is based off of papers by Atkins and his students, inspired by work in the social sciences on social dynamics, which are about what he calls Q-analysis of simplicial complexes. In this paper, Barcelo et al really get to work putting Atkins' idea on a a rigorous footing.
  • They define the A-homotopy group \(A^q_n(\Delta, x_0)\) of a simplicial complex.
  • They associate to every simplicial complex \(\Delta\) a \(q\)-conectivity graph \(\Gamma^q(\Delta)\), whose vertices are the simplices of \(\Delta\) of dimension \(\geq q\) and whose edges connect those simplices which share a \(q\)-face. They define the \(A\)-homotopy groups of a graph \(A_n(G, x_0)\) such that \(A_n(\Gamma^q(\Delta), x_0) \cong A^q_n(\Delta, x_0)\).
  • They show that the \(A\)-fundamental group \(A^q_1(\Delta, x_0) \) can be computed easily by taking the \(q\)-connectivity graph \(\Gamma^q(\Delta)\) and filling in all 3 and 4-cycles with a 2-cell, and taking the usual fundamental group of the resulting CW complex.
  • They prove a Seifert-Van Kampen type theorem for the \(A\)-fundamental group.
(2005) Perspectives on A-Homotopy Theory and Its Applications by Hélène Barcelo, and Reinhard Laubenbacher.
  • Discrete Mathematics, Formal Power Series and Algebraic Combinatorics 2002 (FPSAC’02), vol. 298, no. 1 (2005): 39–61. (link)
  • Really wonderful paper that gives a whole bunch of applications and relationships of \(A\)-homotopy theory to combinatorics. Barcelo and Laubenbacher show that \(A\)-homotopy theory shows up in the work of several combinatorialists:
    • in the work of Maurer (1973) on matroids. In particular Maurer proves that if \(M\) is a matroid, and \(\mathcal{B}(M) \) is the basis graph of \(M\), then \(\mathcal{B}(M)\) has \(A_1(\mathcal{B}(M) = 0 \).
    • in the work of Lovasz (1977) on \(k\)-fold partitions of \(k\)-connected graphs,
    • in the work of Malle (1983), who proves that if \(G\) is a graph, then \(A_1(G) = 0\) if and only if every cycle in \(G\) has a pseudoplanar net in \(G\).
    • in the work of Babson and Bjorner, but published later by Barcelo-Severs-White (2011) as Theorem 3.1. The \(k\)-equal arrangement, \(A_{n,k} \) is the collection of all subspaces of \( \mathbb{R}^{n+1} \) given by \(x_{i_1} = x_{i_2} = \dots = x_{i_k}\) over all indices \({i_1, \dots , i_k} \subseteq [ n + 1]\), with the relation \(\sum_{i=1}^{n+1} x_i = 0 \). They prove that if \(U(A_{n,k}) \) denotes the complement of \(A_{n,k}\) in \(\mathbb{R}^{n+1} \), then \(\pi_1(U(A_{n,k})) \cong A_1^{n - k + 1}(\Delta(B_n)) \), where \(\Delta(B_n) \) is the order complex of the Boolean lattice \(B_n = \{0,1\}^n \).
(2006) Homotopy Theory of Graphs by Eric Babson, Hélène Barcelo, Mark Longueville, and Reinhard Laubenbacher.
  • J. Algebraic Comb. 24, no. 1 (2006): 31–44. (link)
  • One of the key results of the 2001 Foundations paper computes the \(A\)-fundamental group of a graph \(G\) in terms of the usual fundamental group of a related space \(X_G \) obtained by filling in the 3 and 4 cycles with 2-cells. This paper addresses the question of this can be achieved for the higher \(A\)-homotopy groups.
  • They define the loop graph \(\Omega G \) of a graph \(G \) and prove that \( A_{n+1}(G) \cong A_n(\Omega G) \) for \(n \geq 0 \).
  • Given a graph \(G \), they construct a cubical set \(N_1(G) \) (which they denote \(M_*(G) \), but we will use the notation from Kapulkin-Carranza (2024)) and prove that if a certain cubical approximation conjecture holds (and note that as of this writing, this conjecture is still open) then \(\pi_n(N_1(G)) \cong A_n(G) \) for all \(n \geq 1 \).
    • Note that the above result was later proven in Kapulkin-Carranza (2024), using abstract homotopy theory, entirely avoiding having to prove the cubical approximation conjecture.
(2014) Discrete Homology Theory for Metric Spaces by Hélène Barcelo, Valerio Capraro, and Jacob A. White.
  • Bulletin of the London Mathematical Society 46, no. 5: 889–905. (link)
  • Develops a notion of discrete homology for metric spaces that satisfies a discrete form of the Eilenberg-Steenrod axioms.
  • Unfortunately, the Mayer-Vietoris theorem proven here is not as useful as one might think for A-homotopy theory. In the context of A-homotopy theory, the kind of cover needed for excision and Mayer-Vietoris would be a discrete cover, which is a cover of a graph by subgraphs such that every nondegenerate singular cube \(f : Q_n \to G \) factors through one of the subgraphs. In practice this cannot be checked, as there is an enormous amount of nondegenerate singular cubes of high dimensions.
(2019) Discrete Cubical and Path Homologies of Graphs by Hélène Barcelo, Curtis Greene, Abdul Salam Jarrah, and Volkmar Welker.
  • Algebraic Combinatorics 2, no. 3 (2019): 417–37. (link)
  • Specializes the definition of discrete homology for metric spaces from Barcelo-Capraro-White (2014) to graphs, calls it discrete cubical homology. We will use the notation \(H_n^\square(G) \) for these homology groups of a graph \(G \).
  • Proves that all trees are \(A\)-contractible
  • Proves that all hypercubes \(Q_n\) are \(A\)-contractible
  • Proves that all chordal graphs are cubical acyclic, i.e. if \(G\) is chordal, then \(H_n^\square(G) = 0 \) for all \(n \geq 1\).
  • Proves that complete bipartite graphs are cubical acyclic
  • Proves that discrete cubical homology and path homology do not always agree. Also shows that the Greene Sphere graph has nontrivial \(H_2^\square\) (Theorem 6.1).
(2020) Higher Discrete Homotopy Groups of Graphs by Bob Lutz.
  • Algebraic Combinatorics 4, no. 1 (2021): 69–88. (link)
  • The main theorem of this paper is the following: Suppose that \(G \) is a graph without 3 or 4-cycles. Then \(A_n(G,x) = 0 \) for every \(n \geq 2 \) and \(x \in G \).
  • This result is the homotopy group analogue of a similar theorem proved by Barcelo, Greene, Jarrah and Welker for cubical homology.
  • This result can nowadays be proved using the covering space theory developed in [Kapulkin-Mavinkurve (2025)](https://doi.org/10.1016/j.aam.2024.102838). Indeed, a graph with no 3 or 4-cycles has a forest for an universal cover. Kapulkin-Mavinkurve prove that the universal cover induces an isomorphism on higher homotopy groups, proving the theorem, as forests can easily be shown to have zero higher A-homotopy groups.
(2021) On the Vanishing of Discrete Singular Cubical Homology for Graphs by Hélène Barcelo, Curtis Greene, Abdul Salam Jarrah, and Volkmar Welker.
  • SIAM Journal on Discrete Mathematics, 2021 (link)
  • This paper is about a very impressive result that says that if a graph \(G\) has no 3 or 4-cycles, then its higher discrete cubical homology vanishes: \(H_n^{\square}(G) = 0\) for \(n \geq 2\). The proof is quite involved. The idea is to lift a cube to the universal cover, subdivide it, and then map it back down to the graph, crafting a homotopy equivalence between the singular n-cube chain complex and a subcomplex consisting of cubes whose image has cardinality less than 2.
(2024) Cubical Setting for Discrete Homotopy Theory, Revisited by Krysztof Kapulkin and Daniel Carranza
  • Compositio Mathematica 160, no. 12 (2024): 2856–903. (link)
  • This paper proved the following conjecture from [Babson, Barcelo,Longueville and Laubenbacher (2006)](https://doi.org/10.1007/s10801-006-9100-0): Given a graph \(G\), there exists a topological space \(X_G\) such that \(A_n(G) \cong \pi_n(X_G) \) for all \(n \geq 0\).
  • Kapulkin-Carranza prove this by crafting a cubical nerve functor from graphs to cubical sets. After some very involved calculations, they show that this cubical nerve is a cubical Kan complex, and can transfer a category of fibrations structure over to graphs, and prove that the homotopy groups of this cubical Kan complex are precisely the A-homotopy groups. This gives a powerful tool to study the A-homotopy groups of a graph, but this cubical nerve functor is still very hard to study. Even for the simplest graphs, it is wildly huge, with nondegenerate cells in every dimension (consider the map \(Q_n \to K_2 \) that takes the logical sum 0 + 0 = 1 + 1 = 0, 0 + 1 = 1 + 0 = 1, this is a nondegenerate graph map that is nondegenerate in every dimension).
(2025) The Fundamental Group in Discrete Homotopy Theory by Krysztof Kapulkin and Udit Mavinkurve
  • Advances in Applied Mathematics 164 (March 2025): 102838 (link)
  • Gives a very nice account of covering theory for graphs, improving upon previous accounts, and crafting a universal cover for graphs that may have 3 or 4-cycles. Is able to construct for any finitely presented group A a graph G whose fundamental group is \(\pi_1(G) = A \). However, it is unknown what the higher homotopy groups of this construction are.
(2025) The Lifting Properties of A-Homotopy Theory by Rachel Morrill
(2025) Mapping Fiber, Loop and Suspension Graphs in Naive Discrete Homotopy Theory by Rachel Morrill

Path Homology or GLMY theory

The GLMY (Giro)

(2012) Homologies of Path Complexes and Digraphs by Alexander Grigoyan, Yong Lin, Yuri Muranov, Shing-Tung Yau

Čech Closure Spaces and Pseudotopological Spaces

(2021) Eilenberg-Steenrod homology and cohomology theories for Čech's closure spaces by Peter Bubenik and Nikola Milićevic
(2021) Homotopy, homology, and persistent homology using closure spaces by Peter Bubenik and Nikola Milićevic
  • J. Appl. Comput. Topol. 8 (2024), no. 3, 579-641 (link)