Abstract:

The $\mathcal{I}(n, k)$ is a generative model of random almost $k$-regular graphs, where graphs are constructed from $k$ randomly permuted perfect matchings on the vertex set $[n]$. We show that the likelihood of a graph $G$ drawn from $ \mathcal{I}(n, k)$ being disconnected is bounded by $O(n^{-k+2})$.
Based on this observation, we establish a threshold property for hypergraph connectedness within almost $k$-regular $d$-dimensional complexes, as introduced by Abu-Fraiha (2016). Specifically, these complexes are almost surely hypergraph connected when $k > d+1$, while the probability of disconnection decreases with $k$ for $k \leq d$.
Additionally, we demonstrate that for random 2-dimensional simplicial complexes (the model for general $d$ was introduced by Lubotzky, Luria, and Rosenthal (2019)), where the 1-cells are bounded by a degree of $k$, the complex is almost surely homologically connected over $\mathbb{Z}_2$ when $k=371$.
Advisor: Prof. Roy Meshulam