טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAmir Abu-Fraiha
SubjectHomology of Random Simplicial Complexes Based on
Steiner Systems
DepartmentDepartment of Mathematics
Supervisor Full Professor Meshulam Roy
Full Thesis textFull thesis text - English Version


Abstract

    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 Sk (n,d), a k-dimensional generalization of I(n,d), and study its topology. A complex Xϵ Sk (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ϵ Sk (n,d) : H̃k-1(X;)=0] = 1

                                                             n→∞

for any d≥c(k). Furthermore, c(k)≤(3 2√2)k2.


    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) = dimKj(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--2(X)=0. Then

β̃k-1(X)Bn,k, ,

where Bn,k,  is a constant depending n, k and .


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