Ph.D Thesis | |

Ph.D Student | Lew Alan |
---|---|

Subject | Studies in Topological Combinatorics |

Department | Department of Mathematics |

Supervisor | PROF. Roy Meshulam |

Let *X* be a simplicial complex.
*X* is called *d*-Leray if the homology groups of any induced
subcomplex of *X* vanish in dimensions *d* and higher. *X* is
called *d*-collapsible if it can be reduced to the void complex by
sequentially removing a simplex of size at most *d* that is contained in a
unique maximal face. *X* is called *d*-representable if it is the
nerve of a family of convex sets in *R ^{d}*. It was shown by
Wegner that any

In this thesis we study different
combinatorial, topological and geometric aspects of simplicial complexes and
the relations between them. We focus in particular on the notions of *d*-Lerayness,
*d*-collapsibility and *d*-representability.

First, we prove some general upper
bounds on the collapsibility of a complex *X* (the minimum integer *d*
such that *X* is *d*-collapsible). We then apply these bounds to
several families of simplicial complexes related to different properties of
graphs and hypergraphs. As an application, we obtain some old and new results
concerning "rainbow independent sets" in graphs.

Inspired by results of Montejano and
Oliveros, we study the *t*-tolerance complex of a complex *X*. This
is the complex whose simplices are formed as the union of a simplex in *X*
and a set of size at most *t*. We show that, for any *t* and *d*,
there is a function *h(t,d)* such that the *t*-tolerance complex of
any *d*-collapsible complex is *h(t,d)-*Leray.

Next, we study the *d*-boxicity
of a simplicial complex *X*, which is the minimal *k* such that *X*
can be written as the intersection of *k* *d*-representable
complexes. This is an extension of the classical notion of boxicity of graphs
introduced by Roberts. We prove tight upper bounds and corresponding lower
bounds on the *d*-boxicity of simplicial complexes with *n* vertices,
improving upon previous work by Witsenhausen. We also present a related
conjecture about the representability of complexes on *n* vertices.

Finally, we study certain complexes
associated to linear and affine spaces over finite fields: we investigate the
topology of the complex of line-free sets in a finite affine plane and its
relation to blocking sets having certain stability properties, and we study the
asymptotic behavior of the Laplacian eigenvalues of complexes of flags in *F _{q}^{n} *, settling a special case of a
conjecture of Papikian.