Homological connectivity

In algebraic topology, homological connectivity is a property describing a topological space based on its homology groups. This property is related, but more general, than the properties of graph connectivity and topological connectivity. There are many definitions of homological connectivity of a topological space X.[1]

Definitions

Basic definitions

X is homologically-connected if its 0-th homology group equals Z, i.e. ${\displaystyle H_{0}(X)\cong \mathbb {Z} }$, or equivalently, its 0-th reduced homology group is trivial: ${\displaystyle {\tilde {H_{0}}}(X)\cong 0}$. When X is a graph and its set of connected components is C, ${\displaystyle H_{0}(X)\cong \mathbb {Z} ^{|C|}}$ and ${\displaystyle {\tilde {H_{0}}}(X)\cong \mathbb {Z} ^{|C|-1}}$ (see graph homology for details). Therefore, homological connectivity is equivalent to the graph having a single connected component, which is equivalent to graph connectivity. It is similar to the notion of a connected space.

X is homologically 1-connected if it is 1-connected, and additionally, its 1-th homology group is trivial, i.e. ${\displaystyle H_{1}(X)\cong 0}$.[1] When X is a connected graph with vertex-set V and edge-set E, ${\displaystyle H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+1}}$. Therefore, homological 1-connectivity is equivalent to the graph being a tree. Informally, it corresponds to X having no 1-dimensional "holes", which is similar to the notion of a simply connected space.

In general, for any integer k, X is homologically k-connected if its reduced homology groups of order 0, 1, ..., k are all trivial. Note that the reduced homology group equals the homology group for 1,..., k (only the 0-th reduced homology group is different).

The homological connectivity of X, denoted conn_H(X), is the largest k for which X is homologically k-connected. If all reduced homology groups of X are trivial, then conn_H(X) is defined as infinity.

Variants

Some authors define the homological connectivity shifted by 2, i.e., ${\displaystyle \eta _{H}(X):={\text{conn}}_{H}(X)+2}$. [2]

The basic definition considers homology groups with integer coefficients. Considering homology groups with other coefficients leads to other definitions of connectivity. For example, X is F₂-homologically 1-connected if its 1st homology group with coefficients from F₂ (the cyclic field of size 2) is trivial, i.e.: ${\displaystyle H_{1}(X;\mathbb {F} _{2})\cong 0}$.

Homological connectivity in specific spaces

Homological connectivity was calculated for various spaces, including:

• The independence complex of a graph;[3][4]
• A random 2-dimensional simplicial complex;[1]
• A random k-dimensional simplicial complex;[5]
• A random hypergraph;[6]
• A random Čech complex.[7]

Meshulam's game

Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex of a graph. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv.[8][9]

The game-board is a graph G. It is a zero-sum game for two players, CON and NON. CON wants to show that I(G), the independence complex of G, has a high connectivity; NON wants to prove the opposite.

At his turn, CON chooses an edge e from the remaining graph. NON then chooses one of two options:

• Deletion – remove the edge e from the graph.
• Explosion – remove both endpoints of e, together with all their neighbors and the edges incident to them.

The score of CON is defined as follows:

• If at some point the remaining graph has an isolated vertex, the score is infinity;
• Otherwise, at some point the remaining graph contains no vertex; in that case the score is the number of explosions.

For every given graph G, the game value on G (i.e., the score of CON when both sides play optimally) is denoted by Ψ(G).

Meshulam[3] proved that, for every graph G, the homological connectivity of I(G) is at least Ψ(G).

References

1. Linial*, Nathan; Meshulam*, Roy (2006-08-01). "Homological Connectivity Of Random 2-Complexes". Combinatorica. 26 (4): 475–487. doi:10.1007/s00493-006-0027-9. ISSN 1439-6912.
2. Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-10-01). "On a conjecture of Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. doi:10.1007/s12188-016-0160-3. ISSN 1865-8784.
3. Meshulam, Roy (2003-05-01). "Domination numbers and homology". Journal of Combinatorial Theory, Series A. 102 (2): 321–330. doi:10.1016/s0097-3165(03)00045-1. ISSN 0097-3165.
4. Adamaszek, Michał; Barmak, Jonathan Ariel (2011-11-06). "On a lower bound for the connectivity of the independence complex of a graph". Discrete Mathematics. 311 (21): 2566–2569. doi:10.1016/j.disc.2011.06.010. ISSN 0012-365X.
5. Meshulam, R.; Wallach, N. (2009). "Homological connectivity of random k-dimensional complexes". Random Structures & Algorithms. 34 (3): 408–417. doi:10.1002/rsa.20238. ISSN 1098-2418.
6. Cooley, Oliver; Haxell, Penny; Kang, Mihyun; Sprüssel, Philipp (2016-04-04). "Homological connectivity of random hypergraphs". arXiv:1604.00842 [math].
7. Bobrowski, Omer (2019-06-12). "Homological Connectivity in Random \v{C}ech Complexes". arXiv:1906.04861 [math].
8. Aharoni, Ron; Berger, Eli; Ziv, Ran (2007-05-01). "Independent systems of representatives in weighted graphs". Combinatorica. 27 (3): 253–267. doi:10.1007/s00493-007-2086-y. ISSN 0209-9683.
9. Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-01-04). "On a conjecture of Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. doi:10.1007/s12188-016-0160-3. ISSN 0025-5858.