Aspects of Random Simplicial Complexes

In recent years there is a growing interest in higher dimensional random complexes, both as natural extensions of random graphs, and as potential tools for new applications. We will focus on relatively new models of random complexes and their generic topological properties:

1. A classical theorem of Alon and Roichman asserts that the Cayley graph C(G,S) of a group G with respect to a logarithmic size random subset S of G is a good expander. We consider a k-dimensional analogue of Cayley graphs, called Balanced Cayley Complexes, discuss the spectral gap of their (k-1)-Laplacian and in particular obtain a high dimensional version of the Alon-Roichman theorem.

2. A permutation complex is the order complex of the intersection of two linear orders. We describe some properties of these complexes and discuss bounds on the probability that a permutation complex associated with random orders is topologically k-connected.

Joint work with Omer Moyal.

3. A classical result of Erdos and Gallai asserts that a graph G=(V,E) with |E|> k(|V|-1)/2 must contain a simple cycle of length at least k+1. We describe a high dimensional qualitative version of this result and discuss some questions that arise in the random setting.

Joint work with Ilan Newman and Yuri Rabinovich.