\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsthm,amsmath,amssymb} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \usepackage{mathtools} \mathtoolsset{showonlyrefs} \usepackage{tikz} \usepackage{caption} \usepackage{subcaption} \usepackage[numbers]{natbib} \usetikzlibrary{calc} \usepgflibrary{shapes.geometric} \usetikzlibrary{decorations.markings} \tikzstyle{vertex}=[draw,circle,fill=black,minimum size=5pt, inner sep=0pt, outer sep=0pt,text=white,line width=0mm] \tikzset{->-/.style={decoration={markings, mark=at position #1 with {\arrow[scale=1.7, xshift=1.5pt]{stealth}}},postaction={decorate}}} \tikzset{->-/.default=0.5} \newcommand{\convexpath}[2]{ % Syntax: \draw \convexpath{v1, v2, v3,...}{radius}; [ create hullcoords/.code={ \global\edef\namelist{#1} \foreach [count=\counter] \nodename in \namelist { \global\edef\numberofnodes{\counter} \coordinate (hullcoord\counter) at (\nodename); } \coordinate (hullcoord0) at (hullcoord\numberofnodes); \pgfmathtruncatemacro\lastnumber{\numberofnodes+1} \coordinate (hullcoord\lastnumber) at (hullcoord1); }, create hullcoords ] ($(hullcoord1)!#2!-90:(hullcoord0)$) \foreach [ evaluate=\currentnode as \previousnode using {\currentnode-1}, evaluate=\currentnode as \nextnode using {\currentnode+1} ] \currentnode in {1,...,\numberofnodes} { let \p1 = ($(hullcoord\currentnode) - (hullcoord\previousnode)$), \p2 = ($(hullcoord\nextnode) - (hullcoord\currentnode)$), % \n1 = {atan2(\y1,\x1) + 90}, % \n2 = {atan2(\y2,\x2) + 90}, %%% If this looks odd when you compile it, try exchanging the preceding two lines with the following two lines. %%% \n1 = {atan2(\x1,\y1) + 90}, \n2 = {atan2(\x2,\y2) + 90}, \n{delta} = {Mod(\n2-\n1 - .001,360) - 360 + .001} in {arc [start angle=\n1, delta angle=\n{delta}, radius=#2]} node {} -- ($(hullcoord\nextnode)!#2!-90:(hullcoord\currentnode)$) } } \newcommand{\Q}{{\mathbb Q}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\N}{{\mathbb N}} \newcommand{\R}{{\mathbb R}} \newcommand{\C}{{\mathbb C}} \newcommand{\ep}{{\varepsilon}} \newcommand{\ones}{\vec{1}} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator*{\E}{E} \DeclareMathOperator*{\Var}{Var} \newcommand{\defeq}{\vcentcolon=} \DeclarePairedDelimiter{\set}{\{}{\}} \DeclarePairedDelimiterX{\innerprod}[2]{\langle}{\rangle}{#1,#2} \DeclarePairedDelimiter{\size}{\lvert}{\rvert} \DeclarePairedDelimiter{\abs}{\lvert}{\rvert} \DeclarePairedDelimiter{\norm}{\lVert}{\rVert} \DeclarePairedDelimiter{\parens}{(}{)} \DeclarePairedDelimiter{\bracks}{[}{]} \DeclarePairedDelimiter{\ceil}{\lceil}{\rceil} \newcommand{\sumstrut}{\vphantom{\sum_{S^2_y}}} \newcommand{\ssumstrut}{\vphantom{\sum_{\substack{S^2_y\\S^2_y}}}} \newcommand{\usumstrut}{\vphantom{\sum^{S^2_y}}} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \title{\bf Inverse Expander Mixing for Hypergraphs} %\author{Emma Cohen\thanks{research supported in part by the NSF grants DMS 1101447 and 1407657} \qquad Peter Ralli\footnotemark[1] \qquad Prasad Tetali\footnotemark[1] \\ %\small School of Mathematics and School of Computer Science\\[-0.8ex] %\small Georgia Institute of Technology, USA\\ %\small\tt \{ecohen32, pralli3, tetali\}@math.gatech.edu\\ %\and %Dhruv Mubayi\thanks{research supported in part by the NSF grants DMS 0969092 and 1300138}\\ %\small Department of Mathematics, Statistics, and Computer Science\\[-0.8ex] %\small University of Illinois at Chicago, USA\\ %\small\tt mubayi@uic.edu %} \author{Emma Cohen\thanks{Research supported in part by the NSF grants DMS 1101447 and 1407657.} \\ \small School of Mathematics\\[-0.8ex] \small Georgia Institute of Technology, USA\\ \small\tt ecohen@gatech.edu\\ \and Dhruv Mubayi\thanks{Research supported in part by the NSF grants DMS 0969092 and 1300138.}\\ \small Department of Mathematics, \\[-0.8ex]\small Statistics, and Computer Science\\[-0.8ex] \small University of Illinois at Chicago, USA\\ \small\tt mubayi@uic.edu \and Peter Ralli\footnotemark[1] \\ \small School of Mathematics\\[-0.8ex] \small Georgia Institute of Technology, USA\\ \small\tt pralli@gatech.edu\\ \and Prasad Tetali\footnotemark[1] \\ \small School of Mathematics and \\[-0.8ex]\small School of Computer Science\\[-0.8ex] \small Georgia Institute of Technology, USA\\ \small\tt tetali@math.gatech.edu\\ } \date{\dateline{May 28, 2015}{Feb. 24, 2016}\\ \small Mathematics Subject Classifications: 05C50, % Graphs and linear algebra 05C65, % Hypergraphs 05E45 % Combinatorial aspects of simplicial complexes } \begin{document} \maketitle \begin{abstract} We formulate and prove inverse mixing lemmas in the settings of simplicial complexes and $k$-uniform hypergraphs. In the hypergraph setting, we extend results of Bilu and Linial for graphs. In the simplicial complex setting, our results answer a question of Parzanchevski et al. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Beginning with the seminal works of Thomason \cite{T} and Chung-Graham-Wilson \cite{CGW} the theory of quasirandom graphs has served as an important tool in graph theory and the study of random structures. Their work showed that many graphs share a collection of common properties, including local properties like subgraph counts, and global properties like edge distribution and eigenvalues. The connection between these different concepts has proved to be an invaluable tool in graph theory and computer science over the past two decades. Even the recent theory of graph limits has borrowed many insights from quasirandom graphs \cite{Lov12}. A fundamental result in this theory is the quantitative relationship between spectral and expansion properties of a graph. Although early versions of this were proved by Tanner \cite{Tan84} and Alon \cite{Alon86}, the formulation of the result below, which has been termed as the Expander Mixing Lemma for graphs, is perhaps the most popular one. For a graph $G$, let $\lambda(G)$ be the second largest eigenvalue, in absolute value, of the adjacency matrix $A(G)$. \begin{theorem}[Expander Mixing Lemma for graphs, \citet{AC}] \label{thm:mixing_graph} If $G$ is an $r$-regular graph then for any $S,T\subseteq V(G)$, \begin{equation} \abs*{E(S,T)-\tfrac{r}{n}\size{S}\size{T}} \leq \lambda(G)\sqrt{\size{S}\size{T}}, \end{equation} where $E(S,T)$ is the number of $(s, t) \in S\times T$ such that $st \in E(G)$. \end{theorem} The converse to Theorem~\ref{thm:mixing_graph} is essentially a question about approximating certain quadratic forms on the sphere by points in a cube. This was achieved by Bilu and Linial \cite{BL} who proved the following converse to the Expander Mixing Lemma. \begin{theorem}[Inverse Mixing Lemma for graphs, \citet{BL}] \label{thm:inverse_mixing_graph} If $G$ is an $r$-regular graph such that for every disjoint $S,T\subset V(G)$ \begin{equation} \abs*{E(S,T)-\tfrac{r}{n}\size{S}\size{T}} \leq \rho\sqrt{\size{S}\size{T}}, \end{equation} then \begin{equation} \lambda(G) = O(\rho\,(\log(r/\rho)+1)). \end{equation} \end{theorem} \begin{remark} This theorem is a converse to the mixing lemma. However, we borrow the language used in \cite{PRT13}, and we refer to this as the Inverse Mixing Lemma. \end{remark} Soon after the initial papers on quasirandom graphs, quasirandom properties of other structures were investigated including $k$-uniform hypergraphs for fixed $k \ge 2$ \cite{ChungGraham}. It was quickly observed by Chung, Graham, and R\"odl that there could be no straightforward generalization of the theory of quasirandom graphs to hypergraphs. Over the past two decades, many researchers have extended and generalized parts of the theory and today the situation for hypergraphs is much more satisfactory \cite{Chung12, FW, KNRS, CHPS, LM1, LM2, Towsner13}. In particular, the recent work in \cite{LM} defines a hypergraph eigenvalue that originated in the work of Friedman and Wigderson \cite{FW}. An analogue of Theorem \ref{thm:mixing_graph} was already proved in \cite{FW}, and this was extended to more general situations in \cite{LM}. In the present work, we prove a converse (Theorem \ref{thm:inverse_mixing_hypergraph}) to the mixing lemma for hypergraphs, in other words, a hypergraph version of Theorem \ref{thm:inverse_mixing_graph}. Another direction in which the theory of quasirandom graphs has developed is to simplicial complexes. Indeed, the connection between topological combinatorics and random graphs is proving to be a fruitful and successful area of current research \cite{K}. Inspired by the success of Cheeger-type inequalities in graphs---relating isoperimetry (namely, vertex and edge expansion of a graph) to spectral information (eigenvalues of the Laplacian of the graph)---along with the aforementioned expander mixing lemmas in graphs and hypergraphs, several researchers have initiated developing such connections in the simplicial complex settings. Indeed, in recent work Parzanchevski, Rosenthal, and Tessler \cite{PRT13} proved an expander mixing lemma for simplicial complexes (of arbitrary dimension), possessing a complete skeleton. (See also an independent development by Steenbergen, Klivans and Mukerjee \cite{SKM12}.) In subsequent work Parzanchevski \cite{P13} extended this development by removing the assumption of a complete skeleton and showing that concentration of spectra of the so-called Hodge Laplacian in all dimensions implies combinatorial expansion in any complex. An important question left open by Parzanchevski et al was whether a {\em converse} to the expander mixing lemma of theirs held true, much in the spirit of the Bilu-Linial converse \cite{BL} to the mixing lemma of Alon-Chung \cite{AC}. Our first main theorem in this work (Theorem \ref{thm:inverse_mixing_simplicial}) provides an answer to this question, by way of an {\em inverse mixing lemma} for simplicial complexes. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Simplicial Complex Setting} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Our main result for simplicial complexes (Theorem \ref{thm:inverse_mixing_simplicial}) requires some notation and preliminaries which are discussed in the next section. %%%%%%%%%%%% \subsection{Notation for simplicial complexes} %%%%%%%%%%%% For a fuller discussion of notation and preliminaries, refer to \cite{PRT13}. Throughout, let $X$ be a $d$-dimensional simplicial complex with vertex set $V$ of size $n$. Let $X^i$ denote the set of $i$-cells of $X$, where an $i$-cell consists of $i+1$ vertices so that the simplex defined by these points has dimension $i$. The simplicial complex $X$ is said to have a \emph{complete skeleton} if $X^i = \binom{V}{i}$ for each $i = 0, \dots, d-1$. Note that a $d$-dimensional simplicial complex with a complete skeleton is essentially the same as a simple $(d+1)$-uniform hypergraph (as each is given by a subset of $\binom{V}{d+1}$). For any subsets $S_0,\dots,S_d\subseteq V$, we write $F(S_0,\dots,S_d)$ for the number of ordered tuples $(s_0, \ldots, s_d) \in S_0\times \dots \times S_d$ such that $\{s_0, \ldots, s_d\} \in X^d$. If $i > 0$, an $i$-cell $\set{\sigma_0,\dots,\sigma_i}$ has two orientations given by the orderings of its vertices up to an even permutation. Denote one orientation by $\sigma = (\sigma_0,\dots,\sigma_i)$ and the other orientation by $\overline{\sigma}$. Let $X^i_{\pm}$ denote the set of all oriented $i$-cells. Sometimes, abusing this notation, we also use $\sigma$ to refer to the {\em unoriented} $i$-cell which corresponds to the oriented $i$-cells $\sigma$ and $\overline{\sigma}$. If $\sigma$ is an oriented $i$-cell and $v\in V-\sigma$, we write $v\sigma$ for the oriented $(i+1)$-cell $(v,\sigma_0,\dots,\sigma_i)$ and we say $v\sim \sigma$ if and only if $v\sigma\in X^{i+1}$. For $\sigma\in X^{d-1}$ write $\deg(\sigma) \defeq \size{\{v\in V\,:\, v\sim \sigma\}}$ for its degree, and say that $X$ is \emph{$r$-regular} if $\deg(\sigma) = r$ for all $\sigma\in X^{d-1}$. \begin{definition} Let $\Omega^i$ be the vector space of real-valued, skew-symmetric functions on $X^i_{\pm}$, i.e., functions $f:X^i_{\pm}\to\R$ so that $f(\overline{\sigma}) = -f(\sigma)$ for all $\sigma \in X^i_{\pm}$. \end{definition} For example, we can think of $\Omega^0$ as the set of vertex weightings, and $\Omega^1$ as the set of flow functions. \begin{definition} Define an inner product on $\Omega^i$ by \begin{align} \innerprod*{f}{g} \defeq \sum_{\sigma\in X^i} f(\sigma)g(\sigma), \end{align} noting that $f(\sigma)g(\sigma)=f(\overline{\sigma})g(\overline{\sigma})$, and that we only take one of these terms in the sum. \end{definition} With this inner product comes an associated norm $\norm{f} \defeq \sqrt{\innerprod*{f}{f}}$ on $\Omega^i$. Recall that for an operator $M:\Omega^i\to \Omega^i$ (or on any normed vector space) we also have an operator norm, \begin{align} \norm{M} \defeq \sup_{\substack{f\in \Omega^i\\ f\neq 0}} \frac{\norm{Mf}}{\norm{f}}. \end{align} \begin{definition} Define the \emph{boundary operator} $\partial_{d-1}:\Omega^{d-1}\to \Omega^{d-2}$ by \begin{align} (\partial_{d-1}f)(\tau) \defeq \sum_{v\sim \tau} f(v\tau), \end{align} and let $Z_{d-1} \defeq \ker\partial_{d-1}$. \end{definition} The boundary of a weight function is the total weight of vertices, while the boundary of a flow is the function that assigns to each vertex the net flow at that vertex. Correspondingly, $Z_0$ is the set of vertex-weightings with weights summing to 0, while $Z_1$ is the set of conservative flows. \begin{definition} For every $(d-2)$-cell $\tau$, define linear operators $A_{\tau}, J_\tau:\Omega^{d-1}\to \Omega^{d-1}$ by \begin{align} (A_{\tau}f)(\sigma) \defeq \begin{cases} \displaystyle\sum_{w\sim v\tau} f(w\tau) &\text{if }\sigma = v\tau\\[1.4em] \displaystyle\sum_{w\sim v\tau} f(\overline{w\tau}) &\text{if }\sigma = \overline{v\tau}\\[1.2em] 0 &\text{if }\tau\not\subset \sigma \end{cases} &&\text{\quad and \quad}&& (J_{\tau}f)(\sigma) \defeq \begin{cases} \displaystyle\sum_{w\sim \tau} f(w\tau) &\text{if }\sigma = v\tau\\[1.4em] \displaystyle\sum_{w\sim \tau} f(\overline{w\tau}) &\text{if }\sigma = \overline{v\tau}\\[1.2em] 0 &\text{if }\tau\not\subset \sigma. \end{cases} \end{align} Let $A \defeq \sum_{\tau\in X^{d-2}} A_\tau$ be the adjacency operator, and let $J \defeq \sum_{\tau \in X^{d-2}}J_\tau$ be the lower Laplacian, which is sometimes also denoted by $\Delta^-$, $\Delta^L$, or $\Delta^{down}$. Denote by $I$ the identity operator on $\Omega^{d-1}$. %% As a matrix, $A$ has a 1 in the $\sigma,\sigma'$ coordinate if $\sigma\cup\sigma'$ is a $d$-cell. \end{definition} \begin{remark} \label{rmk:matrices} We could also view these definitions in a more linear-algebraic light. For each $\sigma \in X^{d-1}$ we can choose a canonical ``positive'' orientation $\sigma = (\sigma_0, \dots, \sigma_{d-1})$, and define a set $X^{d-1}_+$ of such orientations. We identify $\Omega^{d-1}$ with the vector space $\R^{X_+^{d-1}}$ and operators such as the adjacency operator $A$ above could then be considered as matrices indexed by the canonical orientations of $i$-cells. With these identifications the inner product and norms defined above correspond to their usual counterparts. The matrix for the adjacency operator $A_\tau$ would be the signed adjacency matrix of the \emph{graph} induced on $d$-cells and $(d-1)$-cells containing $\tau$, with $w\tau\sim v\tau$ (i.e, a $\pm 1$ in the coordinate corresponding to the positive orientations of $w\tau$ and $ v\tau$) if and only if $wv\tau\in X^d$. The signs are determined by the orientations of $w\tau$ and $v\tau$ relative to the canonical positive orientations of those cells (for instance, if the positive orientations are $w\tau$ and $\overline{v\tau}$ then the entry is negative). See Figure \ref{fig:simplicial_example} for an example. Similarly, the matrix for $J_\tau$ would have a $\pm 1$ for any pair of $(d-1)$-cells (not necessarily distinct) both containing $\tau$, with the signs determined in the same fashion. More precisely, if $\sigma$, $\sigma' \in X^{d-1}$ are positively-oriented cells that differ by exactly one vertex, let $\pi_{\sigma,\sigma'}$ be the unique permutation of $\set{0,\dots,d-1}$ so that $\sigma_{\pi_{\sigma,\sigma'}(i)} = \sigma'_{i}$ whenever $\sigma'_i\in \sigma$. Then we can calculate the $\sigma,\sigma'$ entry of $A$ and $J$: \begin{align} A_{\sigma,\sigma'} = \begin{cases} \sgn(\pi_{\sigma,\sigma'}) &\text{if }\sigma\cup\sigma'\in X^d\\ 0 &\text{otherwise.} \end{cases} &&\text{\quad and\quad }&& J_{\sigma,\sigma'} = \begin{cases} \sgn(\pi_{\sigma,\sigma'}) &\text{if }\size{\sigma\cup\sigma'} = d+1,\\ d &\text{if }\sigma = \sigma'\\ 0 &\text{otherwise.} \end{cases} \end{align} \begin{figure}[t] \centering % \begin{tabular}{cc} \begin{subfigure}[b]{.2\textwidth} \begin{tikzpicture}[label distance=1mm, scale=.7] \node[vertex, label=135:1] (v1) at (0,2) {}; \node[vertex, label=45:2] (v2) at (2,2) {}; \node[vertex, label=225:3] (v3) at (0,0) {}; \node[vertex, label=315:4] (v4) at (2,0) {}; \draw \convexpath{v1, v2, v3}{3mm}; \draw \convexpath{v2, v4, v3}{2mm}; \draw \convexpath{v1, v4, v3}{4mm}; \end{tikzpicture} \caption{} \end{subfigure} & \begin{subfigure}[b]{.2\textwidth} \begin{tikzpicture}[label distance=0mm, scale=.7] \node[vertex, label=135:1] (v1) at (0,2) {}; \node[vertex, label=45:2] (v2) at (2,2) {}; \node[vertex, label=225:3] (v3) at (0,0) {}; \node[vertex, label=315:4] (v4) at (2,0) {}; \draw[->-] (v1) to (v2); \draw[->-] (v1) to (v3); \draw[->-=.65] (v1) to (v4); \draw[->-=.65] (v2) to (v3); \draw[->-] (v2) to (v4); \draw[->-] (v3) to (v4); \end{tikzpicture} \caption{} \end{subfigure} \\ \begin{subfigure}[b]{.2\textwidth} \begin{tikzpicture}[label distance=0mm, scale=.7] \node[vertex, label=135:1] (v1) at (0,2) {}; \node[vertex, label=45:2, fill=white] (v2) at (2,2) {}; \node[vertex, label=225:3] (v3) at (0,0) {}; \node[vertex, label=315:4] (v4) at (2,0) {}; \draw[-] (v1) to (v3); \draw[-] (v3) to (v4); \end{tikzpicture} \caption{} \end{subfigure} & \begin{subfigure}[b]{.2\textwidth} \begin{tabular}{c|ccc} & 12 & $\overline{32}$ & $\overline{42}$ \\\hline\\[-.9em] 12 & 0 & -1 & 0 \\ $\overline{32}$ & -1 & 0 & 1 \\ $\overline{42}$ & 0 & 1 & 0 \\ \end{tabular} \caption{} \end{subfigure} \end{tabular} \quad \begin{subfigure}[c]{.4\textwidth} \begin{tabular}{c|cccccc} & 12 & 13 & 14 & 23 & 24 & 34 \\\hline\\[-.9em] 12 & 0 & 1 & 0 & -1 & 0 & 0 \\ 13 & 1 & 0 & 1 & 1 & 0 & -1 \\ 14 & 0 & 1 & 0 & 0 & 0 & 1 \\ 23 & -1 & 1 & 0 & 0 & 1 & -1 \\ 24 & 0 & 0 & 0 & 1 & 0 & 1 \\ 34 & 0 & -1 & 1 & -1 & 1 & 0 \\ \end{tabular} \caption{} \end{subfigure} \caption{Suppose $X$ is the 2-complex containing the 2-cells shown in (a) (along with a complete skeleton not shown) and suppose we pick canonical orientations of 1-cells as in (b). The graph induced on the neighborhood of $\tau = \{2\}$ is shown in (c). The matrix $A_{\{2\}}$ indexed by canonical 1-cells containing $\{2\}$ (listed in the form $v\tau$ or $\overline{v\tau}$) is as shown in (d). Figure (e) shows the summed adjacency matrix $A$.} \label{fig:simplicial_example} \end{figure} Note that for ease of analysis positive orientations can be chosen for any \emph{particular} $\tau$ to make all of the signs in $A_\tau$ positive, but (depending on $A$) it may be impossible to maintain this property across $(d-2)$-cells $\tau$ simultaneously and so the matrix for $A$ might exhibit both signs. \end{remark} For graphs each $(d-1)$-cell has only one orientation, so we have $X^0 = V$ and $\Omega^0 = \R^V$ and we can think of the usual adjacency matrix of a graph as an operator $A:\R^V\to \R^V$. Indeed, for $d=1$ the only $(d-2)$-cell is the empty set, and so $A = A_\emptyset$ is just the adjacency matrix of the graph, while $J = J_\emptyset$ is the all-ones matrix. \begin{definition} Finally, define the \emph{degree operator} $D:\Omega^{d-1}\to\Omega^{d-1}$ by \begin{align} (Df)(\sigma) \defeq \deg(\sigma) f(\sigma), \end{align} and define $\Delta^+ \defeq D - A$. \end{definition} Note that for $d=1$, $\Delta^+$ is the graph Laplacian. %%%%%%%%%%%% \subsection{Mixing Lemmas for Simplicial Complexes} %%%%%%%%%%%% The following is a recent mixing lemma due to Parzanchevski, Rosenthal \& Tessler: \begin{theorem}[Mixing Lemma for simplicial complexes, \citet{PRT13}] \label{thm:mixing_simplicial} Let $X$ be a $d$-dimensional complex with a complete skeleton and fix $\alpha\in \R$. For any disjoint sets $S_0,\dots,S_d\subseteq V$, \begin{align} \abs*{F(S_0,\dots,S_d)-\tfrac{\alpha}{n} \size{S_0} \dots \size{S_d}} \leq \rho_{\alpha}\sqrt{\size{S_0}\size{S_1}}\size{S_2}\dots \size{S_d}, \end{align} where $\rho_{\alpha} \defeq \norm{(\alpha I-\Delta^+)|_{Z_{d-1}}}$. \end{theorem} This is not quite the statement given in the original paper, which concludes with a slightly looser but more symmetric result. Note that if $X$ is $r$-regular and $\alpha = r$ then $\rho_\alpha$ is the largest non-trivial eigenvalue of $A = r I - \Delta^+$. That is, it is the largest eigenvalue in absolute value besides the $\binom{n-1}{d-1}$ eigenvalues that must be equal to $r$. Throughout this paper, we use the common shorthand of referring to this eigenvalue as the second eigenvalue. The first result we prove is an inverse of the mixing lemma for simplicial complexes. \begin{theorem} \label{thm:inverse_mixing_simplicial} Let $X$ be an $r$-regular, $d$-dimensional complex with a complete skeleton, and suppose that for every collection of disjoint sets $S_0,\dots,S_d\subseteq V$ \begin{align} \abs*{F(S_0,\dots,S_d)-\tfrac{r}{n}\size{S_0}\dots \size{S_d}} \leq \rho\sqrt{\size{S_0}\size{S_1}} \size{S_2}\dots \size{S_d}. \end{align} Then \begin{align}\label{eqn:simplicial_rho} \norm*{A|_{Z_{d-1}}} = O\big(\rho d (\log\tfrac{r}{\rho}+1)\big). \end{align} \end{theorem} Again, when the complex is regular with a complete skeleton this quantity is the second-largest eigenvalue of $A$. \begin{remark} It is possible to generalize this result by replacing the $r$ in \eqref{eqn:simplicial_rho} with an arbitrary value $\alpha\in \R$, and by replacing $A$ with $\alpha I - \Delta^+$, as in the statement of Theorem \ref{thm:mixing_simplicial}. \end{remark} \begin{remark} In our proof, we do not use the full strength of the hypothesis. In fact, we will always take $S_2,\dots, S_d$ to be singletons. \end{remark} \begin{remark} Our proof makes use of the ``local-to-global'' technique which is common in the theory of higher-dimensional Laplacians, which was introduced in \cite{G}. \end{remark} \begin{proof}[Proof of Theorem \ref{thm:inverse_mixing_simplicial}] It is clear from the graph interpretation of $A_\tau$ that the largest eigenvalue of $A_{\tau}$ is $r$, with eigenfunction $f(v\tau) = 1$ (and $f(\overline{v\tau}) = -1$) if $v\sim \tau$ and $f(\sigma) = 0$ if $\tau\not\subset\sigma$. We will bound $\norm{A_{\tau}-\tfrac{r}{n}J_{\tau}}$, which is an approximation of the second eigenvalue of $A_\tau$. First we argue that $J_\tau|_{Z_{d-1}} = 0$. To see this, consider $f\in Z_{d-1}$, $\tau\in X^{d-2}$, and $\sigma \in X^{d-1}$. If $\tau\not\subset \sigma$ then $(J_{\tau}f)(\sigma) = 0$. On the other hand, if $\tau\subset\sigma$ then we can write $\sigma = v\tau$ for some $v\notin \tau$. In this case \begin{align} (J_{\tau}f)(\sigma) = \sum_{w\sim \tau} f(w\tau) = (\partial_{d-1}f)(\tau) = 0, \end{align} so we have $J_{\tau}f\equiv 0$ for every $f\in Z_{d-1}$, or in other words $J_{\tau}|_{Z_{d-1}} = 0$. This allows us to say that \begin{align} \norm*{A |_{Z_{d-1}}} &= \norm*{\left.\parens*{A-\smash[b]{\sum_{\tau\in X^{d-2}}}\tfrac{r}{n}J_{\tau}}\right|_{Z_{d-1}}} \sumstrut\\ &\leq \norm*{A-\smash[b]{\sum_{\tau\in X^{d-2}}}\tfrac{r}{n}J_{\tau}} \sumstrut\\ &= \norm*{\smash[b]{\sum_{\tau\in X^{d-2}}} \parens*{A_{\tau}-\tfrac{r}{n}J_{\tau}}}.\sumstrut \label{eqn:sum_to_bound} \end{align} What remains is to bound \eqref{eqn:sum_to_bound}. We use a lemma of Bilu \& Linial: \begin{lemma}[\citet{BL}] \label{thm:bilu_linial} Let $B$ be a symmetric, real-valued $n\times n$ matrix in which the diagonal entries are all $0$. Suppose that the $\ell^1$-norm of every row of $B$ is at most $m$, and also that for any vectors $x,y\in \set{0, 1}^n$ with disjoint support \begin{align}\label{eqn:bl} \abs{\innerprod{x}{By}} \leq \beta\norm{x}\norm{y}. \end{align} Then \begin{align} \norm{B} = O(\beta(\log(m/\beta)+1)). \end{align} \end{lemma} We will apply this lemma to \begin{align} B = A-\tfrac{r}{n}J + \tfrac{rd}{n}I. \end{align} As mentioned in Remark \ref{rmk:matrices}, we can interpret $B$ as a matrix indexed by positive orientations of elements in $X^{d-1}$. Combining the calculations of $A$ and $J$ in that remark, we can calculate that for each $\sigma,\sigma'\in X^{d-1}$, \begin{align} B_{\sigma,\sigma'} = \begin{cases} \sgn(\pi_{\sigma,\sigma'})\parens*{1-r/n} &\text{if }\sigma\cup\sigma'\in X^d\\ \sgn(\pi_{\sigma,\sigma'})\parens*{-r/n} &\text{if }\sigma\cup\sigma'\in \binom{V}{d+1}\setminus X^d\\ 0 &\text{otherwise.} \end{cases} \end{align} Then we can see that $B$ is symmetric (because $\pi_{\sigma',\sigma} = \pi_{\sigma,\sigma'}^{-1}$), real-valued and its diagonal entries are 0. Since $X$ is $r$-regular, the $\ell^1$-norm of each row $\sigma$ in $B$ is \begin{align} \sum_{\sigma'\in X^{d-1}}\abs{B_{\sigma, \sigma'}} = dr\parens*{1-\tfrac{r}{n}} + (n-d-r)d\,\tfrac{r}{n} \leq 2dr. \end{align} Indeed, there are $(n-d)$ total sets $\eta$ of size $d+1$ containing $\sigma$, and $r$ of those are $d$-cells; each such set $\eta$ contains $d$ other cells $\sigma'$ such that $\sigma\cup\sigma'=\eta$. Let $x, y: X^{d-1}_{\pm}\to \set{0,\pm 1}$ be functions in $\Omega^{d-1}$ with disjoint support, so that clearly $\innerprod*{x}{Iy} = 0$. For each $\tau\in X^{d-2}$, define $x_{\tau}(\sigma) = x(\sigma)$ if $\tau\subset\sigma$ and $x_{\tau}(\sigma) = 0$ otherwise. Define $y_{\tau}$ similarly. Note that each $\sigma\in\supp x$ is in the support of exactly $d$ of the functions $x_\tau$. % Observe that \begin{align} \innerprod*{x}{By} &= \innerprod*{x}{\parens*{\smash[b]{\sum_{\tau\in X^{d-2}}}A_{\tau}-\tfrac{r}{n}J_{\tau}}y} + \tfrac{rd}{n} \innerprod*{x}{Iy} \sumstrut\\ &= \sum_{\tau\in X^{d-2}}\innerprod*{x}{\parens*{A_{\tau} - \tfrac{r}{n}J_{\tau}}y} = \sum_{\tau\in X^{d-2}}\innerprod*{x_{\tau}}{A_{\tau} y_{\tau}} - \tfrac{r}{n} \innerprod*{x_{\tau}}{J_{\tau}y_{\tau}}. \end{align} By definition, for any fixed $\tau = (\tau_2,\dots,\tau_d)$ \begin{align} \innerprod*{x_\tau}{A_\tau y_\tau} &= \sum_{\sigma\in X^{d-1}} x_\tau(\sigma) (A_\tau y_\tau)(\sigma) =\sum_{v\not\in\tau} x(v\tau) (A_\tau y_\tau)(v\tau)\\ &= \sum_{v\not\in\tau} x(v\tau) \sum_{w\sim v\tau} y_\tau(w\tau) = \sum_{\substack{v\neq w\\v,w\not\in\tau}} 1_{[vw\tau\in X^d]}x(v\tau)y(w\tau). \end{align} Using a similar decomposition for $\innerprod*{x_\tau}{J_\tau y_\tau}$ we obtain \begin{align} \innerprod*{x_\tau}{(A_\tau - \tfrac{r}{n} J_\tau) y_\tau} = \sum_{\substack{v\neq w\\v,w\not\in\tau}} (1_{[vw\tau\in X^d]} - \tfrac{r}{n})x(v\tau)y(w\tau). \end{align} We would like to interpret the first half of the sum as a number of edges and the second half as the product of the sizes of some vertex sets, since for any disjoint sets $S_0,S_1$ we have by assumption that \begin{align} \abs*{\smash[b]{\sum_{\substack{v\in S_0\\w\in S_1}}} (1_{[vw\tau\in X^d]} - \tfrac{r}{n})}\sumstrut &= \abs*{F(S_0,S_1,\set{\tau_2},\dots,\set{\tau_d}) - \tfrac{r}{n} \size{S_0}\size{S_1}\size{\set{\tau_2}}\dots\size{\set{\tau_d}}}\\ &\leq \rho \sqrt{\size{S_0}\size{S_1}}\,. \end{align} However, this differs from what we have above by the signs from $x$ and $y$. Instead we break the sum apart according to these values, and for each $\eta\in\set{\pm 1}$ we write \begin{align} S_0^\eta &= \set{v \,:\, x(v\tau) = \eta} & S_1^\eta = \set{w \,:\, y(w\tau) = \eta}. \end{align} These four sets are pairwise disjoint and $\norm{x_\tau}^2 = \size{S_0^+} + \size{S_0^-}$ and $\norm{y_\tau}^2 = \size{S_1^+} + \size{S_1^-}$, so now we can write \begin{align} \abs*{\innerprod*{x_\tau}{(A_\tau - \tfrac{r}{n} J_\tau) y_\tau}} &= \abs*{\smash[b]{\sum_{v,w}} (1_{vw\tau\in X^d}-\tfrac{r}{d})x(v\tau)y(w\tau)} = \abs*{\smash[b]{\sum_{\eta_0,\eta_1\in \set{\pm 1}}} \eta_0\eta_1 \smash[b]{\sum_{\substack{v\in S_0^{\eta_0}\\w\in S_1^{\eta_1}}}} (1_{[vw\tau\in X^d]} - \tfrac{r}{n})}\sumstrut\\ &\leq \sum_{\eta_0,\eta_1\in \set{\pm 1}} \rho\sqrt{\size{S_0^{\eta_0}} \size{S_1^{\eta_1}}} = \rho \sum_{\eta_0\in\set{\pm 1}} \sqrt{\size{S_0^{\eta_0}}} \sum_{\eta_1\in\set{\pm 1}} \sqrt{\size{S_1^{\eta_1}}}\\ &\leq \rho \sqrt{2 \smash[b]{\sum_{\eta_0\in\set{\pm1}}} \size{S_0^{\eta_0}}}\ \sqrt{2 \smash[b]{\sum_{\eta_1\in\set{\pm1}}} \size{S_1^{\eta_1}}}\sumstrut = 2\rho \norm{x_\tau}\norm{y_\tau} \end{align} by Cauchy-Schwarz. Summing over all $\tau\in X^{d-2}$ gives that \begin{align} \abs{\innerprod{x}{By}} &=\abs*{\smash[b]{\sum_{\tau\in X^{d-2}}}\innerprod*{x_{\tau}}{(A_{\tau} - \tfrac{r}{n}J_{\tau})y_{\tau}}} \sumstrut\\ &\leq \sum_{\tau\in X^{d-2}} \abs*{\innerprod*{x_{\tau}}{(A_{\tau}-\tfrac{r}{n} J_{\tau})y_{\tau}}}\\ &\leq \sum_{\tau\in X^{d-2}} 2\rho\sqrt{\size{\supp x_{\tau}}\size{\supp y_{\tau}}}\\ &\leq 2\rho \sqrt{\smash[b]{\sum_{\tau\in X^{d-2}}} \size{\supp x_{\tau}}}\ \sqrt{\smash[b]{\sum_{\tau\in X^{d-2}}} \size{\supp y_{\tau}}}\sumstrut \label{eqn:cauchy_schwarz}\\ &=2\rho\sqrt{d\size{\supp x}}\ \sqrt{d\size{\supp y}} \\ &=2\rho d \norm{x}\norm{y}, \end{align} where the inequality in \eqref{eqn:cauchy_schwarz} follows from Cauchy-Schwarz. Finally we can apply Lemma \ref{thm:bilu_linial} with $m = 2r d$ and $\beta = 2\rho d$ to get \begin{align} \norm*{\parens*{\smash[b]{\sum_{\tau\in X^{d-2}}} A_{\tau}-\tfrac{r}{n}J_{\tau}}+\tfrac{rd}{n}I}\sumstrut = O(\rho d (\log(r/\rho)+1)). \end{align} Combining the results for each $\tau$ using the triangle inequality gives \begin{align} \norm*{A|_{Z_{d-1}}} \leq \norm*{\smash[b]{\sum_{\tau\in X^{d-2}}} A_{\tau}-\tfrac{r}{n}J_{\tau}}\sumstrut \leq \norm*{\parens*{\smash[b]{\sum_{\tau\in X^{d-2}}} A_{\tau}-\tfrac{r}{n}J_{\tau}}+\tfrac{rd}{n}I} + \tfrac{rd}{n}. \end{align} To prove the theorem, all that remains is to argue that the second term of the above bound is bounded by $(\tfrac{rd}{n})\leq 4\rho d = O(\rho d (\log(r/\rho)+1))$. (It was previously argued that this expression bounds the first term.) As long as $\emptyset\subsetneq X^d \subsetneq \binom{V}{d+1}$, $\rho\geq \max\set{1-\tfrac{r}{n},\tfrac{r}{n}} \geq 1/2$ (take $S_0, \dots, S_d$ to be singletons corresponding to a subset which is either a $d$-cell or not), so $\tfrac{rd}{n}\leq d \leq 2\rho d$ and we can replace the above bound by \begin{align} \norm*{A|_{Z_{d-1}}} = O(\rho d (\log(r/\rho)+1)). \end{align} For the empty complex, it is trivial that $\tfrac{rd}{n} = 0$, while for the complete complex (with $r = n-d$) we can take $S_2, \dots, S_d$ to be singletons and $\size{S_0} = \size{S_1} = \ceil{\frac{n-d}{2}}$, to get \begin{align} \rho &\geq \frac{F(S_0,\dots,S_d) - \frac{r}{n} \size{S_0}\dots\size{S_d}}{\sqrt{\size{S_0}\size{S_1}}\size{S_2}\dots\size{S_d}} = \frac{d}{n}\sqrt{\size{S_0}\size{S_1}} = \frac{d(n-d)}{2n} \geq \frac{1}{4} \end{align} when $1\leq d < n$, so that $\frac{rd}{n}\leq d\leq 4\rho d$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Friedman-Wigderson Hypergraph Setting} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%% \subsection{Notation for hypergraph eigenvalues} %%%%%%%%%%%% The notion of eigenvalues for hypergraphs that we now describe was developed by Friedman \& Wigderson in \cite{FW}. Further discussion can be found in \cite{LM}. We note that these eigenvalues do not correspond to any matrix, but instead are named by analogy to the eigenvalues of (the adjacency matrix of) a graph. Throughout, let $H = (V, E(H))$ be a $k$-uniform hypergraph with vertex set $V = \set{v_1, \dots, v_n}$. We will only consider hypergraphs $H$ with no loops or multiple edges, that is, $E(H)\subseteq \binom{V}{k}$. The \emph{degree} $\deg(S)=\deg_H(S)$ of a $(k-1)$-set $S$ of vertices in $H$ is the number of edges containing $S$. Say that $H$ is \emph{$r$-regular} if $\deg(S)=r$ for every $(k-1)$-set $S$. \begin{definition}[Hypergraph adjacency form] Let $A = A_H : \prod_{i=1}^k \R^n \to \R$ be the $k$-linear form defined by \begin{align} A(e_{i_1}, e_{i_2}, \dots, e_{i_k}) \defeq\begin{cases} 1 &\text{if }\set{v_{i_1}, v_{i_2}, \dots, v_{i_k}}\in E(H)\\ 0 &\text{otherwise} \end{cases} \end{align} for all choices of the standard basis vectors $e_{i_1}, e_{i_2}, \dots, e_{i_k}$. \end{definition} \begin{definition} If $V_1,\dots,V_k$ are subsets of $V$, then let \begin{align} e_H(V_1,\dots,V_k) \defeq \abs*{\set[\big]{\parens*{v_1,\dots,v_k}\in V_1\times\dots\times V_k:\set{v_1,\dots,v_k}\in E(H)}}. \end{align} \end{definition} As with the adjacency form we will suppress the subscript $H$ when the hypergraph is clear from context. If $V_1,\dots, V_k$ are pairwise disjoint, this is the number of edges that intersect each $V_i$ in exactly one vertex. Alternatively, if we take $x^i$ to be the indicator vector of $V_i$ then we could equivalently define $e(V_1, \dots, V_k) = A(x^1,\dots,x^k)$. Let $J$ denote the $k$-linear form with $J(e_{i_1}, e_{i_2}, \dots, e_{i_k}) = 1$ for all choices of standard basis vectors $e_{i_1}, e_{i_2}, \dots, e_{i_k}$. Let $K = (V, \binom{V}{k})$ denote the complete $k$-uniform hypergraph on vertex set $V$ (with corresponding adjacency form $A_K$ which evaluates to 1 on any \emph{distinct} standard basis vectors.) \begin{definition} If $\displaystyle \phi: \prod_{i=1}^k \R^n \to \R$ is a $k$-linear form, we define the \emph{spectral norm} of $\phi$ to be \begin{align} \norm{\phi} \defeq \sup_{x_i\in \R^n,\ x_i\neq 0} \frac{\abs{\phi(x_1, \dots, x_k)}}{\norm{x_1} \dots \norm{x_k}}\,. \end{align} \end{definition} In the case where $\phi$ is symmetric, as shown in ~\cite{FW} we in fact have that \begin{align} \norm{\phi} = \sup_{x\in \R^n,\ x\neq 0} \frac{\abs{\phi(x, \dots, x)}}{\norm{x}^k}\,. \end{align} Observe that both $A$ and $J$ are symmetric. Recall that the first (largest) eigenvalue of a graph can be defined as the operator norm of its adjacency matrix, $\norm{A_G}$, and if the graph is $r$-regular then the second-largest eigenvalue is $\norm*{A_G - \tfrac{r}{n} J}$. This motivates a definition of the second eigenvalue for \emph{hypergraphs} given by Friedman and Wigderson in \cite{FW}: if $H$ is $r$-regular, they define the second eigenvalue to be \begin{align} \lambda_2(H) \defeq \norm*{A-\tfrac{r}{n}J}. \label{eqn:lambda2} \end{align} For any $H$ (not necessarily $r$-regular), the quantity in \eqref{eqn:lambda2} is called the \emph{second eigenvalue of $H$ with respect to $r$-regularity}. For technical reasons, we will take a slightly different definition for the second eigenvalue. \begin{definition} For any $\alpha\in \R$, the \emph{second eigenvalue of $H$ with respect to $\alpha$-density} is \begin{align} \lambda_{2,\alpha}(H) \defeq \norm{A-\alpha A_K} = \sup_{x\in \R^n,\ x\neq 0} \frac{\abs{A(x,\dots,x) - \alpha A_K(x,\dots,x)}}{\norm{x}^k}. \end{align} \end{definition} We also define a parallel parameter measuring the combinatorial expansion of a hypergraph. \begin{definition} For a $k$-uniform hypergraph $H$, define for each $\alpha \geq 0$ \begin{align} \rho_\alpha(H) \defeq \max_{V_1,\dots,V_k}\frac{\abs[\big]{\size{e(V_1,\dots,V_k)}-\alpha\size{V_1}\dots \size{V_k}}}{\sqrt{\size{V_1}\dots \size{V_k}}}, \end{align} where the maximum is taken over all tuples $V_1,\dots,V_k$ of pairwise disjoint nonempty subsets of $V$. \end{definition} \begin{remark} Our aim is to bound the second eigenvalue in terms of $\rho=\rho_{\alpha}(H)$. Unfortunately, we find that independently of $\rho$, $\lambda_2 = \Omega(rn^{k-2})$ with high probability for random hypergraphs with edge density $r/n$, making an inverse mixing lemma for $\lambda_2$ impossible. Our new definition $\lambda_{2,\alpha}$ allows us to avoid this problem. A further discussion of this problem is found in Section \ref{sec:counterexamples}. \end{remark} It is natural in our definition to choose $\alpha = \size{E(H)}/\size{E(K)}$, i.e., the edge-density of $H$. However, to more closely parallel the Friedman-Wigderson definition one can choose $\alpha = \frac{r}{n}$. For now we will proceed without specifying a fixed value for $\alpha$. \begin{remark} Even if one fixes $\alpha$ as suggested above to be the edge density of $H$, our definition does not quite agree with the usual definition of graph eigenvalues in the case of $r$-regular graphs ($k=2$). In particular, where $\lambda(G) = \norm{A - \tfrac{r}{n} J}$ we use $\lambda_{2,\alpha}(G) = \norm{A - \tfrac{r}{n-1} A_K}$. However, it is easy to see that the two values differ by exactly $\frac{r}{n-1}\norm{I - \tfrac{1}{n}J} = \tfrac{r}{n-1}$, which is bounded from above by $1$. \end{remark} The following simple upper bound will come in handy in later analysis. \begin{proposition}\label{thm:rho_sanity_bound} For any $k$-uniform hypergraph $H$ with maximum degree $r$, \begin{align} \rho_\alpha(H) \leq (r+\alpha n) n^{(k-2)/2}. \end{align} \end{proposition} \begin{proof} Working directly from the definition, we have \begin{align} \rho_\alpha(H) &= \max_{V_1,\dots,V_k} \frac{\abs[\big]{e(V_1,\dots, V_k) - \alpha\size{V_1}\dots\size{V_k}}}{\sqrt{\size{V_1}\dots\size{V_k}}}\\ &\leq \max_{V_1,\dots,V_k} \frac{e(V_1,\dots, V_k) + \alpha\size{V_1}\dots\size{V_k}}{\sqrt{\size{V_1}\dots\size{V_k}}}\\ &\leq \max_{\size{V_1}\geq \dots \geq \size{V_k}} \frac{r\size{V_2}\dots\size{V_k} + \alpha\size{V_1}\dots\size{V_k}}{\sqrt{\size{V_1}\dots\size{V_k}}}\\ &= \max_{\size{V_1}\geq \dots \geq \size{V_k}} (r + \alpha \size{V_1})\frac{\sqrt{\size{V_2}\dots\size{V_k}}}{\sqrt{\size{V_1}}}\\ &\leq (r+\alpha n) n^{(k-2)/2}. \end{align} \end{proof} %%%%%%%%%%%% \subsection{Hypergraph Mixing Lemmas} %%%%%%%%%%%% The following hypergraph mixing result is given in \cite{FW}. \begin{theorem}[Mixing Lemma for hypergraphs, \citet{FW}] \label{thm:mixing_hypergraph} Let $H$ be a $k$-uniform hypergraph. For any choice of subsets $V_1,\dots,V_k\subset V(H)$ of vertices, \begin{align} \abs*{\size{e(V_1,\dots,V_k)}-\frac{k!\size{E(H)}}{n^k}\size{V_1}\dots \size{V_k}} \leq \lambda_2(H)\sqrt{\size{V_1}\dots \size{V_k}}\,. \end{align} \end{theorem} Before stating and proving a converse to Theorem~\ref{thm:mixing_hypergraph} above, we mention the mixing result using our definition of the second eigenvalue $\lambda_{2,\alpha}$, with respect to density $\alpha$. \begin{theorem}[Mixing Lemma for hypergraphs] \label{thm:mixing_hypergraph_density} Let $H$ be a $k$-uniform hypergraph. For any choice of subsets $V_1,\dots,V_k\subset V(H)$ of vertices, \begin{align} \abs{e(V_1,\dots,V_k)-\alpha e_K(V_1,\dots,V_k)} \leq \lambda_{2,\alpha}(H)\sqrt{\size{V_1}\dots \size{V_k}}\,. \end{align} \end{theorem} \begin{proof} Let $V_1,\dots,V_k\subset V(H)$. If any $V_i$ is empty, it is clear that the inequality holds; we may assume that each $V_i$ is nonempty. For $1\leq i\leq k$ let $x^i\in \set{0,1}^n$ be the indicator vector of $V_i$. Then \begin{align} \frac{\abs*{e(V_1,\dots,V_k)-\alpha e_K(V_1,\dots,V_k)}}{\sqrt{\size{V_1}\dots \size{V_k}}} &=\frac{\abs*{A(x^1,\dots ,x^k)-\alpha A_K(x^1,\dots, x^k)}}{\prod_{i=1}^k\norm{x^i}} \\ &\leq \norm{A-\alpha A_K} = \lambda_{2,\alpha}(H) \end{align} as desired. \end{proof} We now prove the main theorem of this section, a converse to the above Theorem \ref{thm:mixing_hypergraph_density}: \begin{theorem}[Inverse Mixing Lemma for hypergraphs] \label{thm:inverse_mixing_hypergraph} If $H$ is a $k$-uniform hypergraph with maximum degree $r$ and $\rho = \rho_\alpha(H)$ then \begin{align} \lambda_{2,\alpha}(H) = O\parens*{\rho\,(\log^{k-1}((r+\alpha n) n^{k-2}/\rho)+1)}. \end{align} \end{theorem} \begin{remark} In our discussion of hypergraphs (as opposed to simplical complexes), the $O$-notation (or $\Theta$-, $\Omega$-, $o$-, \dots) suppresses a multiplicative constant that may depend on $k$ (but not on $n,\rho,r,\alpha,$ or $m$.) One reason for this convention is that $k$ is often treated as a fixed value which may not vary. \end{remark} \begin{remark} We have left this result in what is perhaps not its simplest form, in order to show the difference between the cases $k=2$ and $k\geq 3$. In the case where $k=2$ and $\alpha=\Theta(r / n)$ the dependence on $n$ disappears and this simplifies to the classic result $\lambda_{2,\alpha} = O(\rho(\log(r/\rho) + 1))$ for graphs. For larger (but still constant) uniformity, we can still simplify the result to $\lambda_{2,\alpha} = O(\rho\,(\log^{k-1}((r+\alpha n) n/\rho) + 1))$. \end{remark} \newcommand{\bound}{b} We prove the theorem through a series of lemmas. First we show that the partite expansion condition suffices to give expansion for any (not necessarily disjoint) sets of vertices. Throughout, $\bound$ represents a constant independent of $x$ (but which may depend on $k$, $n$, $r$, $\alpha$, $\rho$ or anything else). \begin{lemma} \label{lem:expansion_equivalence} Let $H$ be a $k$-uniform hypergraph on $n$ vertices with adjacency form $A$, and suppose that \begin{align} \abs*{A(x^1,\dots,x^k) - \alpha A_K(x^1,\dots,x^k)} \leq \rho \prod_{i=1}^k \norm{x^i} \end{align} for every choice of pairwise orthogonal vectors $x^1,\dots,x^k \in \set{0,1}^n$. Then \begin{align} \abs*{A(x^1,\dots,x^k) - \alpha A_K(x^1,\dots,x^k)} \leq \rho k^{k/2} \prod_{i=1}^k \norm{x^i} \end{align} for every choice of (not necessarily orthogonal) vectors $x^1,\dots,x^k \in \set{0,1}^n$. \end{lemma} \begin{proof} Let $V_1,\dots,V_k \subseteq [n]$ be any sets of vertices. Consider an ordered partition $\mathcal{P} = P_1\cup \dots \cup P_k$ of $[n]$ into $k$ nonempty parts. Then \begin{align} e(V_1,\dots,V_k) &= \frac{1}{k^{n-k}}\sum_{\mathcal P} e(P_1\cap V_1,\dots,P_k\cap V_k), \end{align} as every ordered edge $(v_1,\dots,v_k)$ shows up in the sum once for each partition $\mathcal{P}$ with $v_j\in P_j$ for every $j$, and there are $(n-k)^k$ such partitions (the remaining $n-k$ elements can be partitioned in any way among the $k$ sets). Similarly, replacing $H$ with the complete hypergraph gives \begin{align} e_K(V_1,\dots,V_k) &= \frac{1}{k^{n-k}}\sum_{\mathcal P} e_K(P_1\cap V_1,\dots,P_k\cap V_k) = \frac{1}{k^{n-k}}\sum_{\mathcal P} \prod_i \size{P_i\cap V_i}. \end{align} For a fixed partition the subsets $P_i\cap V_i$ are disjoint, so by hypothesis we have \begin{align} \abs*{e(P_1\cap V_1,\dots,P_k\cap V_k) - \alpha e_K(P_1\cap V_1,\dots,P_k\cap V_k)} &\leq \rho \sqrt{\smash[b]{\prod_i} \size{P_i\cap V_i}}\,.\sumstrut \end{align} Recall that $S(n,k)$ denotes the number of ordered partitions of $[n]$ into $k$ nonempty sets, (the number of terms in the sum over all choices of $\mathcal P$.) Then \begin{align} \MoveEqLeft\abs*{e(V_1,\dots,V_k) - \alpha e_K(V_1,\dots,V_k)}\\ &\leq \frac{1}{k^{n-k}}\sum_{\mathcal P} \abs*{e(P_1\cap V_1,\dots,P_k\cap V_k) - \alpha e_K(P_1\cap V_1,\dots,P_k\cap V_k)}\\ &\leq \frac{1}{k^{n-k}}\sum_{\mathcal P} \rho \sqrt{\smash[b]{\prod_i} \size{P_i\cap V_i}}\sumstrut\\ &= \frac{\rho k!S(n,k)}{k^{n-k}} \sum_{\mathcal{P}} \frac{1}{k! S(n,k)} \sqrt{\smash[b]{\prod_i} \size{P_i\cap V_i}}\sumstrut\\ &\leq \frac{\rho k! S(n,k)}{k^{n-k}} \sqrt{\frac{1}{k! S(n,k)} \smash[b]{\sum_{\mathcal{P}} \prod_i} \size{P_i\cap V_i}}\sumstrut\label{eqn:concavity}\\ &=\frac{\rho k! S(n,k)}{k^{n-k}} \sqrt{\frac{k^{n-k} e_K(V_1,\dots,V_k)}{k! S(n,k)}}\\ &\leq \rho \sqrt{\frac{k! S(n,k)}{k^{n-k}}} \prod_i \sqrt{\size{V_i}} \leq \rho k^{k/2} \prod_i \sqrt{\size{V_i}}\,. \end{align} In the last inequality we use the fact that $k!S(n,k) \leq k^n$. The inequality in \eqref{eqn:concavity} follows by concavity of square root. The final result follows immediately, noting that if $x^1,\dots,x^k$ are the indicator vectors for $V_1,\dots,V_k$ then $e(V_1,\dots,V_k) = A(x^1,\dots,x^k)$ and $\size{V_i} = \norm{x^i}^2$. \end{proof} The main part of the work goes towards proving a hypergraph version of Lemma \ref{thm:bilu_linial}. We go through several steps to show that if the expansion bound holds for $\set{0,1}$ vectors then a somewhat relaxed bound holds for all real vectors. \begin{lemma} \label{lem:zero_pm_one} Suppose $B$ is a $k$-linear form such that \begin{align} \abs{B(x^1,\dots,x^k)} \leq \bound \prod_{i=1}^k \norm{x^i} \end{align} for every $x^1,\dots,x^k\in\set{0,1}^n$. Then \begin{align} \abs{B(x^1,\dots,x^k)} \leq 2^{k/2} \bound \prod_{i=1}^k \norm{x^i} \end{align} for every $x^1,\dots,x^k \in \set{0,\pm 1}^n$. \end{lemma} \begin{proof} Let $x^1,\dots,x^k \in \set{0,\pm 1}^n$, and decompose $x^i = x^i_+ - x^i_-$ so that $x^i_\pm\in \set{0,1}^n$ and $\supp x^i = \supp x^i_+\cup \supp x^i_-$. Then \begin{align} \abs{B(x^1,\dots,x^k)} &= \abs{B(x^1_+ - x^1_-, \dots, x^k_+ - x^k_-)}\\ &\leq \sum_{\eta \in \set{\pm}^k} \abs{B(x^1_{\eta_1},\dots,x^k_{\eta_k})} \leq \sum_{\eta \in \set{\pm}^k} \bound \prod_{i=1}^k \norm{x^i_{\eta_i}}\\ &= \bound \prod_{i=1}^k \parens*{\norm{x^i_+} + \norm{x^i_-}} \leq \bound \prod_{i=1}^k \sqrt{2} \norm{x^i}. \end{align} \end{proof} \begin{lemma} \label{lem:powers_of_two} Suppose $B$ is a symmetric $k$-linear form satisfying \begin{align} \label{row-sum} \sum_{j=1}^n \abs{B(e_{i_1},\dots,e_{i_{k-1}}, e_j)} \leq m \end{align} for every $(i_1,\dots,i_{k-1})\in [n]^{k-1}$ and \begin{align} \abs{B(x^1,\dots,x^k)} \leq \bound \prod_{i=1}^k \norm{x^i} \end{align} for every $x^1,\dots,x^k \in \set{0,\pm 1}^n$. Let $a \geq b/(m n^{(k-2)/2})$. Then \begin{align} \abs{B(x,\dots,x)} &\leq \bound \parens*{\log^{k-1} \parens*{\frac{a^2 m^2 n^{k-2}}{\bound^2}} + \frac{k^2}{a}}\norm{x}^k \end{align} for every $x \in \set{0,\pm 2^{-\ell}\,:\, \ell\in\N}^n$. \end{lemma} \begin{proof} Let $x\in\set{0,\pm 2^{-\ell}\,:\,\ell\in \N}^n$ and write $x=\sum_{i\in \N} 2^{-i} x^i$ with $x^i\in \set{0, \pm 1}^n$ (the $x^i$ have pairwise disjoint support and are hence orthogonal). Define $s_i=\size{\supp x^i} = \norm{x^i}^2$ so that \begin{align} \norm{x}_1 &= \sum_{i \in \N} 2^{-i} s_i &\text{and}&& \norm{x}_2^2 &= \sum_{i \in \N} 2^{-2i} s_i. \end{align} Note that all sums have only finitely many nonzero terms. We are interested in bounding \begin{align} \abs{B(x,\dots, x)} &\leq \sum_{i\in \N^k} \parens*{\smash{\prod_{j=1}^k}\vphantom{\sum} 2^{-i_j}} \abs{B(x^{i_1}, \ldots, x^{i_k})}. \end{align} We split this sum into two parts, bounding separately the sums over the index sets \begin{align} P &= \set{i\in \N^k\,:\, \max_j\, i_j - \min_j\, i_j < \gamma} &\text{and} && Q &= \N^k \setminus P \end{align} for some $\gamma \geq 0$ to be determined later. For the sum over $i\in P$ we have \begin{align} \sum_{i\in P} \parens*{\smash{\prod_{j=1}^k}\vphantom{\sum} 2^{-i_j}} \abs{B(x^{i_1}, \ldots, x^{i_k})} &\leq \sum_{i\in P} \parens*{\smash{\prod_{j=1}^k}\vphantom{\sum} 2^{-i_j}} \bound \prod_{j=1}^k \sqrt{s_{i_j}} \\ &= \bound \sum_{i\in P} \parens*{\smash[b]{\prod_j} \parens*{2^{-2i_j} s_{i_j}}^{k/2}}^{1/k} \\ &\leq \frac{\bound}{k} \sum_{i\in P}\sum_j \parens*{2^{-2i_j}s_{i_j}}^{k/2}, \intertext{where the final step uses the AM-GM inequality. Each $\ell\in \N$ appears at most $k(2\gamma)^{k-1}$ times in elements of $P$ (as each time $\ell$ appears in some position the remaining $k-1$ terms must all be between $\ell-\gamma$ and $\ell+\gamma$), so} \frac{\bound}{k} \sum_{i\in P} \sum_j \parens*{2^{-2i_j}s_{i_j}}^{k/2} &\leq \bound\, (2\gamma)^{k-1} \sum_{\ell\in \N} \parens*{2^{-2\ell}s_{\ell}}^{k/2}\sumstrut\\ &\leq \bound\, (2\gamma)^{k-1} \parens*{\smash[b]{\sum_\ell} 2^{-2\ell} s_\ell}^{k/2}\sumstrut\\ &= \bound\, (2\gamma)^{k-1} \norm{x}^k, \end{align} where we have used that $\sum_i a_i^{k/2} \leq (\sum_i a_i)^{k/2}$ for nonnegative $a_i$ and $k\geq 2$. Now we focus on bounding the sum over $i\in Q$. For each $i\in Q$ we move $\min i$ to $i_1$ and $\max i$ to $i_k$. Such a reordered index vector corresponds to at most $k^2$ original vectors, so we have \begin{align} \sum_{i\in Q} \parens*{\smash{\prod_{j=1}^k}\vphantom{\sum} 2^{-i_j}} \abs{B(x^{i_1},\dots,x^{i_k})}%\\[-.5em] &\leq k^2\sum_{i\in \N^{k-1}} \sum_{i_k\geq i_1 + \gamma} \parens*{\smash{\prod_{j=1}^k}\vphantom{\sum} 2^{-i_j}} \abs{B(x^{i_1},\dots,x^{i_k})} \usumstrut\\ &\leq k^2 \sum_{i\in \N^{k-1}} 2^{-2i_1-\gamma}\parens*{\smash{\prod_{j=2}^{k-1}}\vphantom{\sum} 2^{-i_j}} \sum_{i_k\in \N} \abs{B(x^{i_1},\dots,x^{i_k})}\usumstrut. \label{eqn:qbound} \end{align} For fixed $i_1,\dots,i_{k-1}$, \begin{align} \sum_{i_k\in \N} \abs{B(x^{i_1},\dots,x^{i_k})} &\leq \sum_{i_k\in \N}\ \sum_{\ell_1 \in \supp\! x^{i_1}}\!\!\cdots\!\! \sum_{\ell_{k} \in \supp\! x^{i_{k}}} \abs{B(e_{\ell_1},\dots,e_{\ell_{k}})}\\ &= \sum_{\ell_1 \in \supp\! x^{i_1}}\!\!\cdots\!\! \sum_{\ell_{k-1} \in \supp\! x^{i_{k-1}}}\ \sum_{\ell_k\in [n]} \abs{B(e_{\ell_1},\dots,e_{\ell_{k}})}\\ &\leq \sum_{\ell_1 \in \supp\! x^{i_1}}\!\!\cdots\!\! \sum_{\ell_{k-1} \in \supp\! x^{i_{k-1}}} m\\ &= m\prod_{j=1}^{k-1}s_{i_j}, \end{align} where the last inequality follows from the hypothesis \eqref{row-sum}. Plugging this into the bound \eqref{eqn:qbound} above gives % \begin{align} \sum_{i\in Q} \parens*{\smash{\prod_{j=1}^k}\vphantom{\sum} 2^{-i_j}} \abs{B(x^{i_1},\dots,x^{i_k})} &\leq k^2 \sum_{i\in \N^{k-1}} 2^{-2i_1-\gamma}\parens*{\smash{\prod_{j=2}^{k-1}}\vphantom{\sum} 2^{-i_j}} m\prod_{j=1}^{k-1} s_{i_j}\usumstrut \label{degree_bound}\\ &= k^2 2^{-\gamma} m \sum_{i_1\in \N} 2^{-2i_1} s_{i_1} \sum_{i_2,\dots,i_{k-1}} \prod_{j=2}^{k-1} 2^{-i_j}s_{i_j}\\ &= k^2 m 2^{-\gamma} \norm{x}^2 \norm{x}_1^{k-2}\\ &\leq k^2 m n^{(k-2)/2} 2^{-\gamma} \norm{x}^k, \end{align} using the fact that $\norm{x}_1 \leq \sqrt{n} \norm{x}$ (by Cauchy-Schwarz). Putting everything together, we have \begin{align} \abs{B(x,\ldots, x)}/\norm{x}^k \leq \bound\, (2\gamma)^{k-1} + k^2 m n^{(k-2)/2} 2^{-\gamma}. \end{align} Finally, set $\gamma = \log (a m n^{(k-2)/2}/ \bound)$ (which is non-negative by the restriction on $a$) to get \begin{align} \abs{B(x,\dots,x)}/\norm{x}^k &\leq \bound\, (\log^{k-1} (a^2 m^2 n^{k-2} / \bound^2) + k^2 / a) \end{align} as desired. \end{proof} \begin{lemma} \label{lem:continuum} Suppose $B$ is a $k$-linear form such that \begin{align} \abs{B(x,\dots, x)} \leq \bound \norm{x}^k \end{align} for every $x \in \set{0,\pm 2^{-\ell}\,:\, \ell\in\N}^n$, and $B(e_{i_1},\dots,e_{i_k}) = 0$ whenever $i_1,\dots,i_k$ are not all distinct. Then $\norm{B} \leq 2^k \bound$. \end{lemma} \begin{proof} Let $x\in\R^n$ be a vector which maximizes $\abs{B(x,\dots,x)}/\norm{x}^k = \norm{B}$. Without loss of generality, scale $x$ so that $\abs{x_i} \leq 1/2$ for all $i \in [n]$. Choose a random vector $z \in \set{0,\pm 2^{-\ell}\,:\, \ell\in \N}^n$ by picking each coordinate $z_i$ independently as follows: \begin{quote} If $x_i = 0$ then $z_i = 0$. Otherwise, write $\abs{x_i} = 2^{\ell_i} (1+\ep_i)$ for some integer $\ell_i$ and some value of $\ep_i \in [0,1)$. Let $z_i = \text{sign}(x_i) 2^{\ell_i}$ with probability $1-\ep_i$ and $z_i = \text{sign}(x_i) 2^{\ell_i+1}$ with probability $\ep_i$. \end{quote} We can see that $\E[z_i] = x_i$ for all $i\in [n]$ and \begin{align} \E[B(z,\dots, z)] &= \sum_{i\in[n]^k} \E[B(z_{i_1} e_{i_1},\dots,z_{i_k}e_{i_k})] = \sum_{i\in[n]^k} \parens*{\smash{\prod_{j=1}^k}\vphantom{\sum} \E[z_{i_j}]}B(e_{i_1},\dots,e_{i_k})\\ &= \sum_{i\in[n]^k} \parens*{\smash{\prod_{j=1}^k}\vphantom{\sum} x_{i_j}}B(e_{i_1},\dots,e_{i_k}) = B(x,\dots,x). \end{align} Thus there is a vector $z$ for which $\abs{B(z, \dots, z)}\geq \abs{B(x, \dots, x)}$. Observe that by construction $\norm{z} \leq 2\norm{x}$, so \begin{align} \abs{B(x,\dots,x)} &\leq \abs{B(z,\dots,z)} \leq b \norm{z}^k \leq 2^k \bound \norm{x}^k. \end{align} Consequently, $\norm{B} = \abs{B(x,\dots,x)}/\norm{x}^k \leq 2^k \bound$. \end{proof} Finally, we put all of these lemmas together to prove the theorem. \begin{proof}[Proof of Theorem \ref{thm:inverse_mixing_hypergraph}] Suppose $H$ is a $k$-uniform hypergraph on $n$ vertices with maximum degree $r$ satisfying \begin{align} \abs*{e(V_1,\dots,V_k) - \alpha e_K(V_1,\dots,V_k)} \leq \rho \sqrt{\smash[b]{\prod_i} \size{V_i}}\sumstrut \end{align} for every choice of disjoint sets $V_1,\dots,V_k\subseteq V(H)$. By Lemma \ref{lem:expansion_equivalence}, the adjacency form $A$ in fact satisfies \begin{align} \abs*{A(x^1,\dots,x^k) - \alpha A_K(x^1,\dots,x^k)} \leq \rho k^{k/2} \prod_{i=1}^k \norm{x^i} \end{align} for every $x^1,\dots,x^k\in\set{0,1}^n$. Taking $B = A - \alpha A_K$ in Lemma \ref{lem:zero_pm_one} gives that \begin{align} \abs{B(x^1,\dots,x^k)} \leq \rho (2k)^{k/2} \prod_{i=1}^k \norm{x^i} \end{align} for all $x^1,\dots,x^k\in\set{0,\pm 1}^n$. Since for any fixed $i_1,\dots,i_{k-1}$ \begin{align} \sum_{j=1}^n \abs{B(e_{i_1}, \dots,e_{i_{k-1}},e_j)} &\leq \sum_{j=1}^n \abs{A(e_{i_1}, \dots,e_{i_{k-1}},e_j)}+\alpha\sum_{j=1}^n \abs{A_K(e_{i_1}, \dots,e_{i_{k-1}},e_j)}\\ &\leq r+\alpha n, %= O(r) \end{align} we can use $m = r + \alpha n$, $b = \rho\, (2k)^{k/2}$ and $a = (2k)^{k/2}$ in Lemma \ref{lem:powers_of_two} (using Proposition \ref{thm:rho_sanity_bound} to guarantee the constraint on $a$) to find that \begin{align} \abs{B(x,\dots,x)} \leq \rho\, (2k)^{k/2} \parens*{\log^{k-1}\parens*{\frac{(d+\alpha n)^2}{\rho^2} n^{k-2}} + k^2 (2k)^{-k/2}} \norm{x}^k \end{align} for every $x\in\set{0, \pm 2^{-\ell}\,:\, \ell\in\N}^n$. Finally, by Lemma \ref{lem:continuum} we find that \begin{align} \lambda_{2,\alpha}(H) = \norm{B} &\leq 2^{3k/2} k^{k/2} \rho \parens*{\log^{k-1}\parens*{\frac{(d+\alpha n)^2}{\rho^2} n^{k-2}} + k^2 (2k)^{-k/2}}\\ &= \rho\, O(\log^{k-1} ((r+\alpha n)n^{k-2}/\rho) + 1). \end{align} \end{proof} %%%%%%%%%%%% \subsection{Comparison with the Friedman-Wigderson definition of $\lambda_2$}\label{sec:counterexamples} %%%%%%%%%%%% In this section we prove an inverse mixing lemma for the Freidman-Wigderson definition of the second eigenvalue. We will see that this result, while tight, is not as useful as Theorem \ref{thm:inverse_mixing_hypergraph}, and we briefly discuss the reason for this. First, we define a useful $k$-linear form and evaluate its norm. \begin{definition} Let $D = J - A_K$ denote the $k$-linear form with $D(e_{i_1},\dots,e_{i_k}) = 1$ if and only if the indices $i_j$ are not all distinct (and 0 otherwise). \end{definition} \begin{proposition} \label{D_bound} $\norm{D} = \Theta(n^{(k-2)/2})$. \end{proposition} \begin{proof} First of all note that \begin{align} \norm{D} &\geq \abs{D(\vec 1, \dots, \vec 1)}/\norm{\vec 1}^k\\ &= \frac{n^k - n!/(n-k)!}{n^{k/2}} = \Omega(n^{(k-2)/2}). \end{align} On the other hand, for any $x\in \R^n$ \begin{align} \abs{D(x,\dots,x)} &\leq \sum_{i\in [n]^k} \parens*{\smash{\prod_{j=1}^k}\vphantom{\sum} \abs{x_{i_j}}} \abs{D(e_{i_1},\dots,e_{i_k})}\usumstrut\\ &= \mathop{\sum_{i\in [n]^k}}_{i_j\text{ not all distinct}}\prod_{j=1}^k \abs{x_{i_j}}\\ &\leq k^2 {\sum_{i\in [n]^{k-1}}} \abs{x_{i_1}} \prod_{j=1}^{k-1} \abs{x_{i_j}}\\ &= k^2 \sum_{i_1=1}^n \abs{x_{i_1}}^2 \prod_{j=2}^{k-1} \sum_{i_j = 1}^n \abs{x_{i_j}}\\ &= k^2 \norm{x}_2^2 \norm{x}_1^{k-2}\\ &\leq k^2 n^{(k-2)/2} \norm{x}^k, \end{align} as desired. \end{proof} \begin{theorem}\label{inverse_mixing_fw} Let $H$ be a $k$-uniform hypergraph with maximum degree $r$, and suppose that for every choice of disjoint sets $V_1,\dots,V_k\subset V(H)$, \begin{align} \abs*{e(V_1,\dots,V_k)-\frac{r}{n} \smash[b]{\prod_{i}} \size{V_i}} \leq \rho\sqrt{\smash[b]{\prod_i} \size{V_i}}\,.\sumstrut \end{align} Then \begin{align} \lambda_2(H) = \Theta(rn^{(k-4)/2}) + O\parens*{(\log^{k-1}(rn^{k-2}/\rho)+1)\rho}. \end{align} \end{theorem} \begin{proof} Set $\alpha = \tfrac{r}{n}$, so that $r = \Theta(\alpha n)$. Observe that if $V_1,\dots,V_k$ are disjoint, then \begin{align} \abs*{e(V_1,\dots,V_k)-\tfrac{r}{n}\, e_K(V_1,\dots,V_k)} = \abs*{e(V_1,\dots,V_k)-\frac{r}{n} \smash[b]{\prod_{i}} \size{V_i}} \leq \rho \sqrt{\smash[b]{\prod_i} \size{V_i}}\,. \end{align} By Theorem \ref{thm:inverse_mixing_hypergraph}, \begin{align} \norm*{A_H-\tfrac{r}{n}A_K} = O\parens*{(\log^{k-1}(rn^{k-2}/\rho)+1)\rho}, \end{align} and hence by Proposition \ref{D_bound} \begin{align}\label{eqn:lambda2bound} \lambda_2(H) &= \norm*{A_H-\tfrac{r}{n}J} \leq \tfrac{r}{n}\norm{D} + \norm*{A_H-\tfrac{r}{n}A_K}\\ &= O\parens*{rn^{(k-4)/2} + (\log^{k-1}(rn^{k-2}/\rho)+1)\rho}. \end{align} A similar calculation to the one above also gives a lower bound of \begin{align}\label{eqn:lambda_2_lower_bound} \lambda_2(H) \geq \Omega(rn^{(k-4)/2}) - \rho\, O(\log^{k-1}(rn^{k-2}/\rho) + 1). \end{align} \end{proof} If the first term dominates in \eqref{eqn:lambda_2_lower_bound} then the asymptotics of $\lambda_2$ are independent of $\rho$ and so there is no interesting inverse mixing for this definition of the second eigenvalue. We now show that this is in fact typically the case by examining $\rho_\alpha$ for random hypergraphs. To get some idea about the typical magnitude of $\rho_\alpha$, we analyze the Erd\H{o}s-Renyi random hypergraph $G(n, \alpha, k)$, in which each of the $\binom{n}{k}$ $k$-tuples is taken as a hyperedge independently with probability $\alpha$. In hypergraphs this model was developed by Linial-Meshulam \cite{LinM}. \begin{proposition}\label{thm:random_rho} For the Erd\H{o}s-Renyi random hypergraph $G = G(n, \alpha, k)$, with high probability \begin{align*} \rho_\alpha(G) \leq \sqrt{\frac{n\log (k+1) + n + \log (2)}{2}}\,. \end{align*} \end{proposition} \begin{proof} For fixed disjoint sets of vertices $V_1,\dots,V_k$, note that $e(V_1,\dots,V_k)$ is a sum of $\prod_{i=1}^k \size{V_i}$ independent Bernoulli random variables each with mean $\alpha$. By Hoeffding's inequality \cite{H}, its deviation from its mean satisfies \begin{align} \Pr\bracks[\Bigg]{\abs*{e(V_1,\dots,V_k) - \alpha \smash[b]{\prod_i} \size{V_i}} > t} \leq 2e^{-2 t^2/\prod_i \size{V_i}}. \end{align} Plugging in $t = \rho\sqrt{\prod_i \size{V_i}}$ gives \begin{align} \Pr\bracks[\Bigg]{\abs*{e(V_1,\dots,V_k) - \alpha \smash[b]{\prod_i} \size{V_i}} > \rho\sqrt{\smash[b]{\prod_i} \size{V_i}}} \leq 2e^{-2\rho^2}. \end{align} Finally, taking a union bound over all $\leq (k+1)^n$ choices of subsets $V_i$, we find that as long as \begin{align} \delta &\geq 2(k+1)^n e^{-2\rho^2},& \text{or equivalently}&& \rho &\geq \sqrt{\frac{n\log (k+1) + \log (2/\delta)}{2}}\,, \end{align} then with probability at least $1-\delta$ the random hypergraph satisfies \begin{align}\label{eqn:hypergraph_rho} \abs*{e(V_1,\dots,V_k)-\alpha e_K(V_1,\dots,V_k)} \leq \rho\sqrt{\smash[b]{\prod_i} \size{V_i}} \end{align} for \emph{all} choices of $V_1,\dots,V_k$. In particular, for $\delta = e^{-n}$ we have $\rho_\alpha(G) \leq \sqrt{\frac{n\log (k+1) + n + \log (2)}{2}}$ with probability at least $1-\delta$. \end{proof} We can prove a converse (up to a multiplicative factor depending on $k$) in the case where $\alpha$ is constant with respect to $n$. \begin{proposition} For any hypergraph $H$ and any constant $\alpha\in [0,1]$, \begin{align*}\rho_{\alpha}(H) \geq \frac{\alpha(1-\alpha)}{\sqrt{\alpha^2 + (1-\alpha)^2}}\sqrt{n-k+1}. \end{align*} \end{proposition} \begin{proof} Set $V_1\dots, V_{k-1}$ to be distinct singletons $v_1, \dots v_{k-1}$. Define \begin{align*} S & = \{v\in V-\{v_1,\dots v_{k-1}\}\,:\, \{v_1,\dots v_{k-1},v\}\in E(H)\}\\ \text{and\quad} T & = \{v\in V-\{v_1,\dots v_{k-1}\}\,:\, \{v_1,\dots v_{k-1},v\}\notin E(H)\} \end{align*} % Observe that $\size{S}+\size{T} = n-k+1$. Also, observe that \begin{align*} \rho_{\alpha}(H) &\geq \max \parens*{\frac{\abs[\big]{e(\set{v_1},\dots,\set{v_{k-1}},S)-\alpha\size{S}}}{\sqrt{\size{S}}}, \frac{\abs[\big]{e(\set{v_1},\dots,\set{v_{k-1}},T)-\alpha\size{T}}}{\sqrt{\size{T}}}}\\ & =\max \parens*{(1-\alpha)\sqrt{\size{S}}, \alpha\sqrt{\size{T}}}. \end{align*} % If $|S|\geq (n-k+1)\frac{\alpha^2}{(1-\alpha)^2 + \alpha^2}$, then \begin{align*} (1-\alpha)\sqrt{|S|}\geq \frac{\alpha(1-\alpha)}{\sqrt{\alpha^2 + (1-\alpha)^2}}\sqrt{n-k+1}. \end{align*} On the other hand, if $|S|\leq (n-k+1)\frac{\alpha^2}{(1-\alpha)^2 + \alpha^2}$, then \begin{align*} |T| = (n-k+1)-|S|\geq (n-k+1)\frac{(1-\alpha)^2}{(1-\alpha)^2 + \alpha^2}, \end{align*} and \begin{align*} \alpha\sqrt{|T|}\geq \frac{\alpha(1-\alpha)}{\sqrt{\alpha^2 + (1-\alpha)^2}}\sqrt{n-k+1}. \end{align*} \end{proof} Combining this with the previous proposition proves \begin{proposition} \label{prop:randomrho} For the dense Erd\H{o}s-Renyi random hypergraph $G = G(n,\alpha,k)$ where $\alpha \in (0,1)$ is constant with respect to $n$, with high probability $\rho_{\alpha}(G) = \Theta(\sqrt{n})$. \end{proposition} Assume that $\alpha = \tfrac{r}{n}$ is a positive constant independent of $n$, in other words, that $r = \Theta(n)$. \begin{corollary} For the dense Erd\H{o}s-Renyi random hypergraph $G = G(n,\alpha,k)$ where $\alpha \in (0,1)$ is constant with respect to $n$ and $k\geq 4$,with high probability $\lambda_2 = \Theta(n^{(k-2)/2})$. \end{corollary} If $G$ satisfies the bound in Proposition \ref{prop:randomrho}, the second term of \eqref{eqn:lambda_2_lower_bound} is $\Theta(\sqrt{n}\log^{k-1}(n))$, which is dominated by the first term when $k\geq 4$. So, almost every hypergraph with $k \geq 4$ will not have an interesting inverse mixing lemma for the Friedman-Wigderson definition of the second eigenvalue. \begin{remark} The reason for the low quality of inverse mixing under the Friedman-Wigderson definition is the fact that we do not allow loops, so that edges of the hypergraph must contain $k$ distinct vertices. Coefficients of $A$ that correspond to these loops must be $0$. The dominating term of \eqref{eqn:lambda_2_lower_bound} derives from these coefficients, which are the non-zero coefficients of the $k$-linear form $D$. We made the choice not to allow loops in order to prove the sequence of lemmas \ref{lem:expansion_equivalence}-\ref{lem:continuum}. We understand that loops are sometimes permitted; indeed, the original definition of $\lambda_2$ in \cite{FW} is for a model of hypergraph that permits loops. It is unknown whether or not $\lambda_2$ will give a higher quality of inverse mixing in that model. Note that in the looped model the regularity condition is required to hold even for degenerate sets of size $d-1$. \end{remark} \begin{corollary} For the dense Erd\H{o}s-Renyi random hypergraph $G = G(n,\alpha,k)$ where $\alpha \in (0,1)$ is constant with respect to $n$, with high probability $\lambda_{2,\alpha}(G) = \Omega(\sqrt{n})$ and $\lambda_{2,\alpha}(G) = O(\sqrt{n}\log^{k-1}{n})$. \end{corollary} This is proven by combining Proposition \ref{prop:randomrho} with the bounds on $\lambda_{2,\alpha}$ found in Theorem \ref{thm:mixing_hypergraph_density} and Theorem \ref{thm:inverse_mixing_hypergraph}. \section{Acknowledgements} We thank the referees for their detailed comments that helped improve the presentation. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Bibliography %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibliography{inversemixing} %\bibliographystyle{plain} %\bibliographystyle{plainnat-arxiv} \begin{thebibliography}{23} \providecommand{\natexlab}[1]{#1} \providecommand{\url}[1]{\texttt{#1}} \expandafter\ifx\csname urlstyle\endcsname\relax \providecommand{\doi}[1]{doi: #1}\else \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi \bibitem[Alon(1986)]{Alon86} N.~Alon. \newblock Eigenvalues and expanders. \newblock \emph{Combinatorica}, 6\penalty0 (2):\penalty0 83--96, 1986. \newblock ISSN 0209-9683. \newblock \doi{10.1007/BF02579166}. \bibitem[Alon and Chung(1988)]{AC} N.~Alon and F.~R.~K. Chung. \newblock Explicit construction of linear sized tolerant networks. \newblock \emph{Discrete Mathematics}, 72\penalty0 (1--3):\penalty0 15--19, 1988. \newblock \doi{10.1016/0012-365X(88)90189-6}. \bibitem[Bilu and Linial(2006)]{BL} Y.~Bilu and N.~Linial. \newblock Lifts, discrepancy and nearly optimal spectral gap. \newblock \emph{Combinatorica}, 26\penalty0 (5):\penalty0 495--519, 2006. \newblock ISSN 0209-9683. \newblock \doi{10.1007/s00493-006-0029-7}. \bibitem[Chung(2012)]{Chung12} F.~R.~K. Chung. \newblock Quasi-random hypergraphs revisited. \newblock \emph{Random Structures \& Algorithms}, 40\penalty0 (1):\penalty0 39--48, 2012. \newblock ISSN 1098-2418. \newblock \doi{10.1002/rsa.20388}. \bibitem[Chung and Graham(1990)]{ChungGraham} F.~R.~K. Chung and R.~L. Graham. \newblock Quasi-random hypergraphs. \newblock \emph{Random Structures \& Algorithms}, 1\penalty0 (1):\penalty0 105--124, 1990. \newblock ISSN 1098-2418. \newblock \doi{10.1002/rsa.3240010108}. \bibitem[Chung et~al.(1989)Chung, Graham, and Wilson]{CGW} F.R.K. Chung, R.L. Graham, and R.M. Wilson. \newblock Quasi-random graphs. \newblock \emph{Combinatorica}, 9\penalty0 (4):\penalty0 345--362, 1989. \newblock ISSN 0209-9683. \newblock \doi{10.1007/BF02125347}. \bibitem[Conlon et~al.(2012)Conlon, H\`{a}n, Person, and Schacht]{CHPS} D.~Conlon, H.~H\`{a}n, Y.~Person, and M.~Schacht. \newblock Weak quasi-randomness for uniform hypergraphs. \newblock \emph{Random Structures \& Algorithms}, 40\penalty0 (1):\penalty0 1--38, 2012. \newblock ISSN 1098-2418. \newblock \doi{10.1002/rsa.20389}. \bibitem[Friedman and Wigderson(1995)]{FW} J.~Friedman and A.~Wigderson. \newblock On the second eigenvalue of hypergraphs. \newblock \emph{Combinatorica}, 15\penalty0 (1):\penalty0 43--65, 1995. \newblock ISSN 0209-9683. \newblock \doi{10.1007/BF01294459}. \bibitem[Garland(1973)]{G} H.~Garland. \newblock $p$-adic curvature and the cohomology of discrete subgroups of $p$-adic groups. \newblock \emph{Annals of Mathematics}, 97\penalty0 (3):\penalty0 375--423, 1973. \newblock ISSN 0003486X.\\ \newblock \doi{10.2307/1970829}. \bibitem[Hoeffding(1963)]{H} W.~Hoeffding. \newblock Probability inequalities for sums of bounded random variables. \newblock \emph{Journal of the American Statistical Association}, 58\penalty0 (301):\penalty0 13--30, 1963.\\ \newblock \doi{10.1080/01621459.1963.10500830}. \bibitem[Kahle(2014)]{K} M.~Kahle. \newblock Sharp vanishing thresholds for cohomology of random flag complexes. \newblock \emph{Annals of Mathematics}, 179\penalty0 (3):\penalty0 1085--1107, 2014. \newblock \doi{10.4007/annals.2014.179.3.5}. \bibitem[Kohayakawa et~al.(2010)Kohayakawa, Nagle, R{\"o}dl, and Schacht]{KNRS} Y.~Kohayakawa, B.~Nagle, V.~R{\"o}dl, and M.~Schacht. \newblock Weak hypergraph regularity and linear hypergraphs. \newblock \emph{Journal of Combinatorial Theory, Series B}, 100\penalty0 (2):\penalty0 151--160, 2010. \newblock ISSN 0095-8956. \newblock \doi{10.1016/j.jctb.2009.05.005}. \bibitem[{Lenz} and {Mubayi}(2013)]{LM1} J.~{Lenz} and D.~{Mubayi}. \newblock Eigenvalues of non-regular linear quasirandom hypergraphs. \newblock \emph{ArXiv e-print}, September 2013. \newblock \arxiv{1309.3584}. \newblock Provided by the SAO/NASA Astrophysics Data System. \bibitem[{Lenz} and {Mubayi}(2015)]{LM} J.~{Lenz} and D.~{Mubayi}. \newblock Eigenvalues of non-regular linear quasirandom hypergraphs. \newblock \emph{Forum of Mathematics, Sigma}, 3:\penalty0 e2 (26 pages), 2015. \newblock ISSN 2050-5094. \newblock \doi{10.1017/fms.2014.22}. \bibitem[Lenz and Mubayi(2015)]{LM2} J.~Lenz and D.~Mubayi. \newblock The poset of hypergraph quasirandomness. \newblock \emph{Random Structures Algorithms}, 46\penalty0 (4):\penalty0 762--800, 2015. \newblock ISSN 1042-9832. \newblock \doi{10.1002/rsa.20521}. \bibitem[Linial and Meshulam(2006)]{LinM} N.~Linial and R.~Meshulam. \newblock Homological connectivity of random 2-complexes. \newblock \emph{Combinatorica}, 26\penalty0 (4):\penalty0 475--487, 2006. \newblock ISSN 0209-9683.\\ \newblock \doi{10.1007/s00493-006-0027-9}. \bibitem[Lov{\'a}sz(2012)]{Lov12} L.~Lov{\'a}sz. \newblock \emph{Large Networks and Graph Limits}, volume~60 of \emph{Colloquium Publications}. \newblock American Mathematical Society, 2012. \newblock ISBN 978-0-8218-9085-1. \bibitem[Parzanchevski(2013)]{P13} O.~Parzanchevski. \newblock Mixing in high-dimensional expanders. \newblock \emph{ArXiv preprint}, 2013. \newblock \arxiv{1310.6477}. \bibitem[Parzanchevski et~al.(2015)Parzanchevski, Rosenthal, and Tessler]{PRT13} O.~Parzanchevski, R.~Rosenthal, and R.~J. Tessler. \newblock Isoperimetric inequalities in simplicial complexes. \newblock \emph{Combinatorica}, 2015. \newblock \doi{10.1007/s00493-014-3002-x}. \bibitem[Steenbergen et~al.(2014)Steenbergen, Klivans, and Mukherjee]{SKM12} J.~Steenbergen, C.~Klivans, and S.~Mukherjee. \newblock A {Cheeger}-type inequality on simplicial complexes. \newblock \emph{Advances in Applied Mathematics}, 56:\penalty0 56--77, 2014. \newblock ISSN 0196-8858. \newblock \doi{10.1016/j.aam.2014.01.002}. \bibitem[Tanner(1984)]{Tan84} R.~Tanner. \newblock Explicit concentrators from generalized $n$-gons. \newblock \emph{SIAM Journal on Algebraic Discrete Methods}, 5\penalty0 (3):\penalty0 287--293, 1984. \newblock \doi{10.1137/0605030}. \bibitem[Thomason(1989)]{T} A.~Thomason. \newblock Dense expanders and pseudo-random bipartite graphs. \newblock \emph{Discrete Mathematics}, 75\penalty0 (1):\penalty0 381--386, 1989. \newblock ISSN 0012-365X.\\ \newblock \doi{10.1016/0012-365X(89)90101-5}. \bibitem[Towsner(2013)]{Towsner13} H.~Towsner. \newblock Sigma-algebras for quasirandom hypergraphs. \newblock \emph{ArXiv e-print}, 2013. \newblock \arxiv{1312.4882}. \end{thebibliography} \end{document}