M.Sc Thesis | |

M.Sc Student | Abu-Fraiha Amir |
---|---|

Subject | Homology of Random Simplicial Complexes Based on Steiner Systems |

Department | Department of Mathematics |

Supervisor | PROF. Roy Meshulam |

Full Thesis text |

Random complex theory is a natural multidimensional generalization of the classical random graph theory.

The first random model for graphs, the *G(n,p)*
model, was introduced by Erdős and Rényi in 1959. *G(n,p)* is
the probability space of all graphs on the vertex set *[n]* with
independent edge probability *p*. This model plays an
important role in random graph theory, and among the classical results
concerning it are the threshold probability functions for various graph properties
such as connectivity and emergence of a giant component. These results
have many applications in the fields of theoretical computer science and
statistical physics.

Recently, there is a growing interest in
multidimensional models generalizing* **G(n,p)*. These models use simplicial complexes as a
high-dimensional analogue of graphs.

Following the *G(n,p)* model,
other random graph models were introduced. One of these models is the *I(n**,**d)* model, which generates *d*-regular graphs with high probability
by taking *d* random perfect matchings on the vertex
set *[n]*.* *A known fact concerning this model asserts that if *d≥
3* then *G**𝜖 **I(n,**d)* is asymptotically almost surely (a.a.s.)
connected.

In this work we present *S**k **(n,**d)*, a *k*-dimensional generalization of *I(n**,**d),* and
study its topology. A complex *X**ϵ
**S**k **(n,**d)* is constructed by taking the union of *d*
random permutations of a specific Steiner system of type* **S(k,**k 1,**n)*. We prove the following result concerning this model.

**Theorem 1.2.** Fix *k≥1*. There exists a constant *c(k)*,
depending only on

*k*, such that

*lim **Pr [**Xϵ** **S**k **(n,**d) : H̃**k-1(X;**ℝ)=0] = 1*

* **n→∞*

for any d≥c(k).
Furthermore, *c(k)≤(3 2√2)k*^{2}*.*

The main tool in the proof of Theorem 1.2, the
Garland method, raises the question of bounding *β̃**k-1(X;**ℝ)* in terms of the homology of various links.
In this direction we prove the following result:

Let *X* be a
simplicial complex. Let *K* be a fixed field and let* β̃**j(X) = β̃**j(X;**K) = *dim_{K}H̃*j(X;**K)* be the Betti numbers of *X* over *K*.
For 0≤ℓ and -1≤ j
let

*λ*_{ℓ}_{, j}(X) = *∑ β̃**j(*lk*(X,**𝜏)).*

*
*^{τϵ}^{X(}^{ℓ}^{)}

~~ ~~

**Theorem 1.
3.** Let *0**≤ℓ** < k *and suppose *X* is a complex on *n*
vertices containing the full *(k-1)*-skeleton satisfying *𝜆 _{ℓ}_{, k-}*

*β̃**k-1(X)* ≤ *B _{n,k,}*

where *B _{n,k,}*

We further prove results concerning the cases of equality in Theorem 1.3.