\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram} \OneNumberAllTheorems %\usepackage[nocompress]{cite} \DeclareMathOperator{\Id}{Id} \newcommand\gobe[1]{} %%%%%%%%% a placer avant \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} \hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red} \newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}} \newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}} \newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}} \newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% Auteur %%%1 \author{\firstname{Yuval} \lastname{Filmus}} \address{The Henry and Marilyn Taub Faculty of Computer Science \\ Technion --- Israel Institute of Technology, Haifa\\ Israel.} \email{yuvalfi@cs.technion.ac.il} \author{\firstname{Konstantin} \lastname{Golubev}} \address{D-MATH, ETH Zurich, Switzerland. Moscow Center for Fundamental and Applied Mathematics, Russia.} \email{golubevk@ethz.ch} \author{\firstname{Noam} \lastname{Lifshitz}} \address{Einstein Institute of Mathematics \\ Hebrew University, Jerusalem \\ Israel.} \email{noam.lifshitz@gmail.com} %%%%% Sujet \keywords{Chromatic number, independence ratio, hypergraph, extremal set theory.} \subjclass{05C15, 05C65, 05D05} \thanks{The first author is a Taub Fellow, and is supported by the Taub Foundation and ISF grant 1337/16. The second author is supported by the SNF grant number 20002\_169106 and by the ERC grant 336283.} %%%%% Titre et résumé \title[High dimensional Hoffman bound and extremal combinatorics]{High dimensional Hoffman bound and applications in extremal combinatorics} \begin{abstract} The $n$-th tensor power of a graph with vertex set $V$ is the graph on the vertex set $V^{n}$, where two vertices are connected by an edge if they are connected in each coordinate. One powerful method for upper-bounding the largest independent set in a graph is the Hoffman bound, which gives an upper bound on the largest independent set of a graph in terms of its eigenvalues. %\hspace{1em} In this paper we introduce the problem of upper-bounding independent sets in tensor powers of hypergraphs. We show that many prominent open problems in extremal combinatorics, such as the Tur{\'a}n problem for graphs and hypergraphs, can be encoded as special cases of this problem. We generalize the Hoffman bound to hypergraphs, and give several applications. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle %\tableofcontents \section{Introduction} The celebrated Hoffman bound~\cite{hoffman2003eigenvalues} connects spectral graph theory with extremal combinatorics, by upper-bounding the independence number of a graph in terms of the minimal eigenvalue of its adjacency matrix.\footnote{Hoffman's original paper only states a bound on the chromatic number. The corresponding bound on the independence number appears in works of Haemers~\cite{haemers1978generalization} and Lov{\'a}sz~\cite{lovasz1979shannon}, where it is attributed to Hoffman. The weighted version of the Hoffman bound, used by Lov{\'a}sz~\cite{lovasz1979shannon} to compute the Shannon capacity of the pentagon, had appeared earlier in foundational work of Delsarte~\cite{delsarte1973algebraic} in coding theory.} The Hoffman bound, in a generalized version due to Lov{\'a}sz~\cite{lovasz1979shannon}, has seen many applications in extremal set theory and theoretical computer science. The Hoffman bound can be used to solve problems in extremal set theory in which the constraints can be modeled as a graph. As an example, the Hoffman bound can be used to prove the fundamental Erd{\H o}s--Ko--Rado theorem on the size of intersecting families, in which the constraint is that every two sets in the family have nonempty intersection, as well as many other Erd{\H o}s--Ko--Rado theorems on various domains~\cite{ellis2012triangle,ellis2011intersecting,godsil2016ekr}. Other problems involve more complex constraints, and so are not amenable to this method. A simple example is the $s$-wise intersecting Erd{\H o}s\textendash Ko\textendash Rado theorem, due to Frankl~\cite{frankl1976sperner}, which concerns families in which every $s$ sets have nonempty intersection. In this case the constraints can be modeled as a \emph{hypergraph} rather than as a graph. Schrijver~\cite{schrijver2005new} generalized the Hoffman bound to handle certain conditions on triples of sets, in the context of coding theory. His generalization can handle constraints on the possible values of $(|A \Delta B|, |A \Delta C|, |B \Delta C|)$, where $A,B,C$ are sets in the family. His method has been used in several subsequent works, for example~\cite{deklerk2007note,gijswijt2005thesis,gijswijt2006upper}. Recently, the Hoffman bound has been generalized to hypergraphs~\cite{bachoc2019theta,golubev2016chromatic}. Our new bound is particularly attractive for upper-bounding independent sets in tensor powers of hypergraphs, a setting which we describe in detail below. We demonstrate the power of this method by solving a problem of Frankl on triangle-free families and by giving a spectral proof of Mantel's theorem. We also formulate a number of known problems in the language of independent sets in hypergraphs. \subsection{Notations}\label{subsec:Notations} A \emph{multiset} is an unordered collection of elements that is allowed to have repetitions, its size is the number of its elements counting the multiplicity. An \emph{$i$-multiset} is a multiset of size $i$. Let $V$ be a set. We denote by $V^{[i]}$ the collection of all $i$-multisets of elements of $V$, and elements of $V^{\left[i\right]}$ will be denoted by $\left[v_{1},\ldots,v_{i}\right]$. The collection $V^{[0]}$ consists of the empty set. \begin{defi} A \emph{weighted $k$-uniform hypergraph} is a pair $X=\left(V,\mu\right)$ where $V$ is the vertex set and $\mu$ is a probability distribution on $V^{\left[k\right]}$. \end{defi} For $0\leq i\leq k-1$, define a probability measure $\mu_{i}$ (or $\mu_i(X)$, if we wish to make the hypergraph explicit) on $V^{\left[i\right]}$ by the following process. First, choose a multiset $\left[v_{1},\ldots,v_{k}\right]$ according to $\mu$, and then choose an $i$-submultiset of it uniformly at random. We write $X^{\left(i\right)}$ for the set of elements of $V^{\left[i\right]}$ whose $\mu_{i}$ measure is positive. The elements of $X^{\left(i\right)}$ are called the $i$\emph{-faces} of $X$, and the elements of $X^{(0)}\cup\cdots\cup X^{\left(k\right)}$ are called the \emph{faces} of $X$. Note that if $\sigma_{2}$ is a face of $X$, then $\sigma_{1}$ is a face of $X$ for any $\sigma_{1}\subseteq\sigma_{2}.$ Note that $X^{(0)}=\{\emptyset\}$, \ie the empty set is the one and only $0$-face of $X$. We assume without loss of generality that $X^{(1)} = V$, that is, $\mu_1(v) > 0$ for all $v \in V$ (otherwise, we can replace $V$ with $X^{(1)}$). The collection of multisets $\left(X^{\left(k\right)},X^{\left(k-1\right)},\ldots,X^{\left(0\right)}\right)$ can be viewed as an abstract simplicial complex of dimension $k-1$ (\eg as defined in~\cite{bachoc2019theta, golubev2016chromatic}) which is however allowed to have loops (multiples of a vertex in a face). Conversely, an abstract simplicial complex can be made into a weighted uniform hypergraph by introducing a probability measure which is positive on its maximal faces. We caution the reader that in the literature on abstract simplicial complexes, an $i$-face is usually defined as a face of size $i+1$. \begin{defi} A set $I\subseteq V$ is said to be \emph{independent in a $k$-uniform hypergraph $X$} if no $k$-face of $X$ is contained in $I$. The largest possible value of $\mu_{1}\left(I\right),$ where $I\subseteq V$ is an independent set in $X$, is called the \emph{independence number} of $X$ and denoted $\alpha\left(X\right)$. A subset $I\subseteq V$ is said to be an \emph{extremal independent set} of $X$ if $\mu_{1}\left(I\right)=\alpha\left(X\right).$ \end{defi} A \emph{flag} of $X$ is a tuple of faces $A_0,\ldots,A_k$ such that $A_i$ is an $i$-face and $A_0 \subseteq \cdots \subseteq A_k$. We can couple the distributions $\mu_{0},\dots,\mu_{k}$ into a distribution $\boldsymbol{\mu}$ over flags of $X$ by sampling a random $k$-face according to $\mu$ and removing elements from it one by one uniformly at random. It will also be useful to consider distributions $\tilde{\mu}_{i}$ on $V^{[i]}$, obtained by sampling an $i$-face according to $\mu_{i}$, and then choosing an order of the vertices it contains uniformly at random. We use the notation $\mathbf{v} \sim \mu_1$ to denote a random variable $\mathbf{v}$ supported on $V^{[1]}$ and distributed according to $\mu_1$. Similarly, $(\mathbf{u},\mathbf{v}) \sim \tilde\mu_2$ denotes a random variable $(\mathbf{u},\mathbf{v})$ supported on $V^{[2]}$ and distributed according to $\tilde{\mu}_2$, and so on. The notation $\mathbf{w} \sim \mathbf{\mu}$ denotes a random variable $\mathbf{w}$ supported on $X^k$ and corresponding to our earlier definition (a probability distribution over tuples of faces $A_0 \subseteq \cdots \subseteq A_k$) as follows: $A_i = [\mathbf{w}_1,\ldots,\mathbf{w}_i]$. Let $\sigma\in X^{\left(i\right)}$ be an $i$-face. Its \emph{link} in \emph{$X$} is the $(k-i)$-uniform hypergraph $X_{\sigma}=\left(V,\mu_{\sigma}\right)$, where $\mu_{\sigma}$ is the probability distribution that corresponds to the following process: sample a random flag according to $\boldsymbol{\mu}$ subject to $\boldsymbol{\mu}_{i}=\sigma$, and output $\boldsymbol{\mu}_{k}\setminus\sigma$. Note that the link of the empty set is the whole hypergraph $X$ itself. For an element $v \in X$, the link of $v$ is $X_v = X_{\{v\}}$. For a set $A\in X^{\left(k-i\right)}$ we shall say that $\mu_{\sigma}\left(A\right)$ is the \emph{relative measure of $A$ according to $\sigma$}. The \emph{skeleton} (or \emph{underlying graph}) of $X$ is the weighted graph $S\left(X\right)$ on the vertex set $X^{\left(1\right)}$, whose edges are $X^{\left(2\right)}$, and whose weights are given by $\mu_{2}$. The inner product on the space $L^{2}\left(X^{(1)},\mu_{1}\right)$ of functions on the vertices is defined as \[ \left\langle f,g\right\rangle =\mathbb{E}_{\boldsymbol v\sim\mu_{1}}f(\boldsymbol v)g(\boldsymbol v)=\sum_{v\in X^{(1)}}f(v)g(v)\mu_{1}(v). \] The normalized adjacency operator $T_{X}$ of $X$ is that of the skeleton $S(X)$. In other words, $T_{X}$ acts on $L^{2}\left(X^{(1)},\mu_{1}\right)$ as follows: \[ \left(T_{X}f\right)(v)=\mathbb{E}_{\mu_{1}(X_{v})}[f]. \] If $f,g\in L^{2}(X^{(1)},\mu_{1})$ then \begin{equation*} \begin{split} \langle f,T_{X}g\rangle &= \mathbb{E}_{\boldsymbol{v}\sim\mu_{1}}f(\boldsymbol{v})\mathbb{E}_{\boldsymbol{u}\sim\mu_{1}(X_{\boldsymbol{v}})}g(\boldsymbol{u}) \\ & =\mathbb{E}_{\boldsymbol{w}\sim\boldsymbol{\mu}}f(\boldsymbol{w}_{1})g(\boldsymbol{w}_{2}\setminus\boldsymbol{w}_{1}) =\mathbb{E}_{\boldsymbol{(u,v)}\sim\tilde{\mu}_{2}}f(\boldsymbol{v})g(\boldsymbol{u}). \end{split} \end{equation*} This shows that $T_{X}$ is self-adjoint, and so has real eigenvalues. The matrix form of $T_{X}$ is given by the formula \begin{equation}\label{eq:norm-adj} T_{X}(u,v)=\begin{cases} \frac{\mu_{2}([u,u])}{\mu_{1}(u)} & \text{if }u=v;\\ \frac{\mu_{2}([u,v])}{2\mu_{1}(u)} & \text{if }u\ne v. \end{cases} \end{equation} Similar reasoning shows that we can sample $[u,v]\sim\mu_{2}$ by sampling $u\sim\mu_{1}$ and $v\sim\mu_{1}(X_{v})$. Note that if $V$ is a finite set (which is the case throughout this paper), then the largest eigenvalue of $T_{X}$ is $1$ and is achieved on the constant function. By $\lambda(X)$ we denote the smallest eigenvalue of $T_{X}$. For all $0\leq i \leq k-2$, we write \[ \lambda_{i}\left(X\right)=\min_{\sigma\in X^{\left(i\right)}}\left[\lambda\left(S\left(X_{\sigma}\right)\right)\right]. \] In other words, $\lambda_{i}\left(X\right)$ is the minimal possible value of an eigenvalue of the normalized adjacency matrix of a skeleton of the link of an $i$-face of $X$. Note that $\lambda_{0}(X)$ is just the smallest eigenvalue of the normalized adjacency operator on the skeleton of $X$. \begin{defi} The tensor product $X\otimes X'$ of two $k$-uniform hypergraphs $X=\left(V,\mu\right)$ and $X'=\left(V',\mu'\right)$ is a $k$-uniform hypergraph $(V\times V',\mu\times\mu')$, where $\mu\times\mu'$ stands for the following measure on $(V\times V')^{[k]}\simeq V^{[k]}\times V'^{[k]}$: an ordering of an edge $(\sigma,\sigma')\in V^{[k]}\times V'^{[k]}$ implies an ordering on $\sigma$ and on $\sigma'$, we define $(\mu \times \mu')_k(\sigma,\sigma')$ as the sum of $\widetilde{\mu_k}(\sigma)\widetilde{\mu_k'}(\sigma')$ over all orderings of $(\sigma,\sigma')$. Recall that $\widetilde{\mu_k}$ is constructed from $\mu$ by choosing an ordering on an edge uniformly at random. For a $k$-uniform hypergraph $X$, we denote by $X^{\otimes n}=\underbrace{X\otimes\dots\otimes X}_{n}$ its $n$-th tensor power. \end{defi} \subsection{Results} We prove a new upper bound for the independence number of a hypergraph, and its invariance under the tensor power operation. \begin{theo} \label{thm:bound-intro} Let $X=\left(V,\mu\right)$ be a $k$-uniform hypergraph. Then \begin{equation} \alpha\left(X\right)\le1-\frac{1}{\left(1-\lambda_{0}\right)\left(1-\lambda_{1}\right)\cdots\left(1-\lambda_{k-2}\right)}.\label{eq:generalized Hoffman bound-1} \end{equation} If in addition $\lambda_{i}\leq0$ for all $0\leq i -1$ and $I$ is an independent set attaining the bound, then $I$ is a dictator (viewed as a subset of $V^n$, membership in $I$ depends on a single coordinate). \end{theo} We prove the first part of this theorem as Theorem~\ref{thm:Generalized-Hoffman-bound}, and the second part (regarding $X^{\otimes n}$) as Theorem~\ref{thm:hoffman-power}. The proof also yields conditions for equality, which we use in the applications to identify extremal families. Since the condition for equality in the first part of the theorem is somewhat verbose, we only state it in full after proving Theorem~\ref{thm:Generalized-Hoffman-bound}. When $k = 2$, we obtain the classical Hoffman bound $\alpha(X) \leq \frac{-\lambda}{1-\lambda}$, where $\lambda$ is the minimal eigenvalue of a weighted adjacency matrix of $X$. We apply Theorem~\ref{thm:bound-intro} to deduce the following result on Frankl's problem on triangle-free families, in both a uniform and a $p$-biased versions. \begin{theo}\label{thm:intro-frankl} \emph{The uniform version.} %\textbf{.} Let $\binom{[n]}{2k}$ be the space of $2k$-subsets of $[n]$, where $3k\le n\le4k-1$. If $\mathcal{F}\subseteq\binom{[n]}{2k}$ is a family of subsets which does not contain three distinct subsets whose symmetric difference is empty, then $|\mathcal{F}|\le\binom{n-1}{2k-1}$. This bound is sharp, as, for example, the family of all subsets containing the element $1$ satisfies the condition and contains $\binom{n-1}{2k-1}$ subsets. \emph{The $p$-biased version.} Let $\{0,1\}^{n}$ be the space of $\{0,1\}$-vectors of length $n$ endowed with be the $p$-biased measure $\mu$, where $1/2\leq p\leq2/3$. If $\mathcal{F}\subseteq\{0,1\}^{n}$ is a family of vectors which does not contain three distinct vectors whose sum is zero, then $\mu(\mathcal{F})\leq p$. This bound is sharp, as, for example, the set of all vectors having $1$ as their first coordinate satisfies the condition and has measure $p$. \end{theo} Our method also provides spectral proofs of Mantel's theorem on triangle-free graphs and Frankl--Tokushige theorem on $k$-wise intersecting families. \begin{theo}[Mantel~\cite{mantel1907}] \label{thm:intro-mantel} If a graph on $n$ vertices contains no triangle, then it contains at most $\left\lfloor \frac{n^{2}}{4}\right\rfloor$ edges. \end{theo} \begin{theo}[Frankl--Tokushige~\cite{frankl2003weighted}] Let $k\ge2$ and $p\leq1-\frac{1}{k}$. Assume $\mathcal{F}\subset\mathcal{P}([n])$ is $k$-wise intersecting family of subsets of $[n]$, that is, for all $F_1,\dots,F_k\in\mathcal{F}$ \[ F_1\cap\dots\cap F_k \neq \emptyset. \] Then $\mu_p(\mathcal{F}) = \sum_{F\in \mathcal{F}} p^{|F|}(1-p)^{n-|F|}\leq p$, where $\mu_p$ is the $p$-biased measure on $\mathcal{P}([n])$. \end{theo} \subsection{Structure of the Paper} In Section~\ref{sec:Hoffman-bound-graphs}, we give a brief overview of the method for graphs: the Hoffman bound, its behavior for tensor product of graphs, and applications in extremal combinatorics. In Section~\ref{sec:Generalization-to-hypergraphs}, we introduce the required hypergraph definitions and notations, and translate a number of known problems to the language of independent sets of hypergraphs. In Section~\ref{sec:High-dimensional-Hoffman}, we prove Theorem~\ref{thm:bound-intro} and compare the new bound to the known ones. In Sections~\ref{sec:Frankl-triangle} and~\ref{sec:Mantel-proof}, we prove Theorems~\ref{thm:intro-frankl} and~\ref{thm:intro-mantel}, respectively. \iffalse We conclude the paper with suggestions for further research in Section~\ref{sec:Open-problems}.\fi %\subsection{Acknowledgements} \section{Hoffman bound for graphs\label{sec:Hoffman-bound-graphs}} Let $G=\left(V,\mu\right)$ be a graph, that is, a $2$-uniform hypergraph in the notations of this paper. By edges of $G$ we mean the support of $\mu$ in $V^{[2]}$. A subset of $V$ is called \emph{independent} if it does not contain any edges. Recall that $\mu_1$ is the induced measure on $V$. \iffalse The stationary distribution $\mu_{G}$ on $V$ is the probability distribution in which a vertex is chosen uniformly at random out of a uniformly random edge of from $E$. The measure of a set $A\subseteq V$ is its measure w.r.t.\ $\mu_{G}$. Note that $\mu_{G}$ coincides with the uniform distribution on $V$ iff $G$ is regular.\fi The \emph{independence number} of $G$ is the maximal value of $\mu_{1}\left(A\right)$ over all independent sets $A\subseteq V$. If $\mu_{1}\left(A\right)=\alpha\left(G\right)$, we say that $A$ is an \emph{extremal independent set} of $G.$ \iffalse The \emph{normalized adjacency operator} of $G$ is defined by the matrix $P_{G}$ given by $P_{G}\left(v,u\right)=\frac{1}{\deg\left(v\right)}.$ The eigenvalues of $G$ are defined to be the eigenvalues of $P_G$. \fi We write $\lambda_{\min}\left(G\right)$ for the minimal eigenvalue of the normalized adjacency $T_G$ on $G$, see Equation~\eqref{eq:norm-adj} for the formula. The Hoffman bound for graphs gives an upper bound on the largest independent set of $G$ in terms of its minimal eigenvalue.\footnote{The Hoffman bound is sometimes stated for $d$-regular graphs in terms of the unnormalized independence number and the unnormalized adjacency matrix, in which case it reads $\alpha(G) \leq \frac{-\lambda_{\min}(G)}{d-\lambda_{\min}(G)}n$, where $n$ is the number of vertices. This formula can be derived from ours by noticing that normalizing the adjacency matrix of a $d$-regular graph corresponds to division by $d$.} \begin{theo}[Hoffman bound~\cite{haemers1978generalization,hoffman2003eigenvalues,lovasz1979shannon}] Let $G$ be a graph. Then \[ \alpha\left(G\right)\le\frac{-\lambda_{\min}\left(G\right)}{1-\lambda_{\min}\left(G\right)}. \] \end{theo} Ever since Hoffman's original work, the Hoffman bound has become a central tool in the study of intersection problems in combinatorics. For example, Lov{\'a}sz~\cite{lovasz1979shannon} showed that it can be used to prove the celebrated Erd{\H o}s\textendash Ko\textendash Rado theorem~\cite{erdos1961intersection}, (aka EKR theorem), which states that for $n\geq2k$, the maximum size of an intersecting family of $k$-element subsets of $[n]$ is $\binom{n-1}{k-1}$. The theorem follows directly from the Hoffman bound by considering the Kneser graph, which is the graph on the vertex set $\binom{[n]}{k}$ in which two sets are connected if they are disjoint. It is crucial for the proof that the Hoffman bound is tight in this case. The Hoffman bound can be also used in a more sophisticated manner. For instance, Wilson~\cite{wilson1984exact} considered the $t$-intersection variant of the EKR theorem, in which the goal is to find the largest subfamily of $\binom{[n]}{k}$ in which any two sets have at least $t$ elements in common. In contrast to the EKR theorem, in this case applying the Hoffman bound on the generalized Kneser graph (in which two sets are connected if their intersection contains less than $t$ points) does not give a tight upper bound. Instead, one needs to accurately choose weights for the edges of this graph, some of them negative, and only then apply the Hoffman bound. In this way, Wilson managed to determine all values of $n,k,t$ in which the extremal family is the family of all sets that contain a given set of size $t$, namely, $n\ge\left(t+1\right)\left(k-t+1\right)$. This approach became more systematic in the work of Friedgut~\cite{friedgut2008measure}, who applied Fourier analysis to construct a matrix for the $p$-biased version of Wilson theorem. This Fourier-analytic approach was also useful in the proof of a long-standing problem of Simonovitz and S{\'o}s on triangle-intersecting families of graphs~\cite{ellis2012triangle}. Ellis, Friedgut, and Pilpel~\cite{ellis2011intersecting}, used a similar approach to solve an old problem of Deza and Frankl, showing that a $t$-intersecting family of permutations in $S_{n}$ contains at most $(n-t)!$ permutations, for large enough $n$ (two permutations $t$-intersect if they agree on the image of at least $t$ points). For an exposition of many different applications of the Hoffman bound to Erd{\H o}s--Ko--Rado theory, consult the excellent monograph of Godsil and Meagher~\cite{godsil2016ekr}. Another important application of this method is to error-correcting codes. This approach was pioneered by Delsarte~\cite{delsarte1973algebraic}. Schrijver~\cite{schrijver1979comparison} showed that Delsarte's linear programming bound can be expressed as a mild generalization of the Hoffman bound. McEliece, Rodemich, Rumsey, and Welch~\cite{mceliece1977upper} used this approach to prove the so-called ``linear programming bound'', which is the best bound on the size of binary error-correcting codes. (Since then, the bound has been recovered using different techniques by Navon and Samorodnitsky~\cite{navon2009linear}.) The main flaw of the Hoffman bound is the fact that it does not apply to problems in which the constraint involves more than two sets. For example, it cannot be used to upper-bound the size of a subfamily of $\binom{[n]}{k}$ in which any \emph{three} sets $t$-intersect. It is therefore of great importance to find high-dimensional analogues of the Hoffman bound that fit these more general restrictions. Schrijver~\cite{schrijver2005new} came up with a generalization of the Hoffman bound which is able to handle some constraints on triples of sets. In more detail, his method can handle constraints on the allowed Hamming distance patterns on triples of sets in the family. However, his method does not handle arbitrary constraints on triples, and does not extend beyond triples. Over the years there has been great interest in the problem of generalizing results from graphs to hypergraphs (or, equivalently, simplicial complexes), see \eg \cite{golubev2019spectrum, AnnaGundert2015, linial2016phase, lubotzky2014ramanujan, parzanchevski2017mixing,parzanchevski2017simplicial, parzanchevski2016isoperimetric}. In particular, two generalizations of the Hoffman bound were given by~\cite{bachoc2019theta} and~\cite{golubev2016chromatic}. Such results are known as \emph{high-dimensional Hoffman bounds}. In contrast to Schrijver's generalization, such bounds apply to arbitrary hypergraphs. The goal of this paper is to give a new high-dimensional Hoffman bound, which we believe is the right tool for tackling many problems in extremal combinatorics. \subsection{Independent sets in tensor power of graphs} The Hoffman bound is particularly useful for independent sets in \emph{tensor powers of graphs}. Given graphs $G=\left(V,\mu\right)$, $G'=\left(V',\mu'\right)$, their tensor product is the graph $G\otimes G'$ whose vertex set is $V\times V'$ endowed with the product measure $\mu\times\mu'$. In particular, two of vertices in the product are connected by an edge if they are connected by an edge in each coordinate. The $n$-th tensor power of $G$ is the graph $G^{\otimes n}=G\otimes\cdots\otimes G$. Independent sets in tensor products of graphs are well studied, see \eg \cite{alon2004graph}, \cite{alon2007independent}, and~\cite{dinur2008independent}. One motivation is their connection to the theory of hardness of approximation, see~\cite{dinur2009conditional}. However, our main focus in this paper will be the connection to extremal set theory. This connection was first implicitly established by Friedgut~\cite{friedgut2008measure}, and later more explicitly by Dinur and Friedgut~\cite{dinur2009intersecting}. It is a well-known rule of thumb (backed by various results) that the two Erd{\H o}s--R{\'e}nyi models of random graphs, $G\left(n,p\right)$ and $G\left(n,m\right)$, should behave similarly when $p=\frac{2m}{n(n-1)}$.\footnote{Both models construct random graphs on $n$ vertices. In the model $G(n,p)$, we include each edge independently with probability $p$. In the model $G(n,m)$, we choose exactly $m$ edges at random.} A similar phenomenon holds in extremal set theory: questions about subfamilies of $\binom{[n]}{k}$ behave similarly to questions about subsets of $\mathcal{\mathcal{P}}([n])$ with respect to the $p$-biased measure $\mu_{p}$ for $p=k/n$, where a set $\boldsymbol{A}\subseteq\left[n\right]$ is chosen by independently putting each element of $\left[n\right]$ inside $\boldsymbol{A}$ with probability $p$ and outside of it with probability $1-p$. We write $\mu_{p}\left(\mathcal{F}\right)$ for the probability that a random subset $\boldsymbol{A}\sim\mu_{p}$ belongs to $\mathcal{F}.$ For instance, the EKR theorem, which asks how large can an intersecting family $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ be, can be rephrased as follows: \begin{quotation} Suppose that $\mathcal{F}$ is intersecting. How large can the probability that a random $k$-set belongs to $\mathcal{F}$ be? \end{quotation} This formulation of the problem immediately suggests the following $p$-biased analogue: \begin{quotation} How large can $\mu_{p}\left(\mathcal{F}\right)$ be if $\mathcal{F}\subseteq\mathcal{P}\left(\left[n\right]\right)$ is intersecting? \end{quotation} This problem was first studied by Ahlswede and Katona~\cite{ahlswede1977contributions}, in the 70's. While both the EKR problem and its $p$-biased analogue have already been solved, this connection is still useful for many of the generalizations of the EKR theorem, where a result in the $k$-uniform setting can be deduced from the $p$-biased setting and vice versa, see Dinur and Safra~\cite{dinur2005hardness}. The $p$-biased version of the EKR theorem is the problem of determining the extremal independent sets in the graph $G^{\otimes n},$ where $G$ consists of two vertices $\left\{ 0,1\right\} $ with the (undirected) edge $\left\{ 1,0\right\} $ having the weight $2p,$ and with the edge $\left\{ 0,0\right\} $ having the weight $1-2p.$ This observation was used by Friedgut~\cite{friedgut1998boolean}, Dinur and Friedgut~\cite{dinur2005hardness}, and later by Friedgut and Regev~\cite{friedgut2017kneser}, to apply Fourier-analytic methods that are natural in the context of graph products in order to study variants of the EKR theorem. In a suitable basis, the matrix of the adjacency operator of a tensor product of graphs is the Kronecker product of the adjacency operator matrices of the factors. Hence, the following property holds: $\lambda_{\min}(G^{\otimes n}) = \lambda_{\min}(G)$. This immediately implies that the Hoffman bound is sharp on $G^{\otimes n}$ whenever it is sharp on $G$. It reduces the $p$-biased EKR problem for families $\mathcal{F}\subseteq\mathcal{P}\left(\left[n\right]\right)$ to the problem of showing that the Hoffman bound is sharp in the special case $n=1$, which can be verified directly. A subset $A$ of $G^{\otimes n}$ is called a \emph{dictatorship} if there exists a set $B\subseteq G$ and $1\leq i\leq n$ such that a vertex $x=(x_1,\dots,x_n)$ is in $A$ iff $x_{i}$ is in $B$. The above observation shows that if the Hoffman bound is sharp for $G$, then the Hoffman bound is sharp for $G^{\otimes n}$ as well, and the dictatorships corresponding to extremal independent sets of $G$ are extremal for $G^{\otimes n}$ (not necessarily exclusively). Alon, Dinur, Friedgut, and Sudakov~\cite{alon2004graph}, essentially showed the following stronger version of this observation. \begin{theo}[\cite{alon2004graph}] Let $G$ be a weighted connected non-bipartite graph. If the Hoffman bound is sharp for $G$, \ie $\alpha\left(G\right)=\frac{-\lambda_{\min}}{1-\lambda_{\min}}$, then $\alpha\left(G^{\otimes n}\right)=\alpha\left(G\right).$ Moreover, if $A$ is an independent set with $\mu_{G}\left(A\right)=\alpha\left(G\right)$, then $A$ is a dictatorship. Furthermore, for each $\epsilon>0$ there exists $\delta = \delta(\epsilon,G)>0$ such that if an independent set $A$ satisfies $\mu_{G}\left(A\right)>\alpha\left(G\right)-\delta$, then there exists an independent dictatorship $B$ such that $\mu_{G}\left(A\Delta B\right)<\epsilon$. Moreover, $\delta$ in fact depends only on $\epsilon$ and on $\min_v \mu_G(\{v\})$. \end{theo} (To deduce this theorem from their work requires the FKN theorem for product spaces, due to Jendrej, Oleszkiewicz, and Wojtaszczyk~\cite{jendrej2015fkn}.) \section{Known problems in the language of hypergraphs\label{sec:Generalization-to-hypergraphs}} There are plenty of reasons why the above theory begs to be generalized to hypergraphs (or, equivalently, simplical complexes). In addition to the definitions given in the introduction, let us give a version of them in the $k$-partite setting, which is a special case of $k$-uniform hypergraphs. \begin{defi} A weighted $k$-partite hypergraph is a tuple $X=\left(V_{1},\ldots,V_{k},\mu\right)$, where $\mu$ is a probability distribution on $V_{1}\times\cdots\times V_{k}$. The probability distribution $\mu_{X,V_{i}}$ is the probability distribution on $V_{i}$, where a vertex is chosen as the projection on $V_{i}$ of a random element chosen according to $\mu.$ Sets $A_{1}\subseteq V_{1},\ldots,A_{k}\subseteq V_{k}$ are said to be \emph{cross-independent} if the probability that a random element of $\mu$ belongs to $\prod_{i=1}^{k}A_{i}$ is $0$. The tensor power of $X$ is the $k$-partite hypergraph $X^{\otimes n}=\left(V_{1}^{n},\ldots,V_{k}^{n},\mu^{\otimes n}\right),$ where $\mu^{\otimes n}$ is the product probability distribution. \end{defi} Independent sets in tensor powers of hypergraphs arise all over combinatorics, and many of the fundamental problems in extremal combinatorics can be formulated as problems about independent sets in tensor powers of hypergraphs. Below we formulate several well-known problems, solved and open, in the language of hypergraphs, and give proof to two of them: Frankl's Triangle Problem and Mantel's Theorem. \subsection{Number theory} How large can a subset $A\subseteq\mathbb{F}_{q}^{n}$ be if it does not contain elements $x_{1},\ldots,x_{m}\in A$ that form a solution to the system of equations $\sum_{i=1}^{m}a_{ij}x_{i}=b_{j}$, for parameters $a_{ij},b_{j}\in\mathbb{F}_{q}$? For instance, the Meshulam--Roth theorem~\cite{meshulam1995subsets}, concerns the problem of determining how large can a subset of $\mathbb{F}_{p}^{n}$ be if it contains no non-trivial solutions to the equation $x+z=2y.$ Similarly, the analogous problem for $k$-term arithmetic progressions can be formulated as a non-trivial solution to the equations \[ x_{1}+x_{3}=2x_{2},x_{2}+x_{4}=2x_{3},\ldots,x_{m-2}+x_{m}=2x_{m-1}. \] Take the $m$-uniform hypergraph $X=\left(\mathbb{F}_{q},\mu\right),$ where $\mu$ is positive on the solutions to the equations $\sum_{i=1}^{m}a_{ij}x_{i}=b_{j}.$ Since a solution to the system of equations in $\mathbb{F}_{q}^{n}$ is a solution iff it is a solution in each coordinate, the hypergraph $X^{\otimes n}$ is the hypergraph whose independent sets correspond to solutions of the same system of equations as above. This observation was first given by Mossel~\cite{mossel2010noise}. \subsection{Tur{\'a}n problem for hypergraphs} One of the fundamental problems in extremal combinatorics is the Tur{\'a}n problem for hypergraphs, which asks how large can a family $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ be if it does not contain a copy of some given hypergraph $H.$ The Tur{\'a}n problem can be restated as a problem about independent sets in tensor powers of $k$-partite hypergraphs (in preparation by the third author). Let us state it here in the case of triangles in graphs. \begin{exam}\label{exa:Mantel hypergraph} \looseness-1 Let $K_{2,2,2}$ be the complete $3$-partite hypergraph between sets $A_{1},$ $ A_{2},$ $A_{3}$ of size 2, let $E_{ij}$ be the set of edges between $A_{i}$ and $A_{j}$, and let $X=\left(V_{1},V_{2},V_{3},\mu\right)$ be the $3$-partite hypergraph, where \[ V_{1}=E_{23},V_{2}=E_{31},V_{3}=E_{12}, \] and where $\mu$ is the uniform measure on the set of triangles in $K_{2,2,2}.$ The $3$-uniform hypergraph \[ X^{\otimes n} \] is the hypergraph whose vertices correspond to the edges in $K_{2^{n},2^{n},2^{n}}$ and whose hyperedges correspond to the triangles in $K_{2^{n},2^{n},2^{n}}$. Therefore, cross-independent sets correspond to three directed graphs \[ G_{1}\subseteq \mathcal{A}_{1}\times \mathcal{A}_{2},G_{2}\subseteq \mathcal{A}_{2}\times \mathcal{A}_{3},G_{3}\subseteq \mathcal{A}_{3}\times \mathcal{A}_{1}, \] where each $\mathcal{A}_{i}$ is $\left\{ 0,1\right\} ^{n}.$ \end{exam} As mentioned above, this example can be generalized to arbitrary hypergraphs. In Section~\ref{sec:Mantel-proof}, we shall use this construction to give a spectral proof of Mantel's theorem for graphs with $2^{n}$ vertices. In this context, Mantel's theorem can be restated as follows: \begin{theo} Let $G_{1},G_{2},G_{3}$ be cross-independent sets in $X^{\otimes n}$. Suppose additionally that $G_{1},G_{2},G_{3}$ are all equal to some bipartite graph $G\subseteq\left(\left\{ 0,1\right\} \times\left\{ 0,1\right\} \right)^{n}$, and that $G$ corresponds to a graph in the sense that $\left(a,b\right)\in G$ if and only if $\left(b,a\right)\in G$ (in other words, $G$ is the bipartite cover of some graph). Then the largest value of $\left|G\right|$ is attained when $G$ is the dictatorship of all $x\in\left(\left\{ 0,1\right\} \times\left\{ 0,1\right\} \right)^{n}$ whose first coordinate is either $\left(0,1\right)$ or $\left(1,0\right)$. \end{theo} Indeed, the dictatorship of all $x\in\left(\left\{ 0,1\right\} \times\left\{ 0,1\right\} \right)^{n}$ whose first coordinate is either $\left(0,1\right)$ or $\left(1,0\right)$ corresponds to a balanced complete bipartite graph, which is extremal for Mantel's theorem. Interestingly enough, the dictatorships contain only some of the complete balanced bipartite graphs, but not all of them. \subsection{Extremal set theory} Many $p$-biased versions of problems in extremal set theory can be described as a special case of the problem: ``How large can $\alpha\left(X^{\otimes n}\right)$ be?'', where $X$ is a weighted hypergraph. \subsubsection{Erd{\H o}s Matching Conjecture} Our first example is the Erd{\H o}s Matching Conjecture~\cite{erdHos1965problem}, from 1965. An\emph{ $s$-matching} is a family of $s$ sets $\left\{ A_{1},\ldots,A_{s}\right\} $ that are pairwise disjoint. Erd{\H o}s asked how large can a family $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ be if it does not contain an $s$-matching. He conjectured that the extremal family is either the family of all sets that intersect a given set of size $s-1$ in at least one element, or the family $\binom{\left[ks-1\right]}{k}.$ The corresponding $p$-biased version of this problem is as follows: \begin{quotation} Given $p\le\frac{1}{s}$, how large can $\mu_{p}\left(\mathcal{F}\right)$ be if $\mathcal{F}$ does not contain an $s$-matching? \end{quotation} This is the problem of determining the independence number of the $n$-th tensor power of the $s$-uniform hypergraph whose vertex set is $\left\{ 0,1\right\} $ with the weight function $\mu([1,0,\dots,0])=sp$ and $\mu\left([0,\ldots,0]\right)=1-sp$ (recall that $[\cdot]$ is our notation for multiset). A nice feature of the $p$-biased variant of the Erd{\H o}s Matching Conjecture is that there is only one suggestion for the extremal family, which is the family of all sets that intersect a given set of size $s-1$ in at least one element. \subsubsection{$s$-wise Intersecting Families} The second example is the problem of $s$-wise intersecting families, first studied by Frankl~\cite{frankl1976sperner}. A family $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ is \emph{$s$-wise intersecting }if the intersection of every $s$ sets in $\mathcal{F}$ is nonempty. Frankl showed that when $k\le\tfrac{s-1}{s}n$, the extremal $s$-wise intersecting family is the family of all sets that contain a given element (otherwise every family is $s$-wise intersecting). The $p$-biased version of the problem was studied by Frankl and Tokushige~\cite{frankl2003weighted}. They showed that the largest value of $\mu_{p}\left(\mathcal{F}\right)$ for an $s$-wise intersecting family $\mathcal{F}$ is $p$, as long as $p\leq\frac{s-1}{s}$. This problem can be expressed as the determining the independence number of the $s$-uniform hypergraph $X^{\otimes n}$, where \begin{enumerate} \item The hypergraph $X=\left(V,\mu\right)$ has $\left\{ 0,1\right\} $ as its vertex set $V$. \item The induced distribution $\mu_{1}$ on $V$ is the $p$-biased one. \item $\mu\left(x\right)=0$ if $x$ is the all ones vector. \end{enumerate} It is easy to construct many hypergraphs $X$ that satisfy these hypotheses. We reprove this result in Section~\ref{sec:frankl-tokushige}. \subsubsection{Frankl's Tur{\'a}n Problem} Last but not least, this problem is related to Frankl's Tur{\'a}n problem on hypergraphs without extended triangles. A \emph{triangle} in $\mathcal{P}\left(\left[n\right]\right)$ is a $2k$-uniform hypergraph $\left\{ A,B,C\right\} $ such that each element of $\left[n\right]$ belongs to an even number of the sets $A,B,C.$ In other words, there exist disjoint $k$-element sets $D,E,F$ such that $D\cup E=A$, $D\cup F=B$, and $E\cup F=C$. Frankl~\cite{frankl1990asymptotic} asked how large can a family $\mathcal{F}\subseteq\binom{\left[n\right]}{2k}$ be if it does not contain a triangle. The reason for considering only even uniformities is that no $k$-uniform triangle exists for an odd $k$. The $p$-biased version of the problem is as follows: \begin{quotation} Given $p\le\frac{2}{3}$, how large can $\mu_{p}\left(\mathcal{F}\right)$ be if $\mathcal{F}\subseteq\mathcal{P}\left(\left[n\right]\right)$ does not contain a triangle? \end{quotation} The reason for the condition $p\le\frac{2}{3}$ is the fact that the family $\left\{ A:\,\left|A\right|>\frac{2}{3}n\right\} $ is triangle-free, and its $p$-biased measure tends to $1$ as $n$ tends to infinity. The $p$-biased version of Frankl's Tur{\'a}n problem is the problem of determining the independence number of the $3$-uniform hypergraph $X^{\otimes n},$ where $X=\left(V,\mu\right)$ is with $V=\left\{ 0,1\right\} $ and \[ \mu\left([1,1,0]\right)=\frac{3}{2}p,\:\mu\left([0,0,0]\right)=1-\frac{3}{2}p. \] In Section~\ref{sec:Frankl-triangle} we prove the following theorem: \begin{theo} If a family of $2k$-subsets of $[n]$ contains no three distinct subsets whose symmetric difference is empty, where $n \geq 3k$, then the family contains at most $\frac{2k}{\min(n,4k-1)}\binom{n}{2k}$ subsets. Furthermore, when $n\le4k-1$ and $p\ge1/2$ the bounds are tight for ``dictatorships'' (all subsets or vectors containing a specific point), and otherwise the bounds are asymptotically tight, in the $p$-biased case for the family of all vectors having odd parity, and in the $2k$-uniform case for the family of all subsets whose intersection with $[\lfloor n/2\rfloor]$ is odd. Similarly we prove that if a subset of $\{0,1\}^{n}$ contains no three distinct vectors summing to zero, then for all $p\le2/3$, its $\mu_{p}$-measure is at most $\max(p,1/2)$. \end{theo} \section{High-dimensional Hoffman bound\label{sec:High-dimensional-Hoffman}} Suppose we are given a problem in extremal set theory where constraints on more than two elements are involved. A possible strategy for solving it is to first incorporate families $\mathcal{F}$ that satisfy the constraint as independent sets in some hypergraph or simplical complex, and then to find and apply a high-dimensional generalization of the Hoffman bound in order to bound the size of $\mathcal{F}$. Two such generalizations of the Hoffman bound were obtained by the second author in~\cite{golubev2016chromatic}, and by Bachoc, Gundert, and Passuello in~\cite{bachoc2019theta}. However, none of them seem to give sharp results in our problems of interest. Instead, we develop a different generalization of the Hoffman bound in the spirit of~\cite{golubev2016chromatic}. Let $X=(V,\mu)$ be a $k$-uniform hypergraph on the vertex set $V$. Recall (see Subsection~\ref{subsec:Notations}) that for $0\leq i\leq k-2$ we denote by $\lambda_{i}\left(X\right)$ the minimal possible value of an eigenvalue of the normalized adjacency matrix of the skeleton of the link of an $i$-face of $X$. That is, \[ \lambda_{i}\left(X\right)=\min_{\sigma\in X^{\left(i\right)}}\left[\lambda\left(S\left(X_{\sigma}\right)\right)\right]. \] Note that the hypergraph itself is the link of the only $0$-face, the empty set, and hence $\lambda_{0}(X)$ is just the smallest eigenvalue the normalized adjacency operator on the skeleton of $X$. \begin{exam} \looseness-1 Let $X=\left(\left\{ 0,1\right\} ,\mu\right)$ be a graph (in other words, a $2$-uniform hypergraph) on two vertices $\left\{ 0,1\right\} $ with the probability measure $\mu$ defined on the edges as \[ \mu\left(\left\{0,0\right\}\right)=p_{1},\:\mu\left(\left\{0,1\right\}\right)=p_{2},\:\mu\left(\left\{1,1\right\}\right)=p_{3}. \] Then the induced distribution $\mu_{1}$ on the vertices is as follows: \[ \mu_{1}(0)=p_{1}+\frac{1}{2}p_{2},\:\mu_{1}(1)=\frac{1}{2}p_{2}+p_{3}. \] The normalized adjacency operator $T_{X}$ on the skeleton of $X$ has the matrix form \[ T_{X}=%\left( \begin{pmatrix} \frac{p_{1}}{p_{1}+\frac{1}{2}p_{2}} & \frac{\frac{1}{2}p_{2}}{p_{1}+\frac{1}{2}p_{2}}\\ \frac{\frac{1}{2}p_{2}}{\frac{1}{2}p_{2}+p_{3}} & \frac{p_{3}}{\frac{1}{2}p_{2}+p_{3}} \end{pmatrix} %\right) \] and while its largest eigenvalue is equal to $1$, the smallest one is equal to \[ \lambda_{0}(X)=1-\frac{2p_{2}}{1-(p_{1}-p_{3})^{2}}. \] \end{exam} \begin{theo} [Restatement of first part of Theorem~{\ref{thm:bound-intro}}] \label{thm:Generalized-Hoffman-bound} Let $X=\left(V,\mu\right)$ be a $k$-uniform hypergraph. Then \begin{equation} \alpha\left(X\right)\le1-\frac{1}{\left(1-\lambda_{0}\right)\left(1-\lambda_{1}\right)\cdots\left(1-\lambda_{k-2}\right)}.\label{eq:generalized Hoffman bound} \end{equation} \end{theo} \begin{proof} The proof goes by induction on the uniformity of the hypergraph. The base case, $k=2$, is the graph case, and the bound~\eqref{eq:generalized Hoffman bound} reads as the classical Hoffman bound. Assume that the bound holds for $(k-1)$-uniform hypergraphs. Let $T_{X}$ be the normalized adjacency operator of the skeleton of $X$, and let $v_{1}=1,v_{2},\ldots,v_{m}$ be an orthonormal basis of its eigenvectors with eigenvalues $1\ge l_{2}\ge\cdots\ge l_{m}=\lambda_{0}$ (recall that $T_{X}$ is self-adjoint). Let $I$ be an independent set of measure $\alpha(X)$, and let $f=1_{I}$ be its indicator function. We may write \[ f=\sum_{i=1}^{m}\left\langle f,v_{i}\right\rangle v_{i}. \] On the one hand, \[ \left\langle T_{X}f,f\right\rangle =\Pr_{[\boldsymbol{x},\boldsymbol{y}]\sim\mu_{2}}\left[\boldsymbol{x},\boldsymbol{y}\in I\right], \] or in other words, it is equal to the probability of an ordered edge ($2$-face) distributed according to $\mu_{2}$ to have both ends in $I$. On the other hand, \begin{align*} \left\langle T_{X}f,f\right\rangle & =\sum_{i=1}^{m}l_{i}\left\langle f,v_{i}\right\rangle ^{2}\\ & \ge\left\langle f,1\right\rangle ^{2}+\sum_{i=2}^{m}\lambda_{0}\left\langle f,v_{i}\right\rangle ^{2}\\ & =\left\langle f,1\right\rangle ^{2}\left(1-\lambda_{0}\right)+\lambda_{0}\left\langle f,f\right\rangle \\ & =\mathbb{E}\left[f\right]^{2}\left(1-\lambda_{0}\right)+\lambda_{0}\mathbb{E}\left[f^{2}\right]. \end{align*} Since $f$ is an indicator function, $\mathbb{E}[f]=\mathbb{E}[f^{2}]=\alpha(X)$, and so \[ \Pr_{[\boldsymbol{x},\boldsymbol{y}]\sim\mu_{2}}\left[\boldsymbol{x},\boldsymbol{y}\in I\right]\geq\alpha(X)^{2}\left(1-\lambda_{0}\right)+\lambda_{0}\alpha(X). \] Note that \[ \Pr_{[\boldsymbol{x},\boldsymbol{y}]\sim\mu_{2}}\left[\boldsymbol{x},\boldsymbol{y}\in I\right]\leq\alpha(X)\cdot\max_{x\in I}\Pr_{\boldsymbol{y}\sim\mu_{1}(X_{x})}\left[\boldsymbol{y}\in I\right] \] and that for a fixed vertex $x$, the probability $\Pr_{y\sim\mu_{1}(X_{x})}\left[\boldsymbol{y}\in I\right]$ is the measure of an independent set of vertices in its link $X_{x}$, which is a $(k-1)$-uniform hypergraph. By the inductive assumption, \[ \Pr_{y\sim\mu_{1}(X_{x})}\left[\boldsymbol{y}\in I\right] \leq 1 - \frac{1}{(1-\lambda_0(X_x))\cdots(1-\lambda_{k-3}(X_x))}. \] Clearly $\lambda_i(X_x) \geq \lambda_{i+1}$. Since the expression on the right-hand side is monotone decreasing in $\lambda_i(X_x)$, \[ \Pr_{y\sim\mu_{1}(X_{x})}\left[\boldsymbol{y}\in I\right]\leq1-\frac{1}{\left(1-\lambda_{1}\right)\cdots\left(1-\lambda_{k-2}\right)}. \] Combining the above bounds, we deduce that \[ (1-\lambda_{0})\alpha(X)+\lambda_{0}\leq\Pr_{y\sim\mu_{1}(X_{x})}\left[\boldsymbol{y}\in I\right]\leq1-\frac{1}{\left(1-\lambda_{1}\right)\cdots\left(1-\lambda_{k-2}\right)}, \] which proves the required bound after rearrangement. \end{proof} Suppose now that an independent set $I$ attains the bound in Theorem~\ref{thm:Generalized-Hoffman-bound}. Then the following inequality involving $f = 1_I$ is tight: \[ \langle T_X f,f \rangle = \sum_{i=1}^m l_i \langle f,v_i \rangle^2 \geq \langle f,1 \rangle^2 + \sum_{i=2}^m \lambda_0 \langle f,v_i \rangle^2, \] and so $f - \mathbb{E}[f]$ belongs to the eigenspace of $\lambda_0$. Furthermore, for each $x \in I$, the bound \[ \Pr_{\boldsymbol{y} \sim \mu_1(X_x)}[\boldsymbol{y} \in I] \leq 1 - \frac{1}{(1 - \lambda_0(X_x)) \cdots (1-\lambda_{k-3}(X_x))} \] is tight, and $\lambda_i(X_x) = \lambda_{i+1}$ for $0 \leq i \leq k-3$. We obtain the following tightness condition. \begin{theo} \label{cor:Generalized-Hoffman-bound} If $I$ is an independent set attaining the bound in Theorem~\ref{thm:Generalized-Hoffman-bound} then for every multiset $A \subseteq I$ of size $\ell \leq k-2$: \begin{itemize} \item $\lambda_i(X_A) = \lambda_{i+\ell}$ for $0 \leq i \leq k-2-\ell$. In particular, $\lambda_0(X_A) = \lambda_\ell$. \item $f - \mu_A(I)$ lies in the $\lambda_\ell$-eigenspace of $T_{X_A}$. \end{itemize} \end{theo} \subsection{Comparison to prior work} \label{sec:comparison} \looseness-1 There are two known spectral upper bounds on the independence number of a hypergraph (equivalently, a simplicial complex): one in~\cite{golubev2016chromatic}, to which we will refer as \emph{the Laplacian bound}, and one in~\cite{bachoc2019theta}, to which we will refer as \emph{the Theta bound}. To the bound in Theorem~\ref{thm:Generalized-Hoffman-bound} we will refer as \emph{the Link bound}. The Link bound and the Laplacian bound are based on the same idea. Namely, the bound on the size of an independent set is obtained via a combination of a lower and an upper bound on the number of $2$-faces between the maximal independent set and its complement. However the comparison between them does not seem to be straightforward. It is not clear how the spectra of the Laplace operators relate to the spectra of the normalized adjacency operators of the links used to prove the Link bound in the general case. The Theta bound follows a different approach. In~\cite{bachoc2019theta}, the authors show that the Theta bound is incomparable to the Laplacian bound by providing four families of simplicial complexes, on half of them one bound is sharp while the other is not, and vice versa. The Link bound is sharp for all four examples provided in~\cite{bachoc2019theta}, as we show below. In other words, the Link bound performs at least as good, and sometimes better, as the Theta bound and the Laplacian bound. However, we do not have a proof that it is always the case in general. Here are the examples considered in~\cite{bachoc2019theta}: \begin{enumerate} \item Let $S$ be a set of $3m$ elements of three colors, each color appearing $m$ times. What is the largest size of a subset of $S$ in which no triple of elements contains all three colors? In other words, what is the largest independent set of the 3-partite 3-uniform hypergraph on $3m$ vertices. The answer is $2m$. This is shown by the Theta bound by not by the Laplacian bound. The Link bound is also sharp: if we introduce the uniform measure on the hypergraph, then $\lambda_0 = -\frac{1}{2}$ and $\lambda_1 = -1$, and the Link bound reads as $\frac{2}{3}$, which is exactly the measure of the set of $2m$ vertices. \item Consider the set $S$ again. What is the largest size of a subset of $S$ in which each triple of elements contains all three colors? The answer is $3$. This is again shown by the Theta bound by not by the Laplacian bound. The Link bound is also sharp. To show this, we consider the 3-uniform hypergraph whose triangles are all triples of distinct elements of $S$ in which not all colors are the same. We introduce a measure which gives each monochromatic triangle a probability $p_1$ and each bichromatic triangle a probability $p_2$, where $p_1 = 2p_2$. We compute $\lambda_0 = -\frac{1}{2m-1}$ and $\lambda_1 = -\frac{1}{2m-2}$, and so the Link bound reads as $\frac{1}{m} = \frac{3}{3m}$. \item Let $T$ be a set of $2m$ elements of two colors, each color appearing $m$ times. What is the largest size of a subset of $T$ in which no triple of elements contains both colors? The answer is $m$. This is shown by both the Theta bound and the Laplacian bound, and so also by the Link bound. The Link bound is also sharp: if we introduce the uniform measure on the 3-uniform hypergraph whose triangles are all bichromatic triples of distinct elements of $T$, then $\lambda_0 = -\frac{1}{3}$ and $\lambda_1 = -\frac{1}{2}$, and the Link bound reads as $\frac{1}{2}$, which is exactly the measure of the set of $m$ vertices. \item Consider the set $T$ again. What is the largest size of a subset of $T$ in which each triple of elements contains both colors? The answer is $4$. This is shown by the Laplacian bound and so also by the Link bound, but not by the Theta bound. The Link bound is also sharp: if we introduce the uniform measure on the 3-uniform hypergraph whose triangles are all monochromatic triples of distinct elements of $T$, then $\lambda_0 = -\frac{1}{m-1}$ and $\lambda_1 = -\frac{1}{m-2}$, and so the Link bound reads as $\frac{2}{m} = \frac{4}{2m}$. \end{enumerate} More details on these examples can be found in Appendix~\ref{sec:appendix}. \subsection{Sharpness of Hoffman bound on \texorpdfstring{$X$}{X} implies sharpness in \texorpdfstring{$X^{\otimes n}$}{X otimes n}}\label{subsec:Sharpness-of-tensor} The goal of this section is to prove that the bound~\eqref{eq:generalized Hoffman bound} remains sharp for tensor powers of a hypergraph if it is sharp for the hypergraph itself given all the minimal eigenvalues are negative. First recall the following definition. \begin{defi} The tensor product $X\otimes X'$ of two $k$-uniform hypergraphs $X=\left(V,\mu\right)$ and $X'=\left(V',\mu'\right)$ is a $k$-uniform hypergraph $(V\times V',\mu\times\mu')$, where $\mu\times\mu'$ stands for the product measure on $(V\times V')^{[k]}\simeq V^{[k]}\times V'^{[k]}$. For a $k$-uniform hypergraph $X$, we denote by $X^{\otimes n}=\underbrace{X\otimes\dots\otimes X}_{n}$ its $n$-th tensor power. \end{defi} \begin{prop} \label{prop:ten-prod-evs}Let $Y=X\otimes X'$ be the tensor product of $k$-uniform hypergraphs $X$ and $X'$. Then for all $0\leq i -1$ then an independent set attaining the bound is a dictatorship (depends on at most one of the $n$ input coordinates). \end{theo} \begin{proof} It is a direct corollary of Proposition~\ref{prop:ten-prod-evs} that the r.h.s. of the bound~\eqref{eq:generalized Hoffman bound} is the same for $X^{\otimes n}$ as for $X$. In order to show that it is sharp, note that if $I\subseteq V$ is a maximal independent set in $X$, that is $\mu(I)=\alpha(X)$, then the set $(I,V,\dots,V)\subseteq V^{n}$ is independent in $X^{\otimes n}$. Suppose now that $I$ is an independent set attaining the bound. Theorem~\ref{cor:Generalized-Hoffman-bound} shows that $1_I - \mu(I)$ lies in the $\lambda_0$-eigenspace of $T_{X^{\otimes n}}$, which consists of functions depending on a single coordinate. Therefore we can express $f = 1_A$ in the form \[ f(x_1,\ldots,x_n) = \sum_{i=1}^n \phi_i(x_i). \] Since $f$ is Boolean, at most one $\phi_i$ can be non-constant, and so $f$ is a dictator. \end{proof} \subsection{Computing the generalized Hoffman bound} Given a $k$-uniform hypergraph $X$ on the vertex set $V$ and a distribution $\nu$ on $V$, the generalized Hoffman bound gives an upper bound on the $\nu$-measure of an independent set of $X$ for each $k$-uniform weighted hypergraph $X=(V,\mu)$ whose weight function satisfies the following two constraints: $\mu_{1}=\nu$ and $\mu(x)=0$ whenever $x\notin X$. We can formulate the best bound obtainable in this way as a problem whose variables are the entries of $\mu$: \[ \begin{aligned}\min\: & (1-\lambda_{0})\cdots(1-\lambda_{k-2})\\ s.t.\: & T_{X_{s}}\succeq\lambda_{|s|}\Id \\ & \mu_{1}=\nu\\ & \mu(x)=0\;\forall x\notin X\\ & \mu\geq0 \end{aligned} \] In this program, $s$ goes over all possible faces, $T_{X_{s}}\succeq\lambda_{|s|}\Id $ means that $T_{X_{s}}-\lambda_{|s|}\Id $ is positive semidefinite, and $\mu\geq0$ means that all entries of $\mu$ are nonnegative. If a solution to the program has objective value $\beta$, then this gives a bound of $1-1/\beta$ on the $\alpha$-measure of an independent set of $ X$. Since the maximal eigenvalue of $T_{X_{s}}$ is always $1$, we can rephrase the constraint $T_{X_{s}}\succeq\lambda_{|s|}\Id $ equivalently as follows: the spectral radius of $\Id -T_{X_{s}}$ is at most $1-\lambda_{|s|}$. Using Schur complements, this is easily seen to be equivalent to the semidefinite constraint \[ %\left( \begin{pmatrix} (1-\lambda_{|s|})\Id & \Id -T_{X_{s}}\\ \Id -T_{X_{s}}^{T} & (1-\lambda_{|s|})\Id \end{pmatrix}%\right) \succeq0. \] Making $1-\lambda_{|s|}$ a variable, we have expressed the problem of finding the best generalized Hoffman bound as minimizing a semidefinite program whose objective value is a product of $k-1$ variables. When $k=2$, this is just a semidefinite program, which can be solved efficiently; up to the nonnegativity constraint $\mu\geq0$, we have recovered the Lov{\'a}sz $\theta$ function. When $k>2$, the objective function is no longer convex, and it is not clear how to solve the program efficiently. \section{Frankl's problem on extended triangles\label{sec:Frankl-triangle}} \subsection{The uniform version} Frankl's Tur{\'a}n problem on hypergraphs without extended triangles reads as follows. A \emph{triangle} in $\mathcal{P}\left(\left[n\right]\right)$, the power set on $[n]$, is a $2k$-uniform hypergraph supported on three sets $\left\{ A,B,C\right\} $ such that each element of $\left[n\right]$ belongs to an even number of the sets $A,B,C.$ In other words, there exist disjoint $k$-element sets $D,E,F$ such that $D\cup E=A,$ $D\cup F=B,$ and $E\cup F=C.$ Frankl~\cite{frankl1990asymptotic}, asked how large can a family $\mathcal{F}\subseteq\binom{\left[n\right]}{2k}$ be if it does not contain a triangle. The reason for considering only even uniformities is that no $k$-uniform triangle exists for an odd $k$. Equivalently, we are interested in the maximum independent set in the 3-uniform hypergraph $ X$ whose vertices are the $2k$-subsets of $[n]$ and whose hyperedges are triangles. The skeleton of $ X$ is the graph on the same set of vertices whose edges are pairs of subsets whose intersection has size exactly $k$. This graph is also known as the generalized Johnson graph $J(n,2k,k)$. Brouwer, Cioab\u{a}, Ihringer and McGinnis~\cite[Theorem 3.10]{brouwer2018smallest} showed that when $3k\le n\le4k-1$, the minimum eigenvalue is \[ \lambda_{0}=\frac{n-4k}{2(n-2k)}=1-\frac{n}{2(n-2k)}. \]\iffalse \[ \lambda_{0}=\frac{E_{k}(1)}{E_{k}(0)}=\frac{n-4k}{2(n-2k)}=1-\frac{n}{2(n-2k)}. \]\fi Since the $3$-faces in $X$ are the triples of the form $A,B,A\triangle B$, the link of a vertex is a perfect matching, hence $\lambda_{1}=-1$. It follows that when $3k\le n\le4k-1$, the size of an independent set is at most \[ \binom{n}{2k}\left(1-\frac{1}{2(1-\lambda_{0})}\right)=\binom{n-1}{2k-1}. \] In particular, when $n=4k-1$, an independent set contains at most a $\frac{2k}{4k-1}$ fraction of subsets. %(Here and in the sequel, $O(\frac{1}{k})$ stands for a quantity whose magnitude is bounded by $\frac{C}{k}$ for some absolute constant $C$.) Furthermore, if $I$ is an independent set of maximal size and $f = 1_I$ then $f - \mathbb{E}[f]$ must belong to the eigenspace of $\lambda_0$. When $3k\le n < 4k-1$, this eigenspace consists of all functions of degree~$1$ (this follows from the techniques of Brouwer et al.), and so $\deg f \leq 1$, implying that $f$ is a dictatorship (see~\cite{filmus2019degree1}).\footnote{When $n = 4k-1$, the methods of Brouwer et al.\ only imply that $\deg f \leq 2$. Indeed, there are other examples: all sets intersecting $\{i,j\}$ at exactly one point. We thank Ferdinand Ihringer for this example.} Now suppose that $n\ge4k$, and let $\mathcal{F}$ be a triangle-free family. Consider the following random experiment: choose a random $(4k-1)$-subset $S$ of $[n]$, and check whether a random $2k$-subset of $S$ belongs to $\mathcal{F}$. On the one hand, this is at most $\frac{2k}{4k-1}$. On the other hand, this is equal to the density of $\mathcal{F}$. This completes the proof of the following theorem. \begin{theo} If $\mathcal{F}$ is a family of $2k$-subsets of $[n]$ which does not contain three distinct subsets whose symmetric difference is empty, then $|\mathcal{F}|\le\binom{n-1}{2k-1}$ if $3k\le n\le4k-1$, and $|\mathcal{F}|\leq(\frac{1}{2}+\frac{1}{8k-2})\binom{n}{2k}$ if $n \geq 4k$. This bound is sharp: If $3k\le n\le4k-1$ then the family of $2k$-sets containing a fixed element satisfies the condition and has size $\binom{n-1}{2k-1}$. Furthermore, these are the unique examples if $n < 4k-1$. If $n \geq 4k$ then the family of $2k$-sets containing an odd number of elements among the first $\lfloor n/2\rfloor$ satisfies condition and asymptotically contains half the $2k$-sets. \end{theo} Frankl~\cite{frankl1990asymptotic} gave the upper bound $(\frac{1}{2}+\frac{2k}{n-4k})\binom{n}{2k}$, which is better when $n > (4k)^2$. \subsection{The \texorpdfstring{$p$}{p}-biased version} \label{sec:frankl-triangle-pbiased} The $p$-biased version of the problem is as follows: \begin{quotation} Given $p\le\frac{2}{3}$, how large can $\mu_{p}\left(\mathcal{F}\right)$ be if $\mathcal{F}\subseteq\mathcal{P}\left(\left[n\right]\right)$ does not contain a triangle? \end{quotation} The reason for the condition $p\le\frac{2}{3}$ is the fact that the example $\left\{ A:\,\left|A\right|>\frac{2}{3}n\right\} $ is triangle-free, and its $p$-biased measure tends to $1$ as $n$ tends to infinity. The $p$-biased version of Frankl's problem is the problem of determining the independence number of the $3$-uniform hypergraph $X^{\otimes n},$ where $X=\left(V,\mu\right)$ is with $V=\left\{ 0,1\right\} $ and \[ \mu\left([1,1,0]\right)=\frac{3}{2}p,\:\mu\left([0,0,0]\right)=1-\frac{3}{2}p. \] The induced measures are \begin{gather*} \mu_{2}([1,1])=\frac{1}{2}p,\:\mu_{2}\left([1,0]\right)=p,\:\mu_{2}\left([0,0]\right)=1-\frac{3}{2}p;\\ \mu_{1}(0)=1-p,\:\mu_{1}(1)=p. \end{gather*} And therefore, the matrix of the normalized adjacency operator $T_{X}$ on the skeleton of $X$ is \[ T_{X}= %\left( \begin{pmatrix} \frac{1-\frac{3}{2}p}{1-p} & \frac{\frac{1}{2}p}{1-p}\\ \frac{\frac{1}{2}p}{p} & \frac{\frac{1}{2}p}{p} \end{pmatrix} %\right) = %\left( \begin{pmatrix} \frac{2-3p}{2(1-p)} & \frac{p}{2(1-p)}\\ \frac{1}{2} & \frac{1}{2} \end{pmatrix} %\right) , \] with eigenvalues $1$ and $\frac{1-2p}{2(1-p)}$. The induced distribution on the link of $[0]$ is supported on the faces $[0,0]$ and $[1,1]$, hence the corresponding matrix $T_{X_{0}}$ is \[ T_{X_{0}}= %\left( \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix} %\right) , \] while the link of $[1]$ is supported on $[0,1]$, and $T_{X_{1}}$ is \[ T_{X_{1}}=\begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}. \] The above shows that $\lambda_{0}=\frac{1-2p}{2(1-p)}$ and $\lambda_{1}=-1$. When $p > 1/2$, $\lambda_{0}$ is negative, implying \[ \alpha(X^{\otimes n})\leq1-\frac{1}{(1-\frac{1-2p}{2(1-p)})\cdot2}=p. \] Moreover, $\lambda_0 > -1$, and so all extremal families are dictators. When $p\le1/2$, $\lambda_{0}(X)$ is nonnegative, and so $\lambda_{0}(X^{\otimes n})\ge0$, implying \[ \alpha(X^{\otimes n})\leq1-\frac{1}{1\cdot2}=\frac{1}{2}. \] This completes the proof of the following statement. \begin{theo} Let $\{0,1\}^{n}$ denote the space of $\{0,1\}$-vectors of length $n$, and $\mu$ be the $p$-biased measure on it, with $p\leq2/3$. If $\mathcal{F}\subseteq\{0,1\}^{n}$ is a family of vectors which does not contain three distinct vectors whose sum to zero, then $\mu(\mathcal{F})\leq\max(p,1/2)$. This bound is sharp: if $p\leq1/2$ then the family of vectors having odd parity satisfies the condition and has measure tending to $1/2$ as $n\to\infty$, and if $p>1/2$ then the set of all vectors having $1$ as their first coordinate satisfies the condition and has measure $p$, and moreover these are the unique extremal families. \end{theo} \section{Mantel's Theorem}\label{sec:Mantel-proof} The classical Mantel's theorem bounds the number of edges in a triangle-free graph. \begin{theo}[\cite{mantel1907}] If a graph on $n$ vertices contains no triangles, then it contains at most $\left\lfloor \frac{n^{2}}{4}\right\rfloor $ edges. \end{theo} \goodbreak Mantel's theorem has many different proofs. We give a new proof of Mantel's theorem for graphs with $2^{n}$ vertices that relies on a variation of the bound~\eqref{eq:generalized Hoffman bound}. Ours is not the first spectral proof of Mantel's theorem: Tait and Tobin~\cite{tait2017three} give a very simple such proof. However, their proof is very similar to existing arguments, such as the ones that can be found in Zhao's lecture notes~\cite{zhao2019}. In contrast, our proof is rather different from all existing ones. Apart from presenting a ``genuine'' spectral proof of this fundamental result, we would like to show the flexibility of the presented spectral approach. In some cases, one can improve the bound~\eqref{eq:generalized Hoffman bound} by taking not the smallest eigenvalue of the normalized adjacency operator but a larger one. This is possible when the characteristic function of the independent set we are interested in is orthogonal to the eigenfunctions that correspond to smaller eigenvalues. \begin{proof} First, we encode the statement of the theorem in terms of the independent sets of a hypergraph. Let $G$ be a triangle-free graph on $2^{n}$ vertices, which we identify with the set $[2^{n}]$. Let $\mathcal{X}_{2^{n}}$ be a $3$-partite $3$-uniform hypergraph on the vertex set $V=V_{1}\cup V_{2}\cup V_{3}$, where each part $V_{i},\:i=1,2,3,$ is a copy of the set $\left[2^{n}\right]\times\left[2^{n}\right]$. The $3$-faces of $\mathcal{X}_{2^{n}}$ are the triples of the form $\left[\left(i,j\right),\left(j,k\right),\left(k,i\right)\right]$, where $1\leq i,j,k\leq2^{n}$. Assume the probability distribution on the $3$-faces to be the uniform probability distribution on these triples. We encode $G$ as an independent set $I$ of $\mathcal{X}_{2^{n}}$, namely, $I=I_{1}\cup I_{2}\cup I_{3}$, where for each $i=1,2,3$, \[ I_{i}=\left\{ \left(v,u\right)\in V_{i}:\,\text{the set }\left\{ v,u\right\} \text{ makes an edge of }G\right\} . \] Note that $\mathcal{X}_{2}^{\otimes n}=\mathcal{X}_{2^{n}}$ and hence this gives the desired encoding of $G$ as the independent set $I$ in a $3$-uniform hypergraph which is also a tensor power. It follows immediately from the construction of $\mathcal{X}_{2^{n}}$, in particular, from the fact that it is $3$-partite, that the matrix of the normalized adjacency operator $T$ on the skeleton of $\mathcal{X}_{2^{n}}$ is the Kronecker product of the following $3\times3$ matrix \[ M=\begin{pmatrix} 0 & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & 0 & \frac{1}{2}\\ \frac{1}{2} & \frac{1}{2} & 0 \end{pmatrix} \] and the matrix $M_{n}$ which, in turn, is the $n$-th tensor power of $M_{1}$, given by the following $4\times4$ matrix indexed by the elements of $[2]\times[2]$: \[ \left.M_{1}=\begin{matrix} \left(1,1\right)\\ \left(1,2\right)\\ \left(2,1\right)\\ \left(2,2\right) \end{matrix}\underset{\begin{array}{cccc} \left(1,1\right) & \left(1,2\right) & \left(2,1\right) & \left(2,2\right)\end{array}}{\begin{cases} \underbrace{\left( {\renewcommand{\arraycolsep}{9pt}\begin{array}{@{}cccc@{}} \frac{1}{2} & \frac{1}{4} & \frac{1}{4} & 0\\ \frac{1}{4} & 0 & \frac{1}{2} & \frac{1}{4}\\ \frac{1}{4} & \frac{1}{2} & 0 & \frac{1}{4}\\ 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{2} \end{array}}\right)}\end{cases}}.\right. \] Since $T$ is the Kronecker product of $M$ and $M_{n}$, its eigenvalues are exactly the products of the eigenvalues of $M$ and $M_{n}$. The eigenvectors and eigenvalues of $M$ are \[ \left(\left(\begin{matrix} 1\\ 1\\ 1 \end{matrix}\right),1\right),\left(\left(\begin{matrix} 1\\ 0\\ -1 \end{matrix}\right),-\frac{1}{2}\right), \left(\left(\begin{matrix} 1\\ -1\\ 0 \end{matrix}\right),-\frac{1}{2}\right). \] The eigenvectors and eigenvalues of $M_{1}$ are \begin{align*} \left(\chi_{1},\lambda_{1}\right)&=\left(\left(\begin{matrix} 1\\ 1\\ 1\\ 1 \end{matrix}\right),1\right),& \left(\chi_{2},\lambda_{2}\right)&=\left(\left(\begin{matrix} -1\\ 1\\ 1\\ -1 \end{matrix}\right),0\right),\\ \left(\chi_{3},\lambda_{3}\right)&=\left(\left(\begin{matrix} 1\\ 0\\ 0\\ -1 \end{matrix}\right),\frac{1}{2}\right),&\left(\chi_{4},\lambda_{4}\right) &=\left(\left(\begin{matrix} 0\\ 1\\ -1\\ 0 \end{matrix}\right),-\frac{1}{2}\right). \end{align*} We now exploit the symmetries of the set $I$ to show that its characteristic function $1_{I}$ is orthogonal to the subspace of eigenvectors of $T$ with negative eigenvalues. First, note that the set $I$ is invariant under the action of the symmetric group $S_{3}$ acting on $\mathcal{X}_{2^{n}}$ by permutations of the parts $\left\{ V_{1},V_{2},V_{3}\right\} $. The only eigenvector of $M$ invariant under the action of $S_{3}$ is the constant vector with eigenvalue $1$. A vertex in $\mathcal{X}_{2}$ is a pair $\left(i,j\right)$. Let $\mathcal{S}_{0}$ be the operator that swaps between $i$ and $j$, which satisfies \[ \mathcal{S}_{0}\chi_{i}=\begin{cases} \chi_{i} & \text{if } i=1,2,3;\\ -\chi_{i} & \text{if } i=4. \end{cases} \] The operator $\mathcal{S}$ that swaps the coordinates of a vertex in $\mathcal{X}_{2^{n}}$ is of the form $\mathcal{S}=\mathcal{S}_{0}^{\otimes n}$. The set $I$ is invariant under the action of $\mathcal{S}$ by the construction. Since the characteristic function $1_{I}$ is orthogonal to the subspace spanned by eigenvectors of the normalized adjacency operator with negative eigenvalues, we may take $0$ instead of $\lambda_{0}$ in~\eqref{eq:generalized Hoffman bound}. Note that since the link of most vertices in $\mathcal{X}_{2^{n}}$ is bipartite, $\lambda_{1}=-1$ (which is the minimal possible eigenvalue of a Markov matrix). Hence, the bound~\eqref{eq:generalized Hoffman bound} reads as \[ \frac{|I|}{3\cdot4^{n}}\leq1-\frac{1}{1\cdot2}=\frac{1}{2}. \] Taking into account the fact that every edge of $G$ is counted six times in $|I|$ completes the proof. \end{proof} \section{Frankl--Tokushige Theorem on Intersecting Families} \label{sec:frankl-tokushige} Our method also provides a new proof for the result of Frankl and Tokushige on $k$-wise intersecting families~\cite{frankl2003weighted}. \begin{theo}[\hspace{1sp}\cite{frankl2003weighted}] Let $k\ge2$ and $p\leq\frac{k-1}{k}$. Assume $\mathcal{F}\subset\mathcal{P}([n])$ is $k$-wise intersecting, that is, for all $F_1,\dots,F_k\in\mathcal{F}$ \[ F_1\cap\dots\cap F_k \neq \emptyset. \] Then $\mu_p(\mathcal{F}) \leq p$, where $\mu_p$ stands the $p$-biased measure. This bound is attained by dictators, uniquely (unless $k=2$ and $p=1/2$). \end{theo} \begin{proof} We will show that the theorem holds for all $\frac{k-2}{k-1} \leq p \leq \frac{k-1}{k}$. If $p < \frac{k-2}{k-1}$ then we can deduce the theorem by applying it for $k := k-1$, since a $k$-wise intersecting family is also $(k-1)$-wise intersecting. Let $X$ be the $k$-uniform hypergraph on $\{0,1\}$ weighted by the measure $\mu([0^{(k)}])=1-\frac{k}{k-1}p$, $\mu([0,1^{(k-1)}])=\frac{k}{k-1}p$. Here $0^{(k)}$ means $k$ copies of $0$. The induced measure $\mu_1$ on the vertex set $\{0,1\}$ is the $p$-biased one, \ie $\mu_1(1) = p$ and $\mu_1(0)=1-p$. The matrix form of $T_{X}$ is directly calculated to be \[ \begin{pmatrix}\frac{1-\frac{k}{k-1}p}{1-p} & \frac{\frac{1}{k-1}p}{1-p}\\ \frac{1}{k-1} & \frac{k-2}{k-1} \end{pmatrix}, \] from which it follows that its smallest eigenvalue is $\lambda_{0} = \frac{\frac{k-2}{k-1}-p}{1-p}\le0$, hence $\frac{1}{1-\lambda_{0}}=(k-1)(1-p)$. Furthermore, $\lambda_0 > -1$ as long as $p < 1 - \frac{1}{2(k-1)}$, which is automatically satisfied when $k > 2$. In order to calculate $\lambda_{i}$ for $i>0$, notice that the only links with non-trivial $\mu_{1}(X_{S})$ are of the faces $S=[1^{\ell}]$. The matrix form of $T_{X_{S}}$ is directly calculated to be \[ \begin{pmatrix}0 & 1\\ \frac{1}{k-1-\ell} & \frac{k-2-\ell}{k-1-\ell} \end{pmatrix}, \] and so $\lambda_{\ell}=-\frac{1}{k-1-\ell}<0$ and $\frac{1}{1-\lambda_{\ell}}=\frac{k-1-\ell}{k-\ell}$. Applying the generalized Hoffman bound for tensor powers (Theorem~\ref{thm:bound-intro}), we conclude \[ \alpha(X^{\otimes n})\leq1-(k-1)(1-p)\cdot\frac{k-2}{k-1}\cdot\cdots\cdot\frac{1}{2}=p. \] Since the edges of $X$ are exactly the multisets with either all 0's or exactly one 0, every $k$-wise intersecting set is independent in $X^{\otimes n}$. \end{proof} %\nocite{*} \appendix \section{More details on examples from Section~\ref{sec:comparison}} \label{sec:appendix} %\paragraph{Example 1} \begin{exam} We start by describing the weighted hypergraph $(V,\mu)$. The set of vertices is $V = [3] \times [m]$. If $x,y,z$ are of different color, then $\mu([x,y,z]) = \frac{1}{6m^3}$. The skeleton is the complete tripartite graph $K_{m,m,m}$, and so its eigenvalues are simply the eigenvalues of $K_{m,m,m}$, normalized by the regularity $2m$. The eigenvalues of $K_{m,m,m}$ are readily seen to be $2m,0,-m$, and so $\lambda_0 = -\frac{1}{2}$. The link of any vertex is the complete bipartite graph $K_{m,m}$, whose eigenvalues are $m,-m$. After normalizing by the regularity $m$, we get $\lambda_1 = -1$. Altogether, the Link bound is $1-\frac{2}{3} \cdot \frac{1}{2} = \frac{2}{3}$. \end{exam} %\smallskip \begin{exam} %\paragraph{Example 2} The weighted hypergraph $(V,\mu)$ has the vertex set $V = [3] \times [m]$. If $x,y,z$ are distinct vertices of the same color, then $\mu([x,y,z]) = \frac{1}{6m(m-1)(2m-1)}$, and if they are distinct vertices of two different colors, then $\mu([x,y,z]) = \frac{1}{12m(m-1)(2m-1)}$. We compute $\mu([x,y]) = \frac{1}{3m(2m-1)}$ if $x \neq y$ have the same color and $\mu([x,y]) = \frac{1}{6m(2m-1)}$ if they have different color. Therefore the normalized adjacency operator is \[ T_X = \frac{1}{4m-2} \begin{pmatrix} 2(J-I) & J & J \\ J & 2(J-I) & J \\ J & J & 2(J-I) \end{pmatrix} = \frac{1}{4m-2} \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix} \otimes J - \frac{1}{2m-1} I. \] The eigenvalues of the small matrix are $4,1$, and so the eigenvalues of $T_X$ are $1,\frac{m-2}{4m-2},-\frac{1}{2m-1}$, hence $\lambda_0 = -\frac{1}{2m-1}$. The link of a vertex $x$, a graph over $3m-1$ vertices, has the following form. If $y,z$ have the same color, then $\mu_x([y,z]) = \frac{1}{2m-1}$. If $y,z$ have the the same color but not that of $x$, or if exactly one of them has the color of $x$, then $\mu_x([y,z]) = \frac{1}{4m-2}$. Therefore the normalized adjacency operator (with blocks of size $m-1,m,m$) is \[ T_{X_x} = \frac{1}{4m-4} \begin{pmatrix} 2(J-I) & J & J \\ 2J & 2(J-I) & 0 \\ 2J & 0 & 2(J-I) \end{pmatrix} = \frac{1}{4m-4} \begin{pmatrix} 2J & J & J \\ 2J & 2J & 0 \\ 2J & 0 & 2J \end{pmatrix} - \frac{1}{2m-2} I. \] The matrix on the right has rank~$2$. Its column space is spanned by the eigenvectors $(1,1,1)$ and $(0,1,-1)$, corresponding to the eigenvalues $4m-2$ and $2m$, respectively. Therefore the eigenvalues of $T_{X_v}$ are $1,\frac{1}{2},-\frac{1}{2m-2}$. In particular, $\lambda_1 = -\frac{1}{2m-2}$. Altogether, the Link bound is $1-\frac{2m-1}{2m} \cdot \frac{2m-2}{2m-1} = \frac{1}{m}$. \end{exam} %\smallskip \begin{exam} %\paragraph{Example 3} In this example, the weighted hypergraph $X = (V,\mu)$ has vertices $V = [2] \times [m]$. If $x,y,z$ are distinct vertices, not all of the same color, then $\mu([x,y,z]) = \frac{1}{6m^2(m-1)}$. We compute $\mu([x,y]) = \frac{1}{6m(m-1)}$ if $x,y$ are distinct vertices of the same color, and $\mu([x,y]) = \frac{1}{3m^2}$ if $x,y$ do not have the same color. Therefore the normalized adjacency operator is \[ T_X = \begin{pmatrix} \frac{1}{3m-3} (J-I) & \frac{2}{3m} J \\ \frac{2}{3m} J & \frac{1}{3m-3} (J-I) \end{pmatrix} = \begin{pmatrix} \frac{1}{3m-3} & \frac{2}{3m} \\ \frac{2}{3m} & \frac{1}{3m-3} \end{pmatrix} \otimes J - \frac{1}{3m-3} I. \] The small matrix has eigenvalues $\frac{3m-2}{3m(m-1)},\frac{-m+2}{3m(m-1)}$, and so the eigenvalues of $T_X$ are $1,-\frac{1}{3m-3},-\frac{1}{3}$. This shows that $\lambda_0 = -\frac{1}{3}$. The link of a vertex $x$ consists of a complete bipartite graph between $m-1$ and $m$ vertices together with a clique on the larger side. Therefore the normalized adjacency operator (with blocks of size $m-1,m$) is \[ T_{X_x} = \begin{pmatrix} 0 & \frac{1}{m} J \\ \frac{1}{2m-2} J & \frac{1}{2m-2} (J-I) \end{pmatrix} = \begin{pmatrix} \frac{1}{2m-2} I & \frac{1}{m} J \\ \frac{1}{2m-2} J & \frac{1}{2m-2} J \end{pmatrix} - \frac{1}{2m-2} I. \] The matrix on the right has the following eigenvectors: $(1,1)$ with eigenvalue $\frac{2m-1}{2m-2}$; $(1,-\frac{1}{2})$ with eigenvalue $-\frac{m-2}{2m-2}$; $(x,0)$ with eigenvalue $\frac{1}{2m-2}$ for any $x \perp 1$ (multiplicity $m-2$); and $(0,y)$ with eigenvalue $0$ for any $y \perp 1$ (multiplicity $m-1$). Therefore the eigenvalues of $T_{X_x}$ are $1,-\frac{1}{2},0,-\frac{1}{2m-2}$. In particular, $\lambda_1 = -\frac{1}{2}$. Altogether, the Link bound is $1-\frac{3}{4} \cdot \frac{2}{3} = \frac{1}{2}$. \end{exam} %\smallskip %\paragraph{Example 4} \begin{exam} Here the weighted hypergraph $X=(V,\mu)$ is simply the union of two disjoint 3-uniform $m$-cliques. That is, $V = [2] \times [m]$, and $\mu([x,y,z]) = \frac{1}{2m(m-1)(m-2)}$ whenever $x,y,z$ are distinct vertices having the same color. The skeleton is simply the union of two $m$-cliques, and so its eigenvalues are simply the eigenvalues of $K_m$, normalized by the regularity $m-1$. In particular, $\lambda_0 = -\frac{1}{m-1}$. Similarly, the link of a vertex is a single $(m-1)$-clique, and so $\lambda_1 = -\frac{1}{m-2}$. It follows that the Link bound is $1-\frac{m-1}{m} \cdot \frac{m-2}{m-1} = \frac{2}{m}$. \end{exam} \longthanks{The authors are grateful to Ehud Friedgut, Gil Kalai, Guy Kindler, and Dor Minzer for valuable discussions. We thank the reviewers for several helpful comments and suggestions.} \bibliographystyle{amsplain-ac} \bibliography{ALCO_Filmus_416} \end{document}