Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Homological connectivity of random graphs

Algebra & Discrete Mathematics

Speaker: Eric Babson, UC Davis
Location: 2112 MSB
Start time: Mon, Feb 11 2019, 12:10PM

Consider a random graph with edge probabilities shrinking slowly to zero as a function of the number of vertices. The clique simplicial complex of such a graph will very likely be connected and the connectivity is the number of vertices which must be lost to disconnect it. Bollobas and Thomasson proved that this is very likely the smallest degree of a vertex and isolating that vertex is the easiest way for the graph to become disconnected. We show that the same thing happens with the first homology: This group is very likely trivial and remains so with the loss of fewer vertices than the smallest degree of an edge (the number of vertices adjacent to both ends) with the easiest way for the graph to obtain first cohomology being to lose the neighbors of an edge so that it supports a cocycle. One motivation for this failure analysis arises from looking at the Stanley-Reisner module generated by the edges not in graph. The bigraded Betti numbers are by Hochster's formula given by the ranks of homology groups of the clique complex with some vertices lost so that the minimum number whose loss gives a nonzero group constitutes a cohomological vanishing for the module. It seems likely (and we conjecture) that the same picture holds for each fixed cohomological dimension.