There are a lot of recent works on generalizing the spectral theory of graphs and graph partitioning to \(k\)-uniform hypergraphs. There have been two broad directions toward this goal. One generalizes the notion of graph conductance to hypergraph conductance [LM16, CLTZ18]. In the second approach one can view a hypergraph as a simplicial complex and study its various topological properties [LM06, MW09, DKW16, PR17] and spectral properties [KM17, DK17, KO18a, KO18b, Opp18].
In this work, we attempt to bridge these two directions of study by relating the spectrum of up-down walks and swap-walks on the simplicial complex to hypergraph expansion. In surprising contrast to random-walks on graphs, we show that the spectral gap of swap-walks and up-down walks between level \(m\) and \(l\) with \(1 < m \leq l\) can not be used to infer any bounds on hypergraph conductance. Moreover, we show that the spectral gap of swap-walks between \(X(1)\) and \(X(k-1)\) can not be used to infer any bounds on hypergraph conductance, whereas we give a Cheeger-like inequality relating the spectral of walks between level \(1\) and \(l\) for any \(l \leq k\) to hypergraph expansion. This is a surprising difference between swaps-walks and up-down walks!
Finally, we also give a construction to show that the well-studied notion of link expansion in simplicial complexes can not be used to bound hypergraph expansion in a Cheeger like manner.
[arXiv]