Reference for Hypergraph Expander Mixing Lemma Generalization

156 Views Asked by At

Wikipedia lists a hypergraph generalization of the expander mixing lemma as follows.

Let $H$ be a $k$-uniform hypergraph, i.e. a hypergraph in which every "edge" is a tuple of $k$ vertices. For any choice of subsets $V_1,\ldots,V_k$ of vertices, $$\left||e(V_1,\ldots,V_k)| - \frac{k!|E(H)|}{n^k}|V_1|\cdots|V_k|\right| \le \lambda_2(H)\sqrt{|V_1|\cdots|V_k|}.$$

However, the reference listed for it by Friedman and Widgerson doesn't appear to (at least explicitly) state such a theorem. Is there a different reference someone could suggest, or explanation of how Friedman's paper does show such a theorem? Thanks!

1

There are 1 best solutions below

0
On BEST ANSWER

If you want some background on the mixing lemma in hypergraph settings, you should have a look at Inverse Expander Mixing for Hypergraphs, section 3, by Cohen et al. It includes some interesting points (e.g. the eigenvalue $\lambda_2$ does not correspond to any matrix).

Then, Eigenvalues and linear quasirandom hypergraphs includes a proof of the statement.