The notion of expansion has been one of the most effective ways to quantify connectivity in graphs, with applications throughout theoretical computer science. However, generalizing this notion to hypergraphs has been extremely challenging, and the most natural generalization has not proven helpful for applications such as algorithm design, coding, hardness of approximation, and pseudorandomness. Recently, local spectral expansion (also known as high-dimensional expansion) has emerged as a promising notion of expansion in hypergraphs.
In this talk, we will first look at the notion of local spectral expansion (and a related notion called approximate product space) through the lens of 'pseudoindependence'. To this end, we will define the notion of simplicial complexes and walks on them and briefly examine the relation between their spectra and local spectral expansion. We will end this exposition with a discussion of the celebrated trickle-down theorem.
Then, to firmly establish local spectral expansion as a useful relaxation of independence, we will look at a few versions of the Chernoff bounds for approximate product spaces and local spectral expansion. The proof for approximate product spaces will be through a direct bound on the moment generating function (MGF). The bound for the case of local spectral expansion will be through a bound on the variance, giving us a bound on the second derivative of the log-MGF.
Finally, we will look at a few constructions of sparse local spectral expanders.
