diff --git a/disctospec.tex b/disctospec.tex index 7e777310f5505a0283d5ce3e930326049fd3e56a..2f5f59d4a9aa3880f8e7769887a8df9f399ef3b6 100644 --- a/disctospec.tex +++ b/disctospec.tex @@ -78,6 +78,9 @@ \begin{document} +\title{Notes on hypergraph versions of Conlon--Zhao} +\maketitle + We attempt to prove that small discrepancy implies small spectral expansion for Cayley hypergraphs over certain types of abelian groups. In the case of regular graphs, this is known to hold for Cayley graphs over any group by a result of Conlan and Zhao, but does not hold for general graphs~\cite{Conlon:2016}. We start by giving definitions. Because these are just my personal notes, I will let the definition of Cayley hypergraphs be the exact same as that in my paper with Jop, except we let $\mathbf{g} = (0, g, g^2, \ldots, g^{t-1})$ and $q = \mathbf{1}$ for now. In particular, $K = \cay^{(t)}(\Gamma, q, S)$ is a $t$-uniform Cayley hypergraph with edges induced by the set $S \subseteq \Gamma$, and we let $A_K$ be the corresponding adjacency tensor. Given a Cayley hypergraph $K$, we say that a sub-hypergraph of $K$, $H = \cay^{(t)}(\Gamma, q, S')$ for some $S' \subseteq S$ has spectral expansion $\lambda$ with respect to $K$ if \[\lambda \geq \|A_H-A_K\|_{\ell_t, \ldots, \ell_t}.\] We say that $H$ has discrepancy $\epsilon$ with respect to $K$ if for all $T_1, \ldots, T_t \subseteq \Gamma$, \[|A_H(1_{T_1}, \ldots, 1_{T_t})-A_K(1_{T_1}, \ldots, 1_{T_t})| \leq \epsilon |\Gamma|.\] We can lower bound discrepancy in terms of the $\ell_{\infty}, \ldots, \ell_{\infty}$-norm of $A_H-A_K$ as stated in the following Lemma (the upper bound is trivial). The proof follows almost exactly that of the same fact for matrices in Lemma 2.1 in~\cite{Conlon:2016}.