Ph.D Thesis

Ph.D StudentLew Alan
SubjectStudies in Topological Combinatorics
DepartmentDepartment 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 Rd.  It was shown by Wegner that any d-representable complex is d-collapsible and any d-collapsible complex is d-Leray. Moreover, many combinatorial properties of families of convex sets are known to follow from the d-Lerayness or d-collapsibility of the nerve of the family.

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 Fqn , settling a special case of a conjecture of Papikian.