\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram} \OneNumberAllTheorems \usepackage{mathtools} \newcommand{\mo}{{-1}} \newcommand{\calM}{\ensuremath{\mathcal{M}}} \newcommand{\calS}{\ensuremath{\mathcal{S}}} \newcommand{\frakh}{\ensuremath{\mathfrak{h}}} %%%%%%%%% 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{Arindam} \lastname{Biswas}} \address{Department of Mathematics\\ Technion - Israel Institute of Technology\\ Haifa 32000, Israel} \email{biswas@campus.technion.ac.il; arin.math@gmail.com} %%%2 \author{\firstname{Jyoti Prakash} \lastname{Saha}} \address{Department of Mathematics\\ Indian Institute of Science Education and Research Bhopal\\ Bhopal Bypass Road, Bhauri, Bhopal 462066, Madhya Pradesh, India} \email{jpsaha@iiserb.ac.in} %%%%% Sujet \keywords{Expander graphs, Cheeger inequality, Spectra of Cayley sum graphs.} \subjclass{05C25, 05C50, 05C75} %%%%% Gestion \DOI{10.5802/alco.166} \datereceived{2020-06-05} \daterevised{2020-12-20} \dateaccepted{2020-12-20} %%%%% Titre et résumé \title{A Cheeger type inequality in finite Cayley sum graphs} \begin{abstract} Let $G$ be a finite group with $\vert G\vert \geqslant 4$ and $S$ be a subset of $G$ with $\vert S\vert = d$ such that the Cayley sum graph $C_{\Sigma}(G,S)$ is undirected and connected. We show that the non-trivial spectrum of the normalised adjacency operator of $C_{\Sigma}(G,S)$ is controlled by its Cheeger constant and its degree. We establish an explicit lower bound for the non-trivial spectrum of these graphs, namely, the non-trivial eigenvalues of the normalised adjacency operator lies in the interval $\big(-1+\frac{h_\Sigma(G)^{4}}{\eta}, 1-\frac{h_\Sigma(G)^{2}}{2d^{2}}\big]$, where $h_\Sigma(G)$ denotes the vertex Cheeger constant of the $d$-regular graph $C_{\Sigma}(G,S)$ and $\eta = 2^{9}d^{8}$. Further, we improve upon a recently obtained bound on the non-trivial spectrum of the normalised adjacency operator of the Cayley graph of finite groups. \end{abstract} \begin{document} %% Abstracts must be placed before \maketitle \maketitle \section{Introduction} Let $G$ be a finite group, and $S$ be a subset of $G$ with $\vert S\vert = d$. The Cayley sum graph $C_\Sigma(G, S)$ is the graph having $G$ as its set of vertices and for $g, h\in G$, the vertex $h$ is adjacent to $g$ if $h = g^\mo s$ for some element $s\in S$. These are classical combinatorial objects. We also recall that the Cayley graph of $G$ (sometimes, called the Cayley difference graph), denoted by $C(G,S)$, is the graph having $G$ as its set of vertices and a vertex $h$ is adjacent to a vertex $g$ if $h = gs$ for some element $s\in S$. The structures of $C(G,S)$ and $C_{\Sigma}(G,S)$ can be very different. This can be seen by considering the Cayley graph $C(G,S)$ and the Cayley sum graph $C_{\Sigma}(G,S)$ of $G = \mathbb{Z}/n\mathbb{Z}$ ($n\geqslant 5$) with respect to the set $S = \lbrace \pm 1\rbrace$. The former is always a cycle graph while the latter need not be so (for instance, the latter is a cycle graph when $n$ is even and is a path with loops at the endpoints whenever $n$ is odd). Cayley graphs have been extensively studied over the ages. However, despite being classical combinatorial objects, the literature on Cayley sum graphs is not extensive. Very few things are known about Cayley sum graphs and most of them are quite recent works. They include those of Chung~\cite{Chung89JAMS}, Green~\cite{GreenCountingSetsWithSmallSubsetsClique, GreenChromatic}, Green--Morris~\cite{GreenMorrisCountingSetsWithSmallSubsets}, Grynkiewicz--Lev--Serra~\cite{GrynkiewiczLevSerraConnCaylSum}, DeVos--Goddyn--Mohar--{\v S}{\'a}mal~\cite{DeVosGoddynMoharSamalCayleySumFullerene}, Mrazovi{\'c}~\cite{MrazovicExtractorsInPaleyGraphs}, Konyagin--Shkredov~\cite{KonyaginShkredovSubgraphRandomCayleySumGra}, Ma--Feng--Wang~\cite{MaFengWangSubGrpPCInCayGra}. Indeed, even the question of vertex connectivity of abelian Cayley sum graphs was treated very recently in 2009 by Grynkiewicz--Lev--Serra~\cite{GrynkiewiczLevSerraConnCaylSum}, whereas vertex connectivity of abelian Cayley graphs is relatively easy. One reason for this fact is that unlike in the case of Cayley graphs, Cayley sum graphs may have less symmetry in them. Even less is known about the spectra of Cayley sum graphs. In fact, among the previous works, only that of Chung~\cite{Chung89JAMS} and that of DeVos et. al.~\cite{DeVosGoddynMoharSamalCayleySumFullerene} deal with eigenvalues of some Cayley sum graphs, whereas the computation of distribution of eigenvalues of graphs is a fundamental topic of interest in graph theory. It is not yet known whether random Cayley sum graphs are expanders. Much remains to be discovered about Cayley sum graphs and it is a topic of current research. In this article, our main motivation is to establish a lower bound on the distribution of non-trivial eigenvalues of Cayley sum graphs. In the following, the graphs and the multi-graphs considered are all undirected. The multi-graphs may possibly admit multiple edges. Moreover, the graphs and the multi-graphs considered may admit loops. Given a finite $d$-regular multi-graph $\mathbb{G} = (V,E)$ where $V$ denotes the set of vertices and $E\subseteq \binom V 2$ denotes the multi-set of edges, we have the normalised adjacency matrix $T$ of size $\vert V\vert\times \vert V\vert$, which is equal to $\frac 1d A$, where $A$ denote the adjacency matrix of $\mathbb G$ of size $\vert V\vert\times \vert V\vert$, whose $(i,j)$-th entry is equal to the number of edges joining the $i$-th vertex and the $j$-th vertex of $V$. Note that the eigenvalues of $T$ lie in the interval $[-1,1]$. The normalised Laplacian matrix of $\mathbb{G}$ is defined by \[ L\coloneqq I_{\vert V\vert} - T \] where $I_{\vert V\vert}$ denotes the identity matrix of size $\vert V\vert\times \vert V\vert$. The eigenvalues of $L$ lie in the interval $[0,2]$. Denote the eigenvalues of $T$ and the eigenvalues of $L$ by $\lbrace t_{i} : i= 1, \ldots, \vert V\vert\rbrace $ and $\lbrace \lambda_{i} : i= 1, \ldots, \vert V\vert\rbrace $ respectively, such that $\lambda_{i} = 1 - t_{i}$ and \begin{align*} -1 \leqslant t_{n} \leqslant t_{n-1} \leqslant \cdots \leqslant t_{2}\leqslant t_{1} & = 1,\\ 0 = \lambda_{1} \leqslant \lambda_{2} \leqslant \cdots \leqslant \lambda_{n-1}\leqslant \lambda_{n} & \leqslant 2. \end{align*} The multi-graph $\mathbb{G}$ is connected if and only if $\lambda_{2} > 0$ (equivalently, $t_2<1$). Moreover, if $\mathbb G$ is connected, then it is bipartite if and only if $\lambda_{n} = 2$ (equivalently, $t_{n} = -1$). For a subset $V_{1}\subseteq V$, we denote the neighbourhood of $V_{1}$ by $N(V_{1})$ where, \[ N(V_{1}) \coloneqq \lbrace v\in V : \{v, v_{1}\}\in E \text{ for some } v_{1}\in V_{1}\rbrace. \] The boundary of $V_{1}$ is defined as $ \delta(V_{1}) \coloneqq N(V_{1})\backslash V_{1}$. \begin{remark} In the case of a Cayley graph $C(G,S)$, the neighbourhood $N(V_1)$ of a subset $V_1$ of $G$ is equal to $V_{1}S$ and its boundary $\delta(V_1)$ is equal to $V_{1}S\setminus S $, while for a Cayley sum graph $C_{\Sigma}(G,S)$, the neighbourhood $N(V_1)$ of a subset $V_1$ of $G$ is equal to $V_{1}^{-1}S$, and its boundary $\delta(V_1)$ is equal to $V_{1}^{-1}S\setminus S$. \end{remark} \begin{definition}[Vertex Cheeger constant] The vertex Cheeger constant of the multi-graph $\mathbb{G} = (V,E)$ with $\vert V\vert \geqslant 2$, denoted by $h(\mathbb{G})$, is defined as \[ h(\mathbb{G}) \coloneqq \inf \left\lbrace \frac{\vert \delta(V_{1})\vert }{\vert V_{1}\vert } : \emptyset \neq V_{1}\subseteq V, \vert V_{1}\vert \leqslant \frac{\vert V\vert}{2} \right\rbrace. \] \end{definition} By considering a subset of $V$ having size around half of the size of $V$, it follows that the vertex Cheeger constant of $(V, E)$ cannot be much bigger than one. Indeed, if $V$ contains an even number of elements, then taking a subset $V_1$ of $V$ of size equal to $\vert V\vert/2$, one observes that the ratio of the size of its boundary $\delta(V_1)$ to the size of $V_1$ is bounded from the above by $1$. Moreover, if $V$ contains an odd number of elements, then taking a subset $V_2$ of $V$ of size equal to $(\vert V\vert-1)/2$, one observes that the ratio of the size of its boundary $\delta(V_2)$ to its size $\vert V_2\vert $ is bounded from the above by \[ \frac{\vert V\setminus V_2\vert }{\vert V_2\vert } = \frac{\vert V\vert + 1}{\vert V\vert -1} = 1 + \frac 2{\vert V\vert-1}. \] In particular, the vertex Cheeger constant of $\mathbb G$ satisfies $h(\mathbb G) \leqslant 2$. Next, we recall the notion of an expander graph as stated by Alon in~\cite{AlonEigenvalueExpand}. \begin{definition}[$(n,d,\varepsilon)$-expander]\label{vexp} Let $\varepsilon>0$. An $(n,d,\varepsilon)$-expander is a graph $\mathbb G = (V,E)$ on $\vert V\vert =n$ vertices, having maximal degree $d$, such that for every set $\emptyset \neq V_{1}\subseteq V$ satisfying $\vert V_{1}\vert \leqslant \frac{n}{2}$, $\vert \delta(V_{1})\vert \geqslant \varepsilon\vert V_{1}\vert $ holds (equivalently, $h(\mathbb{G})\geqslant \varepsilon).$ \end{definition} It was shown qualitatively by Breuillard, Green, Guralnick, and Tao that the eigenvalues of the normalised Laplacian matrix of non-bipartite finite Cayley graphs are bounded away from $2$~\cite[Appendix E]{BGGTExpansionSimpleLie}. Based on their arguments, the first author recently established an explicit upper bound~\cite[Theorem 1.4]{BiswasCheegerCayley}. In this article, we show that a similar phenomenon occurs for the spectrum of the Cayley sum graph $C_{\Sigma}(G,S)$ by suitably adapting the strategy outlined in~\cite[Appendix E]{BGGTExpansionSimpleLie}, along with the introduction of some new refinements. For an outline of the proof, we refer to \S~\ref{Outline}. Henceforth, we assume that $\vert G\vert \geqslant 4$, to avoid trivial cases. \begin{theorem}\label{mainthm} Let $h_\Sigma(G)$ denote the vertex Cheeger constant of the connected Cayley sum graph $C_\Sigma(G, S)$. Then if $C_{\Sigma}(G,S)$ is non-bipartite, we have \[ \lambda_{n}< 2 - \frac{h_\Sigma(G)^{4}}{2^{9}d^{8}}\,\,\, (\text{equivalently, } -1 + \frac{h_\Sigma(G)^{4}}{2^{9} d^{8}} < t_{n}), \] where $\lambda_{n}$ (respectively, $t_{n}$) is the largest (respectively, the smallest) eigenvalue of the normalised Laplacian matrix (respectively, the normalised adjacency matrix) of $C_\Sigma(G, S)$. \end{theorem} \begin{remark} Note that when $C_{\Sigma}(G,S)$ is bipartite, the spectrum of its adjacency matrix is symmetric about the origin. In this case, the lower spectrum is determined by the upper spectrum, for instance, $t_{n}= -t_{1} = -1$ and $t_{n-1} = -t_{2} \geqslant -1 + \frac {h_\Sigma (G)^2}{2d^2}$, which follows from the discrete Cheeger--Buser inequality. Theorem~\ref{mainthm} focuses on the non-bipartite Cayley sum graphs and shows that the smallest eigenvalue of the normalised adjacency matrix admits a lower bound depending only on the vertex Cheeger constant and the degree. This result is deduced after the proof of Theorem~\ref{thmPrincipal}. \end{remark} One has the following corollary of Theorem~\ref{mainthm}. \begin{corollary} \label{Corollary} Let $d\geqslant 2$ be an integer. Let $\lbrace C_{\Sigma}(G_{k}, S_{k})\rbrace_{k\geqslant 1}$ be a sequence of non-bipartite, finite Cayley sum graphs with $\vert G_{k}\vert \rightarrow \infty, \vert S_{k}\vert = d $. Then, if there exists an uniform $\varepsilon >0$, such that each graph $C_{\Sigma}(G_{k}, S_{k})$ in the sequence is an $(\vert G_{k}\vert , d, \varepsilon)$-expander, we have all the eigenvalues of the normalised adjacency matrix of each graph are uniformly bounded away from $-1$. \end{corollary} As a by-product of our proof, we improve the bound established for Cayley graphs in~\cite[Theorem 1.4]{BiswasCheegerCayley}. See Theorem~\ref{Bis19}. \subsection{Outline of the proof}\label{Outline} We outline the proof of Theorem~\ref{mainthm}. To prove this result, we assume on the contrary that the normalised adjacency matrix $T$ of the Cayley sum graph admits an eigenvalue close to $-1$ (see Theorem~\ref{thmPrincipal}). This implies that $T^2$ has an eigenvalue close to $1$. We define a multi-graph $\calM$ such that its normalised adjacency matrix is equal to $T^2$ (see the proof of Proposition~\ref{Prop:AExists}). Then the discrete Cheeger--Buser inequality yields an upper bound on the edge-Cheeger constant of $\calM$, which in turn implies an upper bound on the vertex Cheeger constant of $\calM$. This yields a subset $A$ of $G$ of size $\leqslant \frac{\vert G\vert }{2}$ having a convenient upper bound on $\vert S^\mo AS\setminus A\vert /\vert A\vert $. Using combinatorial arguments, we obtain upper bounds on the sizes of several subsets defined using $A$ (see Proposition~\ref{Prop:AExists}). As a consequence, for a given element $g\in G$, we establish a dichotomy result on the size of $A\cap Ag$ (see Proposition~\ref{Prop:Dichotomy}), which states that the size $A\cap Ag$ is either very small or quite large as compared to the size of $A$. This allows us to adapt an argument due to Fre\u{\i}man~\cite{FreimanGroupsInverseProb} in our set-up to construct a subgroup $H_+$ of $G$ (see Theorem~\ref{thmPrincipal}). From the bound on the smallest eigenvalue of $T$, it follows that the subgroup $H_+$ has index two in $G$. In Proposition~\ref{Prop:Dichotomy}, we also establish a similar dichotomy result on the size of $A\cap A^\mo g$. Using the strategy of Fre\u{\i}man once again, we define a subset $H_-$ of $G$, which avoids $S$ and is equal to a coset of $H_+$ in $G$, \ie to $H_+$ or $G\setminus H_+$. To conclude the result, we consider two cases. First, if $H_-$ is equal to $H_+$, then the index two subgroup $H_+$ avoids $S$, which contradicts the hypothesis that $C_\Sigma(G, S)$ is non-bipartite (by Lemma~\ref{Lemma:Bipartite}). Next, if $H_-$ is equal to $G\setminus H_+$, then the index two subgroup $H_+$ contains $S$, which contradicts the hypothesis that $C_\Sigma(G, S)$ is connected. % \subsection{Acknowledgements} \section{Proof of the main result} The degree of a vertex of a multi-graph is the number of half-edges adjacent to it (in the absence of loops). The presence of a loop at a vertex increases its degree by one. A multi-graph is said to be $r$-regular if each vertex has degree $r$. Apart from the vertex expansion as in Definition~\ref{vexp}, we also have the notion of edge expansion. \begin{definition}[Edge expansion] Let $\mathbb{G} = (V,E)$ be a $d$-regular multi-graph with vertex set $V$ and edge multi-set $E$. For a subset $\emptyset \neq V_{1}\subseteq V$, let $E(V_{1},V\backslash V_{1})$ be the edge boundary of $V_{1}$, defined as \[ E(V_{1},V\backslash V_{1}) \coloneqq \lbrace (v_{1},v_2)\in E: v_{1}\in V, v_2\in V\backslash V_{1} \rbrace . \] Then the edge expansion ratio $\phi(V_{1})$ of $V_1$ is defined as \[ \phi(V_{1}) \coloneqq \frac{\vert E(V_{1},V\backslash V_{1})\vert }{d\vert V_{1}\vert }. \] \end{definition} \begin{definition}[Edge-Cheeger constant] For a multi-graph $\mathbb G = (V, E)$, its edge-Cheeger constant $\mathfrak{h}(\mathbb{G})$ is defined by \[ \mathfrak{h}(\mathbb{G})\coloneqq \inf_{\emptyset \neq V_{1}\subseteq V, \vert V_{1}\vert \leqslant\vert V\vert/2} \phi(V_{1}). \] \end{definition} In a $d$-regular multi-graph, the two Cheeger constants are related by the following. \begin{lemma} \label{Lemma:VertexEdgeCons} Let $\mathbb{G} = (V,E)$ be a $d$-regular multi-graph. Then \[ \frac{h(\mathbb{G})}{d} \leqslant \mathfrak{h}(\mathbb{G}) \leqslant h(\mathbb{G}) \] holds. \end{lemma} \begin{proof} Let $\emptyset \neq V_{1}\subseteq V$ and we consider the map \[ \psi:E(V_{1},V\backslash V_{1}) \rightarrow \delta(V_{1}) \text{ given by }(v_{1},v_2)\mapsto v_{2}. \] This map is surjective, hence we have the left hand side and at the worst case $d$ to $1$ wherein we get the right hand side. \end{proof} The discrete Cheeger--Buser inequality relates the (edge) Cheeger constant with the second smallest eigenvalue of the Laplacian matrix. It is the version for graphs of the corresponding inequalities for the Laplace--Beltrami operator on compact Riemannian manifolds. It was first proven by Cheeger~\cite{CheegerLowerBddSmallest} (the lower bound) and by Buser~\cite{BuserNoteIsoperimetric} (the upper bound). The discrete version was shown by Alon and Milman~\cite{AlonMilmanIsoperiIneqSupConcen} (Proposition~\ref{Prop:chin}). \goodbreak \begin{proposition}[Discrete Cheeger--Buser inequality]\label{Prop:chin} Let $\mathbb{G} = (V,E)$ be a finite $d$-regular multi-graph. Let $\lambda_{2}$ denote the second smallest eigenvalue of its normalised Laplacian matrix and $\mathfrak{h}(\mathbb{G})$ be the edge-Cheeger constant. Then \[ \frac{\mathfrak{h}(\mathbb{G})^{2}}{2} \leqslant \lambda_{2} \leqslant 2\mathfrak{h}(\mathbb{G}). \] \end{proposition} \begin{proof} See~\cite[Proposition 4.2.4, 4.2.5]{LubotzkyDiscreteGroups} or~\cite[Section 3]{ChungLaplacianOfGraph}. \end{proof} \begin{lemma} \label{Lemma:Bipartite} If $G$ contains a subgroup of index two which does not intersect $S$, then the Cayley sum graph $C_\Sigma(G, S)$ is bipartite. \end{lemma} \begin{proof} Suppose $G$ contains a subgroup $H$ of index two which does not intersect $S$. Then $H^\mo S$ is equal to $G\setminus H$ and hence $H$ is an independent set. Moreover, $(G\setminus H)^\mo S$ is equal to $H$. Thus, $G\setminus H$ is also an independent set. So, the Cayley sum graph $C_\Sigma(G, S)$ is bipartite. \end{proof} \begin{lemma} \label{undirected-Cayley-sum} The Cayley sum graph $C_\Sigma(G, S)$ is undirected if and only if $S$ is closed under conjugation. \end{lemma} \begin{proof} The graph $C_\Sigma(G, S)$ is undirected if and only if for any $g\in G$ and $s\in S$, $(g^\mo s) ^\mo t = g$ holds for some $t\in S$, which is equivalent to $S$ being closed under conjugation. \end{proof} \begin{proposition} \label{Prop:nuBdd} Suppose $(V, E)$ is an $(n, d, \varepsilon)$-expander with $\varepsilon >0$ and $\vert V\vert\geqslant 4$. Let $A$ be a subset of $V$ with $\vert A\vert \geqslant \frac 12 \vert V\vert$. Then, the inequalities \begin{equation} \label{Eqn:epsilonD1bdd} \varepsilon \leq d-1, \end{equation} \begin{equation} \label{Eqn:nuBdd} \vert \delta(A)\vert \geqslant \frac \varepsilon d \vert V \setminus A\vert \end{equation} hold. \end{proposition} \begin{proof} If $u, v$ are two adjacent vertices in $V$, then it follows that $\varepsilon \vert \{u, v\}\vert \leqslant \vert \delta (\{u, v\}) \vert \leqslant 2 (d-1)$ (since the size of $\{u, v\}$ is $\leqslant \frac 12 \vert V\vert$), which shows that $\varepsilon \leqslant d-1$. Let $B$ denote the subset $V\setminus (A \cup \delta(A))$ of $V$. Suppose $B$ is nonempty. Since $\vert A\vert \geqslant \frac 12 \vert V\vert$, it follows that $\vert B\vert \leqslant \frac 12 \vert V\vert$. This shows that $\varepsilon \vert B\vert \leqslant \vert \delta (B)\vert $. Note that $V$ is equal to the union of the pairwise disjoint subsets $A, \delta (A), B$. Since no element of $A$ is adjacent to an element of $B$, it follows that $\delta (B)$ is contained in $\delta (A)$. This shows that $\varepsilon \vert B\vert \leqslant \vert \delta (B)\vert \leqslant \vert \delta (A)\vert $. Suppose~\eqref{Eqn:nuBdd} does not hold, \ie the inequality $ d \vert \delta (A)\vert < \varepsilon (\vert B\vert + \vert \delta (A)\vert )$ holds. This yields \[ ( d - \varepsilon) \varepsilon \vert B\vert \leqslant (d-\varepsilon) \vert \delta(A)\vert < \varepsilon \vert B\vert, \] which implies that $\varepsilon > d -1$, which is impossible. Hence, the set $B$ is empty. Then~\eqref{Eqn:nuBdd} follows from the inequality $\varepsilon \leqslant d$, which holds by~\eqref{Eqn:epsilonD1bdd}. \end{proof} \begin{proposition} \label{Prop:AExists} Let $C_\Sigma(G, S)$ be a non-bipartite $(n,d,\varepsilon)$-vertex expander for some $\varepsilon>0$. Suppose the normalised adjacency matrix of $C_\Sigma(G, S)$ has an eigenvalue in the interval $(-1, -1+\zeta]$ for some $\zeta$ satisfying $0<\zeta \leqslant \frac{\varepsilon^2}{4d^4}$. Then for some subset $A$ of~$G$, the following conditions hold with $\beta = d^2 \sqrt{2\zeta (2-\zeta)}$. \begin{enumerate} \item\label{prop2.8_1} $\frac 1{2 + \beta + \frac{d\beta}{\varepsilon}} \vert G\vert \leqslant \vert A\vert \leqslant \frac 12 \vert G\vert $. \item\label{prop2.8_2} $\vert Ag\cap (Ag)^\mo S\vert \leqslant \frac \beta\varepsilon \vert A\vert $ for all $g\in G$. \item\label{prop2.8_3} $\vert (Ag)^\mo s \Delta (Ag)^c \vert \leqslant \frac \beta \varepsilon (\varepsilon + d+ 2) \vert A\vert $ for all $s\in S, g\in G$. \item\label{prop2.8_4} $\vert A^\mo g\cap (A^\mo g)^\mo S\vert \leqslant \frac \beta\varepsilon \vert A\vert $ for all $g\in G$. \item\label{prop2.8_5} $\vert (A^\mo g)^\mo s \Delta (A^\mo g)^c \vert \leqslant \frac \beta \varepsilon (\varepsilon + d+ 2) \vert A\vert $ for all $s\in S, g\in G$. \end{enumerate} \end{proposition} \begin{proof} Since $\vert G\vert \geqslant 4$, it follows from Proposition~\ref{Prop:nuBdd} that \begin{equation} \label{Eqn:EpsilonBound} \varepsilon \leqslant d-1. \end{equation} This implies that $\zeta <1$. Let $T$ denote the normalised adjacency matrix of the Cayley sum graph $C_\Sigma(G, S)$. Since $T$ has an eigenvalue in $(-1, -1+\zeta]$ and $\zeta <1$, it follows that $T^2$ has an eigenvalue $\nu$ in $[(1-\zeta)^2, 1)$. Let $\calM$ denote the weighted graph having $G$ as its set of vertices and having $T^2$ as its normalised adjacency matrix. Thus the second largest eigenvalue of the normalised adjacency matrix of $\calM$ is $\geqslant \nu\geqslant (1-\zeta)^2 = 1 - \zeta(2-\zeta)$. Hence the second smallest eigenvalue of the normalised Laplacian matrix of $\calM$ is $\leqslant \zeta(2-\zeta)$. By the discrete Cheeger--Buser inequality (Proposition~\ref{Prop:chin}), it follows that the edge-Cheeger constant of $\calM$ satisfies \[ \frac 12 \frakh(\calM)^2 \leqslant \zeta(2-\zeta), \] which yields \[ \frakh(\calM)\leqslant \sqrt{2\zeta(2-\zeta)}. \] Consequently, by Lemma~\ref{Lemma:VertexEdgeCons}, the vertex Cheeger constant of $\calM$ satisfies \[ h(\calM) \leqslant d^2 \frakh(\calM) \leqslant d^2\sqrt{2\zeta(2-\zeta)}. \] This implies that for some non-empty subset $A$ of $G$ with $\vert A\vert \leqslant \frac 12 \vert G\vert $, \begin{equation} \label{Eqn:SetA} \frac{\vert S^\mo AS\setminus A\vert }{\vert A\vert } \leqslant d^2\sqrt{2\zeta(2-\zeta)} \end{equation} holds. We claim that \begin{equation} \label{Eqn:LowerBdd} \vert A\cup A^\mo S \vert \geqslant \frac 12 \vert G\vert . \end{equation} Otherwise, the inequality $\vert A\cup A^\mo S \vert \leqslant \frac 12 \vert G\vert $ would imply \[ \varepsilon\vert A \cup A^\mo S\vert \leqslant \vert ((A \cup A^\mo S)^\mo S) \setminus (A \cup A^\mo S)\vert , \] which combined with the inequalities \[ \varepsilon \vert A\vert \leqslant \varepsilon\vert A \cup A^\mo S \vert \] and \begin{align*} \vert ((A \cup A^\mo S)^\mo S) \setminus (A \cup A^\mo S)\vert & = \vert (A^\mo S \cup S^\mo AS) \setminus (A \cup A^\mo S)\vert \\ & \leqslant \vert S^\mo AS \setminus A\vert \\ & \leqslant \vert A\vert d^2\sqrt{2\zeta(2-\zeta)} \end{align*} implies \[ \varepsilon \leqslant d^2\sqrt{2\zeta(2-\zeta)} < d^2 \sqrt{4\zeta}. \] This contradicts the assumption $\zeta \leqslant \frac{\varepsilon^2}{4d^4}$. Hence~\eqref{Eqn:LowerBdd} holds. Applying Proposition~\ref{Prop:nuBdd} to the Cayley sum graph $C_\Sigma(G, S)$, we obtain \[ \frac \varepsilon d \vert G \setminus (A\cup A^\mo S)\vert \leqslant \vert ((A\cup A^\mo S)^\mo S) \setminus (A\cup A^\mo S)\vert \leqslant \vert A\vert d^2\sqrt{2\zeta(2-\zeta)} = \vert A\vert \beta.\vadjust{\goodbreak } \] So \[ \frac {d\beta}\varepsilon \vert A\vert \geqslant \vert G \setminus (A\cup A^\mo S)\vert = \vert G\vert - \vert A\cup A^\mo S\vert , \] which implies \begin{align*} \vert G\vert & \leqslant \frac {d\beta}\varepsilon \vert A\vert + \vert A\cup A^\mo S\vert \\ &\leqslant \frac {d\beta}\varepsilon \vert A\vert + \vert A\vert + \vert A^\mo S\vert \\ & = \frac {d\beta}\varepsilon \vert A\vert + \vert A\vert + \vert S^\mo A\vert \\ &\leqslant \frac {d\beta}\varepsilon \vert A\vert + \vert A\vert + \vert S^\mo A S\vert \\ &\leqslant \frac {d\beta}\varepsilon \vert A\vert + \vert A\vert + \vert A\vert + \vert S^\mo A S\setminus A \vert \\ &\leqslant \frac {d\beta}\varepsilon \vert A\vert + 2\vert A\vert + \beta |A \vert , \end{align*} where the last inequality follows from~\eqref{Eqn:SetA}. This proves the inequalities as in statement~\eqref{prop2.8_1}. To obtain the inequality in statement \eqref{prop2.8_2}, note that $\vert A\vert \leqslant \frac 12 \vert G\vert $ implies that $\vert Ag\cap (Ag)^\mo S\vert \leqslant \frac 12 \vert G\vert $. Since $C_\Sigma(G, S)$ is an $\varepsilon$-vertex expander, it follows that \begin{align*} \varepsilon \vert Ag\cap (Ag)^\mo S\vert & \leqslant \vert ((Ag\cap (Ag)^\mo S)^\mo S) \setminus (Ag\cap (Ag)^\mo S)\vert \\ & = \vert (((Ag)^\mo \cap S^\mo Ag) S) \setminus (Ag\cap (Ag)^\mo S)\vert \\ & \leqslant \vert ((Ag)^\mo S \cap S^\mo Ag S) \setminus (Ag\cap (Ag)^\mo S)\vert \\ & \leqslant \vert S^\mo Ag S\setminus Ag\vert \\ & = \vert S^\mo Ag Sg^\mo \setminus A\vert \\ & = \vert S^\mo AS \setminus A\vert \\ & \leqslant \beta \vert A\vert . \end{align*} This establishes the inequality in statement~\eqref{prop2.8_2}. To obtain the inequality in statement~\eqref{prop2.8_3}, it suffices to observe that \begin{align*} \vert (Ag)^\mo s\Delta (Ag)^c\vert & = \vert (Ag)^\mo s\vert + \vert (Ag)^c\vert - 2 \vert (Ag)^\mo s \cap (Ag)^c\vert \\ & = \vert Ag\vert + \vert G\vert - \vert Ag\vert - 2(\vert (Ag)^\mo s\vert - \vert (Ag)^\mo s \cap Ag\vert )\\ & = \vert G\vert - 2\vert (Ag)^\mo s\vert + 2\vert (Ag)^\mo s\cap Ag\vert \\ & = \vert G\vert - 2\vert A\vert + 2\vert Ag \cap (Ag)^\mo s\vert \\ & \leqslant \vert G\vert - 2\vert A\vert + 2\vert Ag \cap (Ag)^\mo S\vert \\ & \leqslant \left(2 + \beta + \frac {d\beta}\varepsilon\right) \vert A\vert - 2\vert A\vert + \frac {2\beta}\varepsilon \vert A\vert \\ & = \beta \left( 1 + \frac d\varepsilon + \frac 2 \varepsilon\right) \vert A\vert \end{align*} holds, where the final inequality is obtained by applying statements~\eqref{prop2.8_1} and~\eqref{prop2.8_2}. To obtain the inequality in statement \eqref{prop2.8_4}, note that $\vert A^\mo \vert \leqslant \frac 12 \vert G\vert $ implies that $\vert A^\mo g\cap (A^\mo g)^\mo S\vert \leqslant \frac 12 \vert G\vert $. Since $C_\Sigma(G, S)$ is an $\varepsilon$-vertex expander, it follows that \begin{align*} \varepsilon \vert A^\mo g\cap ((A^\mo g)^\mo S)\vert & \leqslant \vert ((A^\mo g\cap ((A^\mo g)^\mo S))^\mo S) \setminus (A^\mo g\cap ((A^\mo g)^\mo S))\vert \\ & = \vert (((A^\mo g)^\mo S \cap (S^\mo A^\mo g S)) \setminus (A^\mo g\cap ((A^\mo g)^\mo S))\vert \\ & \leqslant \vert (((A^\mo g)^\mo S) \cap (S^\mo A^\mo g S)) \setminus (A^\mo g\cap ((A^\mo g)^\mo S))\vert \\ & \leqslant \vert S^\mo A^\mo g S\setminus A^\mo g\vert \\ & = \vert S^\mo A^\mo g Sg^\mo \setminus A^\mo \vert \\ & = \vert S^\mo A^\mo S \setminus A^\mo \vert \\ & = \vert S^\mo A S \setminus A \vert \\ & \leqslant \beta \vert A \vert . \end{align*} This establishes the inequality in statement~\eqref{prop2.8_4}. To complete the proof, it suffices to observe that \begin{align*} \vert (A^\mo g)^\mo s\Delta (A^\mo g)^c\vert & \Mk =\Mk \vert (A^\mo g)^\mo s\vert + \vert (A^\mo g)^c\vert - 2 \vert (A^\mo g)^\mo s \cap (A^\mo g)^c\vert \\ & \Mk =\Mk \vert A^\mo g\vert \Mk +\Mk \vert G\vert \Mk - \Mk \vert A^\mo g\vert \Mk - \Mk 2(\vert (A^\mo g)^\mo s\vert \Mk - \Mk \vert (A^\mo g)^\mo s \Mk \cap \Mk A^\mo g\vert )\\ & \Mk =\Mk \vert G\vert - 2\vert (A^\mo g)^\mo s\vert + 2\vert (A^\mo g)^\mo s\cap A^\mo g\vert \\ & \Mk =\Mk \vert G\vert - 2\vert A \vert + 2\vert A^\mo g \cap (A^\mo g)^\mo s\vert \\ & \Mk \leqslant\Mk \vert G\vert - 2\vert A\vert + 2\vert A^\mo g \cap ((A^\mo g)^\mo S)\vert \\ & \Mk \leqslant\Mk \left(2 + \beta + \frac {d\beta}\varepsilon\right) \vert A\vert - 2\vert A\vert + \frac {2\beta}\varepsilon \vert A\vert \\ & \Mk =\Mk \beta \left( 1 + \frac d\varepsilon + \frac 2 \varepsilon\right) \vert A\vert \end{align*} holds, where the final inequality is obtained by applying statement~\eqref{prop2.8_1} and~\eqref{prop2.8_4}. \end{proof} \begin{proposition} \label{Prop:Dichotomy} Under the notations and assumptions as in Proposition~\ref{Prop:AExists}, and the additional hypothesis \[ \beta < \frac{\varepsilon^2}{4 d(d+1)}, \] it follows that for a given element $g\in G$, \begin{enumerate} \item\label{prop2.9_1} exactly one of the inequalities \[ \vert A \cap Ag\vert \leqslant \frac{d \beta}{\varepsilon^2} (\varepsilon + d + 2)\vert A\vert , \quad \vert A \cap Ag\vert \geqslant \left( 1 - \frac {d \beta}{ \varepsilon^2} ( \varepsilon + d + 2) \right) \vert A\vert \] holds, and \item\label{prop2.9_2} exactly one of the inequalities \[ \vert A \cap A^\mo g\vert \leqslant \frac{d \beta}{\varepsilon^2} (\varepsilon + d + 2)\vert A\vert , \quad \vert A \cap A^\mo g\vert \geqslant \left( 1 - \frac {d \beta}{ \varepsilon^2} ( \varepsilon + d + 2) \right) \vert A\vert \] holds. \end{enumerate} \end{proposition} \begin{proof} Note that the inequalities \[ \frac {2d\beta} { \varepsilon^2} ( \varepsilon + d + 2) \leqslant \frac {2d\beta} { \varepsilon^2}( d + d + 2) = \frac {4d\beta} { \varepsilon^2} ( d + 1) <1 \] imply that \[ \frac{d \beta}{\varepsilon^2} (\varepsilon + d + 2) < 1 - \frac {d \beta}{ \varepsilon^2} ( \varepsilon + d + 2). \] Hence it suffices to show that for a given element $g\in G$, one of the inequalities \[ \vert A \cap Ag\vert \leqslant \frac{d \beta}{\varepsilon^2} (\varepsilon + d + 2)\vert A\vert , \quad \vert A \cap Ag\vert \geqslant \left( 1 - \frac {d \beta}{ \varepsilon^2} ( \varepsilon + d + 2) \right) \vert A\vert \] holds, and one of the inequalities \[ \vert A \cap A^\mo g\vert \leqslant \frac{d \beta}{\varepsilon^2} (\varepsilon + d + 2)\vert A\vert , \quad \vert A \cap A^\mo g\vert \geqslant \left( 1 - \frac {d \beta}{ \varepsilon^2} ( \varepsilon + d + 2) \right) \vert A\vert \] holds. Define the subset $B_+$ of $G$ by $B_+\coloneqq A \Delta (A g)^c$. The set $B_+^c$ is also equal to $(A \Delta (A g)^c)^c = A \Delta Ag$. Note that \begin{align*} \vert B_+^\mo S \Delta B_+ \vert & \leqslant \sum_{s\in S} \vert B_+^\mo s \Delta B_+\vert \\ & = \sum_{s\in S} \vert ((A \Delta (A g)^c)^\mo s) \Delta (A \Delta (A g)^c) \vert \\ & = \sum_{s\in S} \vert (A^\mo s \Delta ((A g)^c)^\mo s) \Delta (A \Delta (A g)^c) \vert \\ & = \sum_{s\in S} \vert (A^\mo s \Delta ((A g)^c)^\mo s) \Delta (A^c \Delta A g) \vert \\ & = \sum_{s\in S} \vert (A^\mo s \Delta A^c) \Delta \left(((A g)^c)^\mo s \Delta A g\right) \vert \\ & = \sum_{s\in S} \vert (A^\mo s \Delta A^c) \Delta \left(((A g)^\mo)^c s \Delta A g\right) \vert \\ & = \sum_{s\in S} \vert (A^\mo s \Delta A^c) \Delta \left((A g)^\mo s \Delta (A g)^c \right) \vert \\ & \leqslant \sum_{s\in S} \left(\vert A^\mo s \Delta A^c\vert + \vert (A g)^\mo s \Delta (A g)^c\vert \right) \\ & \leqslant \frac {2d\beta} \varepsilon (\varepsilon + d+ 2) \vert A\vert , \end{align*} and \begin{align*} \vert (B_+^c)^\mo S \Delta B_+^c \vert & \leqslant \sum_{s\in S} \vert (B_+^c)^\mo s \Delta B_+^c\vert \\ & = \sum_{s\in S} \vert ((A \Delta A g)^\mo s) \Delta (A \Delta A g) \vert \\ & = \sum_{s\in S} \vert (A^\mo s \Delta (A g)^\mo s) \Delta (A^c \Delta (A g)^c) \vert \\ & = \sum_{s\in S} \vert (A^\mo s \Delta A^c) \Delta ((A g)^\mo s \Delta (A g)^c) \vert \\ & \leqslant \sum_{s\in S} \left( \vert A^\mo s \Delta A^c\vert + \vert (A g)^\mo s \Delta (A g)^c \vert \right) \\ & \leqslant \frac{2d\beta}{\varepsilon}(\varepsilon + d + 2) \vert A\vert \end{align*} hold as a consequence of Proposition~\ref{Prop:AExists}\eqref{prop2.8_3}. We consider the following cases, viz., $\vert B_+\vert \leqslant \frac{\vert G\vert }2, \vert B_+\vert > \frac{\vert G\vert }2$. When $\vert B_+\vert \leqslant \frac{\vert G\vert }2$ holds, we obtain \[ \varepsilon \vert B_+\vert \leqslant \vert B_+^\mo S \setminus B_+\vert \leqslant \vert B_+^\mo S \Delta B_+\vert \leqslant \frac{2d \beta}\varepsilon (\varepsilon + d + 2)\vert A\vert , \] which yields \[ \vert B_+\vert \leqslant \frac {2d\beta}{ \varepsilon^2} ( \varepsilon + d + 2) \vert A\vert . \] Since \[ \vert G\vert - \vert B_+\vert = \vert B_+^c\vert = \vert A \Delta A g\vert = \vert A\vert - \vert A\cap Ag\vert + \vert Ag\vert - \vert A\cap Ag\vert = 2\vert A\vert - 2\vert A\cap Ag\vert \] holds, we obtain \[ 2\vert A \cap A g \vert \leqslant \vert G\vert - 2\vert A\vert + 2\vert A \cap A g \vert = \vert B_+\vert \leqslant \frac{2d \beta}{\varepsilon^2} (\varepsilon + d + 2)\vert A\vert . \] While $\vert B_+\vert > \frac{\vert G\vert }2$ holds, we obtain \[ \varepsilon \vert B_+^c\vert \leqslant \vert (B_+^c)^\mo S \setminus B_+^c\vert \leqslant \vert (B_+^c)^\mo S \Delta B_+^c\vert \leqslant \frac{2d\beta}{\varepsilon}(\varepsilon + d + 2) \vert A\vert , \] which yields \[ \vert B_+^c\vert \leqslant \frac{2d\beta}{\varepsilon^2}(\varepsilon + d + 2) \vert A\vert . \] Since \[ \vert B_+^c\vert = \vert A \Delta A g\vert = \vert A\vert - \vert A\cap Ag\vert + \vert Ag \vert - \vert A\cap Ag\vert = 2\vert A\vert - 2\vert A\cap Ag\vert \] holds, we obtain \[ \vert A \cap A g \vert \geqslant \vert A\vert - \frac {d\beta}{ \varepsilon^2} ( \varepsilon + d + 2)\vert A\vert =\left( 1- \frac {d\beta}{ \varepsilon^2} ( \varepsilon + d + 2)\right)\vert A\vert . \] Considering the subset $B_-$ of $G$ defined by $B_- : = A \Delta (A^\mo g)^c$, and using Proposition~\ref{Prop:AExists}\eqref{prop2.8_5} and similar arguments as above, we obtain that \[ \vert A \cap A^\mo g \vert \leqslant \frac{d \beta}{\varepsilon^2} (\varepsilon + d + 2)\vert A\vert \] or \[ \vert A \cap A^\mo g \vert \geqslant \left( 1- \frac {d\beta}{ \varepsilon^2} ( \varepsilon + d + 2)\right)\vert A\vert \] holds according as $\vert B_-\vert \leqslant \frac{\vert G\vert }2$ or $\vert B_-\vert > \frac{\vert G\vert }2$. \end{proof} \begin{theorem}\label{thmPrincipal} Let $C_\Sigma(G, S)$ be a non-bipartite $(n,d,\varepsilon)$-vertex expander for some $\varepsilon>0$. Then the eigenvalues of the normalised adjacency matrix of this graph are greater than $-1 + \ell_{\varepsilon, d}$ with \[ \ell_{\varepsilon, d} =\frac{\varepsilon^4}{2^9 d^8}. \] \end{theorem} \begin{proof} On the contrary, let us assume that an eigenvalue of the normalised adjacency matrix of the graph $C_\Sigma(G, S)$ lies in the interval $\left[-1, -1 + \ell_{\varepsilon, d}\right]$. Since $C_\Sigma(G, S)$ is non-bipartite, it follows that $-1$ is not an eigenvalue of its normalised adjacency matrix. Hence an eigenvalue of the normalised adjacency matrix of the graph $C_\Sigma(G, S)$ lies in the interval $(-1, -1+ \ell_{\varepsilon, d}]$. Set \begin{align*} \tau & = d^2 \sqrt{2 \ell_{\varepsilon, d}(2- \ell_{\varepsilon, d})},\\ r & = 1- \frac {d \tau}{ \varepsilon^2} ( \varepsilon + d + 2). \end{align*} Since $\ell_{\varepsilon, d} = \frac{\varepsilon^4}{2^9 d^8}$, we have \[ \tau = d^2 \sqrt{2 \ell_{\varepsilon, d}(2- \ell_{\varepsilon, d})} < d^2 \sqrt{4 \ell_{\varepsilon, d}} \leqslant \frac{\varepsilon^{2}}{8\sqrt{2}d^{2}}, \] \[ 1 - r = \frac {d \tau}{ \varepsilon^2} ( \varepsilon + d + 2) < \frac 1{8\sqrt 2 d} ( \varepsilon + d + 2) \leqslant \frac 1{8\sqrt 2 d} ( d-1 + d + 2) \leqslant \frac {3} {8\sqrt 2} < \frac 13. \] Consequently, \begin{equation} \label{Eqn:Bounds} \ell_{\varepsilon, d}\leqslant \frac{\varepsilon^2}{4d^4}, \tau < \frac{\varepsilon^2}{4d(d+1)} \text{ and } r> \frac 23. \end{equation} Define the subsets $H_+, H_-$ of $G$ by \begin{align*} H_+ & \coloneqq \{ g\in G \,:\,\, \vert A \cap A g \vert \geqslant r\vert A\vert \}, \\ H_- & \coloneqq \{ g\in G \,:\,\, \vert A \cap A^\mo g \vert \geqslant r\vert A\vert \}. \end{align*} Note that $H_+$ contains the identity element of $G$. By the triangle inequality, \begin{align*} \vert A \setminus A gh\vert & \leqslant \vert A \setminus A h \vert + \vert A h \setminus A gh\vert \\ & = \vert A \setminus A h \vert + \vert A \setminus A g\vert \\ & = \vert A \vert - \vert A \cap A h \vert + \vert A \vert - \vert A \cap A g\vert \\ & \leqslant 2\vert A\vert - 2r \vert A\vert . \end{align*} Consequently, \[ \vert A \cap A gh\vert = \vert A \vert - \vert A \setminus Agh\vert \geqslant \vert A \vert - 2\vert A\vert + 2r \vert A\vert = (2r - 1) \vert A\vert . \] If $\vert A \cap A gh \vert \leqslant (1-r) \vert A\vert $, then we obtain \[ (1-r) \vert A\vert \geqslant \vert A \cap A gh\vert \geqslant (2r - 1) \vert A\vert , \] which implies $r\leqslant \frac 23$. Since $r>\frac 23$, by Proposition~\ref{Prop:Dichotomy}\eqref{prop2.9_1}, it follows that $H_+$ contains $gh$. So $H_+$ is a subgroup of $G$. Note that $H_+$ is not equal to $G$, otherwise, we will obtain \[ \vert A\vert \cdot \frac{\vert G\vert }{2} \geqslant \vert A\vert ^2 = \sum_{g\in G} \vert A\cap Ag\vert \geqslant \vert G\vert \cdot r\vert A\vert , \] which yields $r\leqslant \frac 12$. The following estimate \[ \vert A\vert ^2 = \sum_{g\in G} \vert A\cap Ag\vert \leqslant \vert H_+\vert \vert A\vert + \frac{d\tau}{\varepsilon^2}(\varepsilon + d+ 2)\vert A\vert \vert G\setminus H_+\vert \] implies \[ \vert A\vert \leqslant \vert H_+\vert + \frac{d\tau}{\varepsilon^2}(\varepsilon + d+ 2)(\vert G\vert - \vert H_+\vert ). \] Using Proposition~\ref{Prop:AExists}\eqref{prop2.8_1}, we obtain \[ \frac{1}{2+ \tau + \frac{d\tau}{\varepsilon}} \vert G\vert - \frac{d\tau}{\varepsilon^2}(\varepsilon + d+ 2)\vert G\vert \leqslant \left(1 - \frac{d\tau}{\varepsilon^2}(\varepsilon + d+ 2)\right) \vert H_+\vert . \] We claim that $H_+$ is a subgroup of $G$ of index two. To prove this claim, it suffices to show that \begin{equation} \label{Eqn:13rdInePri} \frac 13 \left(1 - \frac{d\tau}{\varepsilon^2}(\varepsilon + d+ 2)\right) < \frac{1}{2+ \tau + \frac{d\tau}{\varepsilon}} - \frac{d\tau}{\varepsilon^2}(\varepsilon + d+ 2), \end{equation} \ie \[ \left(2 + \tau + \frac{d\tau}{\varepsilon}\right) \left( 1 + \frac{2d\tau}{\varepsilon^2}(\varepsilon + d+ 2) \right) < 3, \] which is equivalent to \begin{equation} \label{Eqn:13rdInequality} \left(\tau + \frac{d\tau}{\varepsilon}\right) + \frac{2d\tau}{\varepsilon^{2}}(\varepsilon + d+ 2)\left(2 + \tau + \frac{d\tau}{\varepsilon}\right) < 1. \end{equation} Let $R = \tau + \frac{d\tau}{\varepsilon}$. From~\eqref{Eqn:EpsilonBound}, we obtain \[ \tau < \frac{1}{8\sqrt{2}}\left(1-\frac{1}{d} \right)^{2}, \frac{d\tau}{\varepsilon} < \frac{1}{8\sqrt{2}}\left(1-\frac{1}{d} \right) \text{ and } R < \frac{1}{8\sqrt{2}} \left(2 - \frac{3}{d} + \frac{1}{d^{2}}\right). \] From~\eqref{Eqn:13rdInequality}, it suffices to show that \[ R + \frac{1}{4\sqrt{2}}\left(2 + \frac{1}{d} \right)(2+ R) < 1. \] \ie it suffices to show that \[ \frac{1}{8\sqrt{2}} \left(2 - \frac{3}{d} + \frac{1}{d^{2}}\right) + \frac{1}{4\sqrt{2}}\left(2 + \frac{1}{d} \right)\left(2+ \frac{1}{8\sqrt{2}} \left(2 - \frac{3}{d} + \frac{1}{d^{2}}\right)\right)<1. \] Collecting the terms, it suffices to show that, \[ \left( \frac 5 {4 \sqrt 2} + \frac 1 {16} \right) + \left(\frac 1 {8\sqrt 2} - \frac 1{16}\right) \frac 1d + \left( \frac 1 {8\sqrt 2} - \frac 1 {64}\right)\frac 1{d^2} + \frac 1 {64} \frac 1{d^3 } < 1, \] which reduces to \[ (60 - 40 \sqrt 2)d^3 - 4(\sqrt 2 -1) d^2 - (4\sqrt 2 - 1) d - 1>0. \] The above cubic polynomial in $d$ is positive for $d\geqslant 2$ and hence the claim that $H_+$ is a subgroup of $G$ of index two follows. By Proposition~\ref{Prop:AExists}\eqref{prop2.8_2}, $H_-$ does not intersect the set $S$. Similar to as before, the following estimate \[ \vert A\vert ^2 = \sum_{g\in G} \vert A\cap A^\mo g\vert \leqslant \vert H_-\vert \vert A\vert + \frac{d\tau}{\varepsilon^2}(\varepsilon + d+ 2)\vert A\vert \vert G\setminus H_-\vert \] implies \[ \vert A\vert \leqslant \vert H_-\vert + \frac{d\tau}{\varepsilon^2}(\varepsilon + d+ 2)(\vert G\vert - \vert H_-\vert ). \] This inequality combined with Proposition~\ref{Prop:AExists}\eqref{prop2.8_1} yields \[ \frac{1}{2+ \tau + \frac{d\tau}{\varepsilon}} \vert G\vert - \frac{d\tau}{\varepsilon^2}(\varepsilon + d+ 2)\vert G\vert \leqslant \left(1 - \frac{d\tau}{\varepsilon^2}(\varepsilon + d+ 2)\right) \vert H_-\vert . \] The inequality in~\eqref{Eqn:13rdInePri} (which has been established) implies that \[ \vert H_-\vert > \frac{\vert G\vert }{3}, \] and consequently, $H_-$ is nonempty. Note that for $h_-\in H_-, h_+\in H_+$, the triangle inequality implies \begin{align*} \vert A\setminus A^\mo h_- h_+\vert & \leqslant \vert A \setminus Ah_+\vert + \vert Ah_+ \setminus A^\mo h_-h_+\vert \\ & = \vert A \setminus Ah_+\vert + \vert A \setminus A^\mo h_-\vert \\ & = \vert A\vert - \vert A \cap Ah_+\vert + \vert A\vert - \vert A \cap A^\mo h_-\vert \\ & \leqslant 2\vert A\vert - 2r\vert A\vert , \end{align*} which yields \[ \vert A\cap A^\mo h_- h_+\vert = \vert A\vert - \vert A\setminus A^\mo h_- h_+\vert \geqslant \vert A\vert - 2\vert A\vert + 2r\vert A\vert = (2r-1)\vert A\vert . \] If $\vert A\cap A^\mo h_- h_+\vert \leqslant (1- r)\vert A\vert $, then we will obtain \[ (1-r) \vert A\vert \geqslant \vert A\cap A^\mo h_- h_+\vert \geqslant (2r-1)\vert A\vert , \] which in turn implies $r\leqslant \frac 23$. Since $r>\frac 23$, using Proposition~\ref{Prop:Dichotomy}\eqref{prop2.9_2}, we conclude that $\vert A\cap A^\mo h_- h_+\vert \geqslant r \vert A\vert $, \ie $H_-$ contains $h_-h_+$. Thus, $H_-H_+$ is contained in $H_-$. Since $H_-$ is a nonempty proper subset of $G$, it follows that $H_-$ is equal to $H_+$ or $H_-$ is equal to the non-trivial coset of $H_+$ in $G$, \ie $G\setminus H_+$. Note that if $H_-$ is not equal to $H_+$, then the index two subgroup $H_+$ of $G$ will contain $S$ (since $H_-\cap S = \emptyset$). Since the graph $C_\Sigma(G, S)$ is an expander, it is connected (otherwise, for a connected component $C$ of least size, the ratio of the size of the boundary of $C$ to the size of $C$ would be zero, which is impossible in this case). Thus, every element of $G$ is connected to the identity element. So, any element of $G$ can be expressed as a product of elements of the set $S\cup S^\mo$. This shows that $G$ is contained in $H_+$, which is impossible. So $H_-$ is equal to $H_+$. Consequently, $H_+$ is a subgroup of $G$ of index two avoiding $S$. Thus, the graph $C_\Sigma(G, S)$ is bipartite by Lemma~\ref{Lemma:Bipartite}. We are done. \end{proof} \begin{proof}[Proof of Theorem~\ref{mainthm}] Since $C_\Sigma(G, S)$ is connected, its vertex Cheeger constant $h_\Sigma(G)$ is positive. Thus $C_\Sigma(G, S)$ is an $h_\Sigma(G)$-expander with $h_\Sigma(G)>0$. So Theorem~\ref{mainthm} follows from Theorem~\ref{thmPrincipal}. \end{proof} \begin{proof} [Proof of Corollary~\ref{Corollary}] From Theorem~\ref{mainthm}, it follows that for any $k\geqslant 1$, the eigenvalues of the normalised adjacency matrix of $C_\Sigma(G_k, S_k)$ are greater than $- 1+ \frac{\varepsilon^4}{2^9d^8}$, which depends on $\varepsilon, d$, but not on $k$. Hence the corollary. \end{proof} In the context of Cayley graphs, the first author obtained the following bound on the spectrum of the adjacency operator. \begin{theorem} [{\cite[Theorem 1.4]{BiswasCheegerCayley}}] Let $\calS$ be a symmetric subset of $G$ and let $C(G,\calS)$ denote the Cayley graph of $G$ with respect to $\calS$ with $\vert \calS\vert =d$ and $h(G)$ denote its vertex Cheeger constant. If $C(G,\calS)$ is non-bipartite, then the largest eigenvalue of its normalised Laplacian matrix is less than \[ \lambda_{n}< 2 - \frac{h(G)^{4}}{2^{9}d^6(d+1)^{2}}. \] \end{theorem} As a consequence of the proof of Theorem~\ref{thmPrincipal}, we obtain the following refinement of the bound provided in the above result. \begin{theorem}\label{Bis19} Let $\calS$ be a symmetric subset of $G$ and let $C(G,\calS)$ denote the Cayley graph of $G$ with respect to $\calS$ with $\vert \calS\vert =d$ and $h(G)$ denote its vertex Cheeger constant. Suppose $\calS$ does not contain the identity element. If the graph $C(G, \calS)$ is non-bipartite, then the largest eigenvalue of its normalised Laplacian matrix is less than \[ 2 - \frac{h(G)^{4}}{2^{9} d^{8}}. \] \end{theorem} \begin{proof} Suppose $C(G, \calS)$ is an $\epsilon$-vertex expander with $\epsilon>0$ and it is non-bipartite. We claim that the largest eigenvalue of the normalised Laplacian matrix is less than \[ 2 - \frac{\epsilon^{4}}{2^{9} d^{8}}. \] The bound on this eigenvalue given by~\cite[Theorem 1.4]{BiswasCheegerCayley} is \[ 2 - \frac{\epsilon^{4}}{2^{9} d^6(d+1)^2}. \] Note that the proof of this result as in \emph{loc.cit.} crucially relies on the last inequality in~\cite[p. 306]{BiswasCheegerCayley}, \ie the inequality \begin{equation} \label{Eqn:OldBdd} \left(\beta + \frac{d\beta}{\epsilon} \right) + \frac{2d\beta}{\epsilon^2}(\epsilon + d+ 2) \left(2 + \beta + \frac{d\beta}{\epsilon} \right) <1 \end{equation} where $\beta = d^2 \sqrt{2\zeta (2-\zeta)}$. This inequality has been established using $\epsilon\leqslant d$ and the hypothesis that $\zeta = \frac{\epsilon^4}{2^9d^6(d+1)^2}$. The analogue of~\eqref{Eqn:OldBdd} in the context of Cayley sum graph is the inequality \[ \left(\tau + \frac{d\tau}{\varepsilon}\right) + \frac{2d\tau}{\varepsilon^{2}}(\varepsilon + d+ 2)\left(2 + \tau + \frac{d\tau}{\varepsilon}\right) < 1 \] in~\eqref{Eqn:13rdInequality} where $\tau = d^2\sqrt{2\ell_{\varepsilon, d}(2-\ell_{\varepsilon, d})}$. The above inequality has been established using $\varepsilon \leqslant d-1$ and $\ell_{\varepsilon, d} = \frac{\varepsilon^4}{2^9d^8}$. Hence~\eqref{Eqn:OldBdd} will be satisfied for $\zeta = \frac{\varepsilon^4}{2^9d^8}$ if $\epsilon \leqslant d-1$ holds, which follows from Proposition~\ref{Prop:nuBdd}. This shows the claim. Noting that $C(G, \calS)$ is an $h(G)$-vertex expander, and $h(G)>0$ (since the graph $C(G,\calS)$ is connected), the result follows from the claim. \end{proof} \longthanks{We thank the anonymous reviewers for a careful reading of the article and for their valuable comments and suggestions that improved the work. We wish to thank Emmanuel Breuillard for a number of helpful discussions during the opening colloquium of the M{\"u}nster Mathematics Cluster. The first author would like to acknowledge the support of the OWLF program of the Mathematisches Forschungsinstitut Oberwolfach (MFO). The second author would like to acknowledge the Initiation Grant from the Indian Institute of Science Education and Research Bhopal and the INSPIRE Faculty Award from the Department of Science and Technology, Government of India. He would also like to thank the MFO for their hospitality.} \bibliographystyle{amsplain-ac} \bibliography{ALCO_Biswas_462} \end{document}