\documentclass[ALCO,Unicode,published]{cedram} \usepackage{amssymb,xcolor, hyperref, mathrsfs} \renewcommand{\theequation}{\roman{equation}} \usepackage[]{cleveref} \newcommand{\mo}{{-1}} \newcommand{\bbZ}{\ensuremath{\mathbb{Z}}} \newcommand{\id}{\ensuremath{\mathrm{id}}} \newcommand{\calA}{\ensuremath{\mathcal{A}}} \newcommand{\calE}{\ensuremath{\mathcal{E}}} \newcommand{\calF}{\ensuremath{\mathcal{F}}} \newcommand{\calG}{\ensuremath{\mathcal{G}}} \newcommand{\calL}{\ensuremath{\mathcal{L}}} \newcommand{\calM}{\ensuremath{\mathcal{M}}} \newcommand{\calN}{\ensuremath{\mathcal{N}}} \newcommand{\calO}{\ensuremath{\mathcal{O}}} \newcommand{\scrN}{\ensuremath{\mathscr{N}}} \newcommand{\scrA}{\ensuremath{\mathscr{A}}} \newcommand{\tth}{\ensuremath{\mathfrak{h}}} \DeclarePairedDelimiter\abs{\lvert}{\rvert} \title[Spectral bound for transitive graphs and spanning subgraphs] {A spectral bound for vertex-transitive graphs and their spanning subgraphs} \author{\firstname{Arindam} \lastname{Biswas}} \address{Department of Mathematical Sciences\\ University of Copenhagen\\ Universitetsparken 5\\ DK-2100 Copenhagen\\ Denmark} \curraddr{} \email{arin.math@gmail.com} \thanks{} \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} \curraddr{} \email{jpsaha@iiserb.ac.in} \thanks{} \keywords{Spectral gap, diameter, vertex-transitive graphs, discrete Cheeger--Buser inequality} \subjclass{05C25, 05C50} \datepublished{2023-06-19} \begin{document} \newtheorem{condition}[cdrthm]{Condition} \begin{abstract} For any finite, undirected, non-bipartite, vertex-transitive graph, we establish an explicit lower bound for the smallest eigenvalue of its normalised adjacency operator, which depends on the graph only through its degree and its vertex-Cheeger constant. We also prove an analogous result for a large class of irregular graphs, obtained as spanning subgraphs of vertex-transitive graphs. Using a result of Babai, we obtain a lower bound for the smallest eigenvalue of the normalised adjacency operator of a vertex-transitive graph in terms of its diameter and its degree. \end{abstract} \maketitle \section{Introduction} The graphs that are considered in this article are undirected, finite and connected. The properties of the spectra of a graph, for instance, the distribution of eigenvalues of its adjacency operator or its Laplacian operator, encode a lot of information about its structural characteristics. Thus, they are an important object of study not only in mathematics, but in other sciences as well where graph theory is applied. Some of the structural properties, e.g.~expansion, diameter, Hamiltonicity, etc.~(to name a few), are related to the spectral gap, which depending on the context can mean either the difference between the largest and the second largest eigenvalue of its adjacency operator, or the difference between the largest and the second largest eigenvalue \emph{in absolute value} of its adjacency operator. The study of spectral bounds, that is, bounds for the spectral gap in terms of various invariants of a graph, is thus an important direction of research. Moreover, the two notions of spectral gap mentioned above and the relationship between them is interesting. Very often for applications, we need to consider the latter notion. This motivates the question of whether the two are equivalent or not, at least for particular classes of graphs. \subsection{Combinatorial expansion implies spectral expansion} From the discrete Cheeger--Buser inequality, established by Dodziuk~\cite{DodziukDifferenceEqnIsoperimetricIneq}, Alon and Milman~\cite{AlonMilmanIsoperiIneqSupConcen}, and Alon~\cite{AlonEigenvalueExpand}, it follows that the second largest eigenvalue of the normalised adjacency operator of a finite graph is bounded uniformly away from $1$ in terms of its degree and its vertex-Cheeger constant, a phenomenon which one sometimes refers to as combinatorial expansion. If the second largest eigenvalue in absolute value of the normalised adjacency operator of a finite graph is bounded uniformly away from $1$ in terms of its degree and its vertex-Cheeger constant, then we shall sometimes refer to it as two-sided spectral expansion. Breuillard--Green--Guralnick--Tao in~\cite[Appendix E]{BGGTExpansionSimpleLie} showed qualitatively that for Cayley graphs, combinatorial expansion implies two-sided spectral expansion. Later, a quantitative version of this fact was derived by the first author~\cite{BiswasCheegerCayley} and the same phenomenon with explicit bounds were also shown to hold true for variants of Cayley graphs, in prior works of the authors~\cite{CheegerCayleySum, CheegerTwisted}. Under suitable hypothesis, there is an interplay between the expansions of these graphs as studied in~\cite{Expansion}. Recently, an improved bound for Cayley graphs has been given by Moorman--Ralli--Tetali~\cite{CayleyBottomBipartite}. However, it is known that the above fact is not true for general regular graphs~\cite[Example 2.1]{CayleyBottomBipartite}. This leads to the question that for which other subclass of regular graphs or even irregular graphs, does the above phenomenon occur. In particular, the situation for vertex-transitive graphs, which form an important class of regular graphs encompassing Cayley graphs, was unknown. In this article, we adapt some of the techniques developed by Breuillard--Green--Guralnick--Tao in~\cite[Appendix E]{BGGTExpansionSimpleLie} for Cayley graphs to the context of vertex-transitive graphs, and combine them with a technique of Fre\u{\i}man~\cite{FreimanGroupsInverseProb}, to address this issue. Further, we go beyond regular graphs and obtain spectral bounds for irregular graphs obtained as spanning subgraphs of vertex-transitive graphs. \subsubsection{Vertex-transitive graphs} We prove that the vertex-transitive graphs have the property that combinatorial expansion implies two-sided spectral expansion. \begin{theorem} \label{Thm:Intro} For any finite, undirected, non-bipartite, vertex-transitive graph of degree $d$ having vertex-Cheeger constant $h$, the nontrivial spectrum of its normalised adjacency operator is contained in the interval $\left(-1 + \frac{h^4}{60^2 d^{10}}, 1- \frac{h^2}{2d^2}\right]$. \end{theorem} The above result is obtained in Proposition~\ref{Cor:SpannSubgraVertexTra}, which follows from Theorem~\ref{Thm:SpannSubgraVertexTra}, which proves the more general statement that a non-bipartite spanning subgraph of a finite, undirected, vertex-transitive graph has the property that the nontrivial spectrum of its normalised adjacency operator is bounded away from $-1$ and $1$ in terms of its degree and its vertex-Cheeger constant if the maximum degrees of these graphs are equal and the difference of their edge sets is `small.' Further, by Theorem~\ref{Thm:SpannSubgraVertexTra}, such a result also holds for non-bipartite, spanning subgraphs of regular graphs (with maximum degree equal to the degree of the ambient regular graph) such that these graphs have `small' difference in their edge sets, and the regular graph is nearly vertex-transitive (see Definition~\ref{Defn:NearlyVertexTra}). These results imply that combinatorial expansion implies two-sided spectral expansion in more general contexts (for instance, for `large' spanning subgraphs of Cayley sum graphs), and also extend the result established by Breuillard--Green--Guralnick--Tao for Cayley graphs~\cite[Appendix E]{BGGTExpansionSimpleLie}. For undirected, non-bipartite, vertex-transitive graphs, Theorem~\ref{Thm:Intro} gives a lower bound for the smallest eigenvalue of the normalised adjacency operator in terms of the vertex-Cheeger constant and the degree, thus, providing an analogue of the discrete Cheeger--Buser inequality for the smallest eigenvalue of the normalised adjacency operator. It would also be interesting to investigate whether an upper bound for the smallest eigenvalue of the normalised adjacency operator in terms of the vertex-Cheeger constant and the degree can be established for undirected, non-bipartite, vertex-transitive graphs, or even for the special case of Cayley graphs. Using fractional decomposition of graphs, Knox--Mohar have shown that the smallest eigenvalue of the normalized adjacency operator of a undirected, regular, non-bipartite, distance-regular graph with odd girth $g$ is greater than or equal to $1 - \cos \frac \pi g$ \cite[Corollary 5]{KnoxMoharFractionalDecomSmallestEigenVal}, generalizing and strengthening a result of Qiao--Jing--Koolen~\cite[Theorem 1]{QiaoJingKoolenNonBipartiteDistRegular}. \subsubsection{Irregular graphs} \label{Subsubsec:IrregularGraphs} Stevanovi\'{c} obtained a lower bound for the gap between the maximum degree and the largest eigenvalue of the adjacency operator of an irregular graph in terms of its number of vertices and the maximum degree ~\cite{StevanovicLargestEigenValueNonregGraphs}. For further related results, we refer to the works of Alon--Sudakov~\cite{AlonSudakovBipartiteSubgraphsSmallestEigenVal}, Zhang~\cite{ZhangEigenVectEigenValNonRegGraph}, Liu--Shen--Wang~\cite{LiuShenWangLargestEigenValNonRegGraph}, Cioab\u{a}--Gregory--Nikiforov~\cite{CioabaGregoryNikiforovExtremeEigenvalNonRegGraph}, Cioab\u{a}~\cite{CioabaSpecRedMaxDegIrrGraphs}, Zhang~\cite{ZhangNewResultSpecRadiusIrregGraph}, Feng--Zhang~\cite{FengZhangNoteSpectralRadiusMaxDegreeIrreg}. They obtained bounds on this gap in terms of the number of vertices, and one or both of the maximum degree and the diameter. Note the the discrete Cheeger--Buser inequality states that the second smallest eigenvalue of the Laplacian operator and the Cheeger constant of a finite graph controls each other. As a consequence, the nontrivial spectrum of the normalized adjacency operator of a finite, undirected graph is bounded away from $1$ in terms of its vertex-Cheeger constant and its degree. To the best of the knowledge of the authors, there is no known result that proves that combinatorial expansion implies two-sided spectral expansion for a large class of irregular graphs, in other words, a result implying that the smallest eigenvalue of the adjacency operator of a graph with maximum degree $d$ is bounded away from $-d$ in terms of its vertex-Cheeger constant and its maximum degree. We obtain the following result for `large' spanning subgraphs of vertex-transitive graphs, thus establishing an analogue of the discrete Cheeger--Buser inequality for these graphs. \begin{theorem} \label{Thm:IntroIrr} Suppose $\Gamma$ is a finite, undirected, connected, non-bipartite graph with vertex-Cheeger constant $h$ and maximum degree $d$. Suppose it is a subgraph of a vertex-transitive graph $\widetilde \Gamma$ such that the difference of their edge sets is `small.' Then the smallest eigenvalue of the adjacency operator of $\Gamma$ is greater than or equal to $ d \left(-1 + \frac{h^4 }{60^2 d^{10}}\right)$, and the largest eigenvalue of the Laplacian operator of $\Gamma$ is less than or equal to $d \left(2 - \frac{h^4 }{60^2 d^{10}}\right)$. \end{theorem} We refer to Proposition~\ref{Prop:SpannSubgraVertexTraEigenBdd}, Theorem~\ref{Thm:Irregular} for the precise results. Theorem~\ref{Thm:Irregular} also deals with `large' spanning subgraphs of nearly vertex-transitive graphs, which include Cayley sum graphs. \subsection{Spectral bound involving diameter and degree} Aldous established that a Cayley graph with diameter $\Delta$ is an $\frac 1{2\Delta}$-expander~\cite[Lemma 3.1]{AldousMarkovChainSimulation}. Babai proved that a vertex-transitive graph with diameter $\Delta$ is also an $\frac 1 {2\Delta}$-expander~\cite[Proposition 3.5]{BabaiLocalExpansionVertexTransitive}. This result combined with Theorem~\ref{Thm:Intro} yields the following. \begin{theorem} \label{Thm:IntroDiam} For any finite, undirected, non-bipartite, vertex-transitive graph of degree $d$ having diameter equal to $\Delta$, the smallest eigenvalue of its normalised adjacency operator is greater than $-1 + \frac{1}{240^2 \Delta^4 d^{10}}$. \end{theorem} For a bound on the second largest eigenvalue in terms of the diameter and the degree, we refer to the works of Saloff-Coste~\cite[Corollary 3.2.7]{SaloffCosteLectureFiniteMarkovChain}, Shkredov~\cite{ShkredovSpectralGapDiamCayley}. \section{Notations} Let $\Gamma$ be a finite graph with adjacency matrix $A_\Gamma$. For $u, v$ lying in the vertex set of~$\Gamma$, the $(u,v)$-th entry of $A_\Gamma$ is equal to the number of edges from $u$ to $v$ if $u\neq v$, and for $u = v$, the $(u,v)$-th entry of $A_\Gamma$ is equal to the number of loops at $u$. The matrices $T_\Gamma, T_\Gamma^\mo, L_\Gamma, \calL_\Gamma$ are defined as follows. The matrix $T_\Gamma$ is diagonal, and its $(v, v)$-th entry is equal to the degree of $v$. The matrix obtained by inverting the nonzero diagonal entries of $T_\Gamma$ is denoted by $T_\Gamma^\mo$. The matrix $T_\Gamma - A_\Gamma$ is denoted by $L_\Gamma$. The \textit{normalised Laplacian} of $\Gamma$ is denoted by $\calL_\Gamma$ and it is defined to be $T_\Gamma^{-\frac 12} L_\Gamma T_\Gamma^{- \frac 12}$. The \textit{normalised adjacency matrix} of $\Gamma$ is $T_\Gamma^{-\frac 12} A_\Gamma T_\Gamma^{- \frac 12}$. The \textit{square-graph} of $\Gamma$ is denoted by $\Gamma^2$, and it has the same set of vertices as that of $\Gamma$ and has adjacency matrix equal to $A_\Gamma^2$. The \textit{vertex-Cheeger constant} of $\Gamma$ is defined as $$\min_{X\subseteq V(\Gamma), 0 < |X| \leq \frac{|V(\Gamma)|}2} \frac{|\{v\in V(\Gamma) \setminus X\,|\, v \text{ is adjacent to some element of } X\}|}{|X|} ,$$ where $V(\Gamma)$ denotes the set of vertices of $\Gamma$. In the following, $(V, E)$ denotes a finite graph (which may contain multiple edges, and even multiple loops at certain vertices) with $|V| \geq 4$. The maximum (resp. minimum) degree of $(V, E)$ is denoted by $d$ (resp. $d'$). The adjacency operator of $(V, E)$ is denoted by $A$. The vertex-Cheeger constant of $(V, E)$ (resp. $(V, E)^2$) is denoted by~$h$ (resp. $\tth$). Let $\scrA$ be a subset of $V$ where the vertex-Cheeger constant of $(V, E)^2$ is attained. The neighbourhood of a subset $V'$ of $V$ in $(V, E)$ is denoted by $\calN(V')$. Henceforth, we assume that Condition~\ref{Cond:MaxDegDNonBipar} holds. \begin{condition} \label{Cond:MaxDegDNonBipar} \quad \begin{enumerate} \item The graph $(V, E)$ is undirected, that is, its adjacency matrix is symmetric. \item The graph $(V, E)$ is non-bipartite. \item The vertex-Cheeger constant $h$ of $(V, E)$ satisfies the inequality $h\geq \varepsilon$ where $\varepsilon$ is a positive real number. \end{enumerate} \end{condition} Set $$ \nu = \nu_d = \begin{cases} 2 & \text{ if } d = 2, \\ \frac 52 & \text{ if } d\geq 3. \end{cases} $$ Since $|V|\geq 4$ holds and the graph $(V, E)$ is an $\varepsilon$-vertex expander with $\varepsilon>0$, it follows that there are two distinct vertices $u, v$ of $V$ which are adjacent, and $$ \varepsilon |\{u, v\}| \leq |(\calN(u) \cup \calN(v) ) \setminus \{u, v\}| \leq |\calN(u) \setminus \{v\}| + |\calN(v)\setminus \{u\}| \leq 2(d-1), $$ which implies $\varepsilon \leq d-1$, and hence $\varepsilon \leq \nu -1$ if $d = 2$. If $|V|$ is odd (resp. even), then the vertex-Cheeger constant $h$ of $(V, E)$ satisfies the inequality $h \leq \frac 32$ (resp. $h \leq 1$) and hence $\varepsilon \leq \nu -1$ if $d\geq 3$. In the results below, we will work under Condition~\ref{Cond:SuubgraphOfRegularGraph}. \begin{condition} \label{Cond:SuubgraphOfRegularGraph} There exists an undirected graph $(V, \widetilde E)$ of degree $d$ (that is, its adjacency matrix is symmetric and has the constant vector $[1, \ldots, 1]$ as an eigenvector with eigenvalue $d$) such that $(V, E)$ is a subgraph of $(V, \widetilde E)$. \end{condition} Under the above condition, the size of the difference of the edge sets of $(V, E)$ and $(V, \widetilde E)$ is denoted by $r$, the size of the difference of the edge sets of their square graphs is denoted by $s$, the vertex-Cheeger constant of $(V, \widetilde E)$ is denoted by $\widetilde h$. Note that $2r$ (resp. $2s$) is equal to the difference of the sum of the entries of the adjacency operator of $(V, \widetilde E)$ (resp. $(V, \widetilde E)^2$) and the sum of the entries of the adjacency operator of $(V, E)$ (resp. $(V, E)^2$). \begin{remark} \label{Rk:NotationsCalN} If Condition~\ref{Cond:SuubgraphOfRegularGraph} holds, then the neighbourhood of a subset $V'$ of $V$ in $(V, \widetilde E)$ is denoted by $\widetilde \calN(V')$. By the Birkhoff-von Neumann theorem~\cite[Theorem~5.5]{vanLintWilsonCourseCombi}, there exist permutations $\theta_1, \ldots, \theta_d: V\to V$ such that the vertices $v, \theta_i(v)$ are adjacent in $(V, \widetilde E)$ for any $v\in V$ and $1\leq i \leq d$, and that $\widetilde \calN(v)$ is equal to $\cup_{i=1}^d \{\theta_i(v)\}$ for any $v\in V$. For a subset $V'$ of $V$, denote the subset $\theta_i(V')$ of $\widetilde \calN(V')$ by $\widetilde \calN^i(V')$, and the subset $\theta_i(V') \cap \calN (V')$ of $\calN(V')$ by $\calN^i(V')$. \end{remark} \section{Bounds on the vertex-Cheeger constant of the square graph} \begin{proposition} \label{Prop:AExists} Suppose the vertex-Cheeger constant $\tth$ of the graph $(V, E)^2$ satisfies $\tth \leq \beta$ for some $0 < \beta < \varepsilon$. Then, the following statements hold. \begin{enumerate} \item The inequalities $$\frac {|V| -s}{2 + \beta + \frac{\nu\beta}{\varepsilon} } \leq |\scrA| \leq \frac 12 |V|$$ hold. \item Let $\tau: V \to V$ be a bijection such that $$ \widetilde\calN (\widetilde\calN(\tau(\scrA)))\subseteq \tau(\widetilde \calN(\widetilde \calN(\scrA))) $$ holds. If $ \frac {2d\beta} { \varepsilon^2} ( 2\nu + 1) + \frac{2d s}{\varepsilon^2 |\scrA|} + \frac{3dr}{\varepsilon |\scrA|} + \frac{2ds}{\varepsilon |\scrA|} <1 $, then exactly one of the inequalities \begin{align*} |\scrA \cap (\tau(\scrA)) | & \leq \frac{d \beta}{\varepsilon^2} (\varepsilon + \nu + 2)|\scrA|+ \frac {ds}{\varepsilon^2} + \frac{2dr}\varepsilon +\frac{ds}{\varepsilon},\\ |\scrA \cap (\tau(\scrA)) | & \geq \left( 1- \frac {d\beta}{ \varepsilon^2} ( \varepsilon + \nu + 2)\right)|\scrA| - \frac {ds}{\varepsilon^2} -\frac{dr}{\varepsilon} -\frac{ds}{\varepsilon} \end{align*} holds. \end{enumerate} \end{proposition} \begin{proof} Note that $|\scrA \cup \calN(\scrA)| \geq \frac{|V|}{2}$. Otherwise, we obtain $$\varepsilon |\scrA| \leq \varepsilon |\scrA \cup \calN(\scrA)| \leq |\calN( \scrA \cup \calN(\scrA)) \setminus (\scrA \cup \calN(\scrA))| \leq \beta |\scrA|,$$ which contradicts $\beta < \varepsilon$. It follows from the proof of~\cite[Proposition 2.7]{CheegerCayleySum} that for a subset $X$ of $V$ with $|X|\geq \frac 12 |V|$, the inequality $$|\calN(X) \setminus X| \geq \frac \varepsilon \nu |V \setminus X|$$ holds. Consequently, we obtain $$ \varepsilon|V \setminus (\scrA \cup \calN(\scrA))| \leq \nu |\calN(\scrA \cup \calN(\scrA)) \setminus (\scrA \cup \calN(\scrA))| \leq \nu |\calN(\calN(\scrA))\setminus \scrA| \leq \nu \beta |\scrA|,$$ which yields \begin{align*} |V| & \leq \frac{\nu\beta}{\varepsilon}|\scrA| + |\scrA \cup \calN(\scrA)|\\ & \leq \frac{\nu\beta}{\varepsilon}|\scrA| + |\scrA| + |\calN(\scrA)| \\ &\leq \frac{\nu\beta}{\varepsilon}|\scrA| + |\scrA| + |\widetilde \calN(\scrA)| \\ & \leq \frac{\nu\beta}{\varepsilon}|\scrA| + |\scrA| + |\widetilde \calN( \widetilde \calN(\scrA))| \\ & \leq \frac{\nu\beta}{\varepsilon}|\scrA| + |\scrA| + |\calN( \calN(\scrA))| + s \\ & \leq \frac{\nu\beta}{\varepsilon}|\scrA| + 2|\scrA| + |\calN(\calN(\scrA))\setminus \scrA| + s. \end{align*} This proves statement~(1). Since $s$ is the size of the difference of the edge sets of the square graphs of $(V, E), (V, \widetilde E)$, it follows that \begin{align*} |\calN(\calN(\tau(\scrA))) \setminus \tau(\scrA)| & \leq |\tau(\widetilde \calN(\widetilde \calN(\scrA))) \setminus \tau(\scrA)|\\ & \leq |\widetilde \calN(\widetilde \calN(\scrA)) \setminus \scrA|\\ & \leq s+ | \calN(\calN(\scrA)) \setminus \scrA|. \end{align*} Let $B = \scrA\Delta(\tau(\scrA))^c$. The identity map from $V$ to $V$ is denoted by $\id$. We shall compute certain upper bounds on $|\calN(B) \Delta B|$ and on $|\calN(B^c) \Delta B^c|$. It follows that \begin{align*} &|\calN^i(B) \Delta B| \\ & \leq |\calN^i(\scrA) \Delta \calN^i((\tau(\scrA))^c) \Delta \scrA \Delta(\tau(\scrA))^c| \\ & \leq |\calN^i(\scrA) \Delta \calN^i((\tau(\scrA))^c) \Delta \scrA^c \Delta \tau(\scrA)| \\ & \leq |\calN^i(\scrA) \Delta \scrA^c \Delta \calN^i((\tau(\scrA))^c) \Delta \tau(\scrA)| \\ & \leq |\calN^i(\scrA) \Delta \scrA^c| + |\calN^i((\tau(\scrA))^c) \Delta \tau(\scrA)|\\ & \leq |\calN^i(\scrA) \Delta \scrA^c| + |\calN^i(\tau(\scrA)) \Delta (\tau(\scrA))^c| + 2r\\ & \leq \sum_{\phi\in \{\id, \tau\}} \left( |V| - 2|\calN^i(\phi(\scrA)) \cap \phi(\scrA^c)|\right) + 2r\\ & = \sum_{\phi\in \{\id, \tau\}} \left( |V| - 2|\calN^i(\phi(\scrA))| + 2|\calN^i(\phi(\scrA))| - 2|\calN^i(\phi(\scrA)) \cap \phi(\scrA^c)|\right) + 2r \\ & \leq \sum_{\phi\in \{\id, \tau\}} \left( |V| - 2|\scrA| + 2|\calN^i(\phi(\scrA)) \cap \phi(\scrA)|\right) + 4r \\ & = 2(|V| - 2|\scrA|) + 2\sum_{\phi\in \{\id, \tau\}} |\calN^i(\phi(\scrA)) \cap \phi(\scrA)| + 4r \\ & \leq 2(|V| - 2|\scrA|) + \frac 2\varepsilon\sum_{\phi\in \{\id, \tau\}} \varepsilon|\calN(\phi(\scrA)) \cap \phi(\scrA)| + 4r\\ & \leq 2(|V| - 2|\scrA|) + \frac 2\varepsilon\sum_{\phi\in \{\id, \tau\}} |\calN(\calN(\phi(\scrA)) \cap \phi(\scrA)) \setminus (\calN(\phi(\scrA)) \cap \phi(\scrA))| + 4r\\ & \leq 2(|V| - 2|\scrA|) + \frac 2\varepsilon\sum_{\phi\in \{\id, \tau\}} |\calN(\calN(\phi(\scrA)) \setminus \phi(\scrA)| + 4r\\ & \leq 2(|V| - 2|\scrA|) + \frac 2\varepsilon (s+ 2 |\calN(\calN(\scrA)) \setminus \scrA| ) + 4r\\ & \leq 2\left(\beta + \frac{\nu\beta}\varepsilon \right)|\scrA| +\frac 2\varepsilon 2|\scrA|\beta + \frac {2s}\varepsilon + 4r + 2s\\ & = \frac{2\beta}\varepsilon (\varepsilon + \nu + 2)|\scrA| + \frac {2s}\varepsilon + 4r + 2s. \end{align*} This implies that $$ |\calN(B) \Delta B| \leq \frac{2d\beta}\varepsilon (\varepsilon + \nu + 2)|\scrA| + \frac {2ds}\varepsilon + 4dr + 2ds. $$ Note that \begin{align*} |\calN^i(B^c) \Delta B^c| & \leq |\calN^i(\scrA) \Delta \calN^i(\tau(\scrA)) \Delta \scrA \Delta\tau(\scrA)| \\ & \leq |\calN^i(\scrA) \Delta \calN^i(\tau(\scrA)) \Delta \scrA^c \Delta (\tau(\scrA))^c| \\ & \leq |\calN^i(\scrA) \Delta \scrA^c \Delta \calN^i(\tau(\scrA)) \Delta (\tau(\scrA))^c| \\ & \leq |\calN^i(\scrA) \Delta \scrA^c| + |\calN^i(\tau(\scrA)) \Delta (\tau(\scrA))^c| )\\ & \leq |\calN^i(\scrA) \Delta \scrA^c| + |V| - 2 |\calN^i(\tau(\scrA)) \cap (\tau(\scrA))^c| \\ & \leq \frac{2\beta}\varepsilon (\varepsilon + \nu + 2)|\scrA| + \frac {2s}\varepsilon + 2r + 2s. \end{align*} This yields $$ |\calN(B^c) \Delta B^c| \leq \frac{2d\beta}\varepsilon (\varepsilon + \nu + 2)|\scrA| + \frac {2ds}\varepsilon + 2dr + 2ds. $$ Finally, we consider the following cases, namely, $|B|\leq \frac{|V|}2$ and $|B| > \frac{|V|}2$. When $|B|\leq \frac{|V|}2$ holds, we obtain $$ \varepsilon |B| \leq |\calN(B) \setminus B| \leq |\calN(B) \Delta B| \leq \frac{2d \beta}\varepsilon (\varepsilon + \nu + 2)|\scrA| + \frac {2ds}\varepsilon + 4dr +2ds, $$ which gives $$|B| \leq \frac {2d\beta}{ \varepsilon^2} ( \varepsilon + \nu + 2) |\scrA|+ \frac {2ds}{\varepsilon ^2} + \frac{4dr}\varepsilon +\frac{2ds}{\varepsilon}. $$ From $$ |V| - |B| = |B^c| = |\scrA \Delta (\tau (\scrA))| = 2|\scrA| - 2|\scrA\cap (\tau(\scrA))| , $$ we obtain $$ 2|\scrA \cap (\tau(\scrA)) | \leq |V| - 2|\scrA| + 2|\scrA \cap (\tau(\scrA))| = |B| \leq \frac{2d \beta}{\varepsilon^2} (\varepsilon + \nu + 2)|\scrA|+ \frac {2ds}{\varepsilon^2} + \frac{4dr}\varepsilon +\frac{2ds}{\varepsilon}. $$ When $|B| > \frac{|V|}2$ holds, we obtain $$ \varepsilon |B^c| \leq |\calN(B^c)\setminus B^c| \leq |\calN(B^c)\Delta B^c| \leq \frac{2d\beta}{\varepsilon}(\varepsilon + \nu + 2) |\scrA|+ \frac {2ds}\varepsilon + 2dr + 2ds , $$ which gives $$|B^c| \leq \frac{2d\beta}{\varepsilon^2}(\varepsilon + \nu + 2) |\scrA|+ \frac {2ds}{\varepsilon ^2} +\frac{2dr}{\varepsilon} +\frac{2ds}{\varepsilon}, $$ and hence \begin{align*} |\scrA \cap (\tau(\scrA)) | &\geq |\scrA| - \frac {d\beta}{ \varepsilon^2} ( \varepsilon + \nu + 2)|\scrA| - \frac {ds}{\varepsilon^2} -\frac{dr}{\varepsilon} -\frac{ds}{\varepsilon}\\ &= \left( 1- \frac {d\beta}{ \varepsilon^2} ( \varepsilon + \nu + 2)\right)|\scrA| - \frac {ds}{\varepsilon^2} -\frac{dr}{\varepsilon} -\frac{ds}{\varepsilon} . \end{align*} This completes the proof of statement~(2). \end{proof} \begin{theorem}\label{Thm:AlmostGraphAut} Assume that a group $\calG$ acts transitively on $V$ from the left, no index two subgroup of $\calG$ acts transitively on $V$, and for any $g\in \calG$, the set $ \widetilde \calN (\widetilde \calN(g(\scrA)))$ is contained in $g(\widetilde \calN(\widetilde \calN(\scrA))) $. Let $\mu> 0$ be such that for any subgroup $H$ of $\calG$ of index two and for any $u, v\in V$ lying in the same $H$-orbit with $u\in \widetilde \calN(v)$, the inequalities \begin{equation} \label{Eqn:muBdd} |\theta_i(Hv)\cap Hu| \geq \frac{|V|}{2\mu}, \quad |\theta_i(H^c v)\cap H^c u| \geq \frac{|V|}{2\mu} \end{equation} hold for some integer $i_{u,v}$ depending on $u, v$ and lying between $1$ and $d$. \begin{enumerate} \item If \begin{equation} \label{Eqn:V108bdd20} \mu = 1, \quad |V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d} \right) \left( \frac{ds}{\varepsilon^2} + \frac{dr}\varepsilon +\frac{ds}{\varepsilon}\right) + s , \end{equation} then the vertex-Cheeger constant of the graph $(V, E)^2$ is greater than $\frac{\varepsilon^{2}}{30d}$. \item If \begin{equation} \label{Eqn:V108bdd} \mu = 2, \quad |V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {72d} \right) \left( \frac{ds}{\varepsilon^2} + \frac{dr}\varepsilon +\frac{ds}{\varepsilon}\right) + s , \end{equation} then the vertex-Cheeger constant of the graph $(V, E)^2$ is greater than $\frac{\varepsilon^{2}}{72d}$. \item If \begin{equation} \label{Eqn:V108bdd20d3} \mu = d, \quad |V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d^3} \right) \left( \frac{d^3s}{\varepsilon^2} + \frac{d^3r}\varepsilon+ \frac{d^{3}s}{\varepsilon}\right) + s, \end{equation} then the vertex-Cheeger constant of the graph $(V, E)^2$ is greater than $ \frac{\varepsilon^{2}}{30d^3}$. \end{enumerate} \end{theorem} \begin{proof} On the contrary, assume that the vertex-Cheeger constant $\tth$ of the graph $(V, E)^2$ satisfies $\tth \leq \frac{\varepsilon^{2}}{30d}$. Set \begin{align*} r & = 1- \frac {d \tth}{ \varepsilon^2} ( \varepsilon + \nu + 2). \end{align*} Since $\varepsilon \leq \nu -1$, it follows that $$ 1 - r = \frac {d \tth}{ \varepsilon^2} ( \varepsilon + \nu + 2) \leq \frac {d \tth}{ \varepsilon^2} (2\nu+1) \leq \frac{2\nu +1}{30} \leq \frac 3{10}.$$ Using $\tth \leq \frac{\varepsilon^{2}}{30d}$ and Equation~\eqref{Eqn:V108bdd20}, we obtain \begin{align*} |\scrA| \left( 2 + \tth + \frac {\nu \tth} {\varepsilon} \right) & \geq |V| - s\\ & \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d} \right) \left( \frac{ds}{\varepsilon^2} + \frac{dr}\varepsilon + \frac{ds}{\varepsilon}\right) \\ & \geq 108 \left( 2 + \frac {\varepsilon (\varepsilon + \nu)} {30d} \right) \left( \frac{ds}{\varepsilon^2} + \frac{dr}\varepsilon + \frac{ds}{\varepsilon}\right) \\ & \geq 108 \left( 2 + \tth + \frac {\nu\tth} {\varepsilon} \right) \left( \frac{ds}{\varepsilon^2} + \frac{dr}\varepsilon + \frac{ds}{\varepsilon}\right) , \end{align*} which implies $ \frac{ ds}{\varepsilon^2 } + \frac{ dr}{\varepsilon } + \frac{ds}{\varepsilon}\leq \frac{|\scrA|}{108}$. Similarly, if $\tth \leq \frac{\varepsilon^{2}}{72d}$, then Equation~\eqref{Eqn:V108bdd} implies $ \frac{ ds}{\varepsilon^2 } + \frac{ dr}{\varepsilon } + \frac{ds}{\varepsilon} \leq \frac{|\scrA|}{108}$. Moreover, if $\tth \leq \frac{\varepsilon^{2}}{30d^3}$, then Equation~\eqref{Eqn:V108bdd20d3} implies $ \frac{ ds}{\varepsilon^2 } + \frac{ dr}{\varepsilon } + \frac{ds}{\varepsilon}\leq \frac{|\scrA|}{108}$. Consequently, $r\geq \frac 7{10}$ and $$ \frac {2d\tth} { \varepsilon^2} ( 2\nu + 1) + \frac{2d s}{\varepsilon^2 |\scrA|} + \frac{3dr}{\varepsilon |\scrA|} + \frac{2ds}{\varepsilon |\scrA|} \leq \frac 3{5} + \frac 3 {108} < 1. $$ Consider the subset $H$ of $\calG$ defined by $$H := \left\{ g\in \calG \,:\,\, |\scrA \cap (g(\scrA))| \geq r|\scrA| - \frac{ds}{\varepsilon^2} - \frac{dr}{\varepsilon} - \frac{ds}{\varepsilon} \right\}.$$ Note that $H$ contains the identity element of $\calG$. Let $g_1, g_2$ be elements of $H$. By the triangle inequality, \begin{align*} |\scrA \setminus (g_1(g_2(\scrA)))| & \leq |\scrA \setminus (g_1(\scrA)) | + |(g_1(\scrA)) \setminus (g_1(g_2(\scrA)))| \\ & = |\scrA \setminus (g_1(\scrA)) | + |\scrA \setminus (g_2(\scrA)) |\\ & = |\scrA | - |\scrA \cap (g_1(\scrA)) | + |\scrA | - |\scrA \cap (g_2(\scrA)) |\\ & \leq 2|\scrA| - 2r |\scrA| + \frac{2ds}{\varepsilon^2} + \frac{2dr}{\varepsilon} +\frac{2ds}{\varepsilon} , \end{align*} which yields that \begin{align*} |\scrA \cap (g_1(g_2(\scrA)))| & = |\scrA | - |\scrA \setminus (g_1(g_2(\scrA)))| \\ & \geq |\scrA | - 2|\scrA| + 2r |\scrA| - \left(\frac{2ds}{\varepsilon^2} +\frac{2dr}{\varepsilon} + \frac{2ds}{\varepsilon} \right)\\ & = (2r - 1) |\scrA| - \left(\frac{2ds}{\varepsilon^2} + \frac{2dr}{\varepsilon} +\frac{2ds}{\varepsilon} \right). \end{align*} If $|\scrA \cap (g_1(g_2(\scrA)))| \leq (1-r) |\scrA| + \frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon +\frac{ds}{\varepsilon}$, then we obtain \begin{align*} (1-r) |\scrA| + \frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon + \frac{ds}{\varepsilon} &\geq |\scrA \cap (g_1(g_2(\scrA)))| \\ &\geq (2r - 1) |\scrA| - \left(\frac{2ds}{\varepsilon^2} + \frac{2dr}{\varepsilon} + \frac{2ds}{\varepsilon} \right), \end{align*} which yields $(3r-2) |\scrA| \leq \frac{3ds}{\varepsilon^2} + \frac{4dr}{\varepsilon} + \frac{3ds}{\varepsilon} \leq \frac {|\scrA|}{ 11}, $ which contradicts $ r \geq \frac 7{10}$. So, the inequality $|\scrA \cap (g_1(g_2(\scrA)))| \leq (1-r) |\scrA| + \frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon + \frac{ds}{\varepsilon}$ does not hold. By Proposition~\ref{Prop:AExists}(2), $H$ contains the product $g_1g_2$. Consequently, $H$ is a subgroup of $\calG$. Let $t$ denote the cardinality of the stabiliser of an element of $V$ under the action of $\calG$. Note that for any $g\in \calG$, the map $$\scrA\cap g^\mo \scrA \to \scrA\times \scrA, \quad x\mapsto (x, gx)$$ induces a map $$\varphi: \coprod _{g\in \calG} \scrA\cap g^\mo \scrA \to \scrA\times \scrA.$$ Each fibre of this map contains exactly $t$ elements. This implies $$ |\scrA|^2 = |im(\varphi)| = \sum_{x\in im(\varphi) } \frac{|\varphi^\mo (x)|} {|\varphi^\mo (x)|} = \frac 1t \sum_{x\in im(\varphi)} |\varphi^\mo (x)| = \frac 1t \sum_{g\in \calG} |\scrA\cap g^\mo \scrA|.$$ If $\calG = H$, then $$|\scrA| \cdot \frac{|V|}{2} \geq |\scrA|^2 = \frac 1t \sum_{g\in \calG} |\scrA\cap g^\mo \scrA| \geq \frac 1t |\calG| \cdot \left(r|\scrA| - \frac{ds}{\varepsilon^2} - \frac{dr}{\varepsilon} - \frac{ds}{\varepsilon} \right),$$ which implies $r \leq \frac 12 + \frac 1{108}$. This contradicts the bound $r \geq \frac 7 {10}$. So, $H$ is a proper subgroup of $\calG$. The estimate \begin{align*} t |\scrA|^2 &= \sum_{g\in \calG} |\scrA\cap g^\mo \scrA| \\ &\leq |H| |\scrA| + \left( \frac{d\tth}{\varepsilon^2}(\varepsilon + \nu+ 2)|\scrA| + \frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon + \frac{ds}{\varepsilon} \right) |\calG\setminus H| \end{align*} yields $$t |\scrA| \leq |H| + \left( \frac{d\tth}{\varepsilon^2}(\varepsilon + \nu+ 2) + \alpha \right) (|\calG| - |H|)$$ with $\alpha = \frac{ds}{\varepsilon^2|\scrA|} + \frac{2dr}{\varepsilon |\scrA|} + \frac{ds}{\varepsilon |\scrA|}$. Proposition~\ref{Prop:AExists}(1) implies \begin{align*} \left(\frac{1}{2+ \tth + \frac{\nu\tth}{\varepsilon} +\frac{s}{|\scrA|}}\right) |\calG| & = \left(\frac{t}{2+ \tth + \frac{\nu\tth}{\varepsilon} + \frac{s}{|\scrA|}}\right) |V| \\ &\leq \left( \frac{d\tth}{\varepsilon^2}(\varepsilon + \nu+ 2) + \alpha \right)|\calG| + \left(1 - \frac{d\tth}{\varepsilon^2}(\varepsilon + \nu+ 2) - \alpha \right) |H|. \end{align*} Now we show that $H$ is a subgroup of $\calG$ of index two. To establish this fact, we use \[\frac 13 \left(1 - \frac{d\tth}{\varepsilon^2}(\varepsilon + \nu+ 2) - \alpha \right) < \left(\frac{1}{2+ \tth + \frac{\nu\tth}{\varepsilon}+ \frac{s}{|\scrA|}}\right) - \frac{d\tth}{\varepsilon^2}(\varepsilon + \nu+ 2) - \alpha,\] equivalently, $$\left(2 + \tth + \frac{\nu\tth}{\varepsilon} +\frac{s}{|\scrA|}\right) \left( 1 + \frac{2d\tth}{\varepsilon^2}(\varepsilon + \nu+ 2) + 2\alpha \right) < 3.$$ Since $\tth\leq \frac{\varepsilon^{2}}{2x d}$ holds with $x= 15$, it follows that \begin{align*} & \left(2 + \tth + \frac{\nu\tth}{\varepsilon} + \frac{s}{|\scrA|}\right) \left( 1 + \frac{2d\tth}{\varepsilon^2}(\varepsilon + \nu+ 2) + 2\alpha \right)\\ & \leq \left(2 + \frac{\tth}{\varepsilon} (\nu + \varepsilon) + \frac{s}{|\scrA|}\right) \left( 1 + \frac{2d\tth}{\varepsilon^2}(\varepsilon + \nu+ 2) + \frac{2ds}{\varepsilon^2|\scrA|} + \frac{4dr}{\varepsilon |\scrA| } + \frac{2ds}{\varepsilon |\scrA|} \right)\\ & \leq \left(2 + \frac{\tth}{\varepsilon} (2\nu -1) + \frac{s}{|\scrA|} \right) \left( 1 + \frac{2d\tth}{\varepsilon^2}(2\nu+ 1) + \frac{2ds}{\varepsilon^2|\scrA|} + \frac{4dr}{\varepsilon |\scrA|} + \frac{2ds}{\varepsilon |\scrA|} \right)\\ & < \left(2 + \frac{(\nu-1)(2\nu -1)}{2xd} +\frac{1}{108} \right) \left( 1 + \frac{2\nu+ 1}{x}+ \frac 1{27}\right)\\ & \leq \begin{cases} \left(2 + \frac 3{4x}+ \frac{1}{108}\right) \left( 1 + \frac{5}{x}+ \frac 1{27}\right) & \text{ if } d = 2, \\ \left(2 + \frac 1{x} + \frac{1}{108}\right) \left( 1 + \frac{6}{x}+ \frac 1{27}\right) & \text{ if } d \geq 3, \end{cases}\\ & < 3. \end{align*} This proves the claim that $H$ is a subgroup of $\calG$ of index two. Since no index two subgroup of $\calG$ acts transitively on $V$, the action of $H$ on $V$ has at least two distinct orbits. Since the action of $\calG$ on $V$ is transitive, the action of $H$ on $V$ has exactly two orbits. Denote the orbits of the action of $H$ on $V$ by $\calO_1, \calO_2$. Now we use Fre\u{\i}man's technique~\cite{FreimanGroupsInverseProb} to conclude the proof. For any $g\in G \setminus H$ and for any subsets $B, C$ of $V$ contained in $\calO_1$, $\calO_2$ (in some order), the map $B\cap g^\mo C \to B\times C$, sending $x\mapsto (x, gx)$, induces a map $\varphi: \coprod _{g\in H^c} B\cap g^\mo C \to B\times C$. If $B \times C$ is nonempty, then each fibre of this map contains exactly $t$ elements and hence $$ |B\times C| = |im(\varphi)| = \sum_{x\in im(\varphi) } \frac{|\varphi^\mo (x)|} {|\varphi^\mo (x)|} = \frac 1 t \sum_{x\in im(\varphi)} |\varphi^\mo (x)| = \frac 1 t \sum_{g\in H^c} |B\cap g^\mo C|.$$ Note that $|B\times C| = \frac 1 t \sum_{g\in H^c} |B\cap g^\mo C|$ holds even if $B \times C = \emptyset$. For any $g\in H^c$, we have \begin{align*} \scrA\cap g^\mo \scrA & = ((\scrA\cap \calO_1) \cup (\scrA\cap \calO_2)) \cap (g^\mo ((\scrA\cap \calO_1) \cup (\scrA\cap \calO_2)))\\ & = ((\scrA\cap \calO_1) \cap (g^\mo (\scrA\cap \calO_2)) \cup ((\scrA\cap \calO_2) \cap (g^\mo (\scrA\cap \calO_1)), \end{align*} which implies \begin{align*} & |\scrA \cap \calO_1| |\scrA\cap \calO_2|\\ & = \frac 12 |\scrA \cap \calO_1| |\scrA\cap \calO_2| + \frac 12 |\scrA \cap \calO_2| |\scrA\cap \calO_1|\\ & = \frac 1 {2t} \sum_{g\in H^c} |(\scrA \cap \calO_1) \cap g^\mo (\scrA \cap \calO_2)| + \frac 1{2 t} \sum_{g\in H^c} |(\scrA \cap \calO_2) \cap g^\mo (\scrA \cap \calO_1)| \\ & = \frac 1 {2t} \sum_{g\in H^c} |\scrA \cap g^\mo \scrA|\\ & \leq \frac 1 {2t} \left( \frac{d \tth}{\varepsilon^2} (\varepsilon + \nu + 2)|\scrA| + \frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon + \frac{ds}{\varepsilon} \right)|H|\\ & = \frac 1 {2t} \left( \frac{d \tth}{\varepsilon^2} (\varepsilon + \nu + 2)|\scrA| +\frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon + \frac{ds}{\varepsilon} \right) \frac{t|V|}2\\ & \leq \frac{d \tth}{\varepsilon^2} (\varepsilon + \nu + 2) \frac{|V|^2}8 + \left(\frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon + \frac{ds}{\varepsilon} \right) \frac{|V|}4. \end{align*} So, the orbit $\calO$ of some element of $V$ under the action of $H$ satisfies $$ |\scrA\cap \calO^c| \leq \sqrt{\frac{d\tth}{8\varepsilon^2} (\varepsilon + \nu + 2) + \left(\frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon + \frac{ds}{\varepsilon} \right) \frac{1}{4|V|} }|V|.$$ If the inequalities $\tth< \frac{\varepsilon^{2}}{2x d^{1 + 2\delta}}$ and $ \frac{ d^{1 + 2\delta} s}{\varepsilon^2 } + \frac{ d^{1 + 2\delta} r}{\varepsilon } + \frac{d^{1 + 2\delta} s}{\varepsilon}\leq \frac{|\scrA|}{108}$ hold with $\delta \in \{0, 1\}$, then for any $1\leq i \leq d$, \begin{align*} &|\theta_i(\calO)\cap \calO |\\ & = |\theta_i(\calO\cap \scrA) \cap \calO| + |\theta_i(\calO\setminus \scrA) \cap \calO|\\ & \leq |\theta_i(\scrA) \cap \calO| + |\calO\setminus \scrA|\\ & = |\theta_i(\scrA) \cap (\calO\cap \scrA) | + |\theta_i(\calO\cap \scrA) \cap (\calO\setminus \scrA) | + |\calO\setminus \scrA|\\ & \leq |\theta_i(\scrA) \cap \scrA| + 2|\calO\setminus \scrA|\\ & = |\theta_i(\scrA) \cap \scrA| + 2|\calO| - 2|\calO\cap \scrA|\\ & = |\theta_i(\scrA) \cap \scrA| + |V| - 2|\scrA| + 2|\scrA\cap \calO^c|\\ & \leq s + |\calN(\scrA) \cap \scrA| + s + \left(2 + \tth + \frac{\nu\tth}{\varepsilon}\right)|\scrA|- 2|\scrA| + 2|\scrA\cap \calO^c|\\ & \leq 2s + \frac \tth\varepsilon |\scrA| + \left( \tth + \frac{\nu\tth}{\varepsilon}\right)|\scrA| + 2\sqrt{\frac{d\tth}{8\varepsilon^2} (\varepsilon + \nu + 2) + \left(\frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon + \frac{ds}{\varepsilon} \right) \frac{1}{4|V|} }|V| \\ & \leq 2s + \left(\frac \tth\varepsilon (\nu+1 + \varepsilon) + \sqrt{\frac{2d\tth}{\varepsilon^2} (\varepsilon + \nu + 2) +\left(\frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon + \frac{ds}{\varepsilon} \right) \frac{4}{|V|} }\right) \frac{|V|}{2} \\ & \leq 2s + \left(\frac {2\nu\tth}\varepsilon + \sqrt{\frac{2d\tth}{\varepsilon^2} (2\nu + 1) +\left(\frac{ds}{\varepsilon^2} + \frac{2dr}\varepsilon + \frac{ds}{\varepsilon} \right) \frac{4}{|V|} }\right) \frac{|V|}{2} \\ & \leq \frac{\varepsilon^2}{d^{1 + 2\delta}} \frac{|\scrA|}{54} + \left(\frac {\nu\varepsilon}{xd^{1 + 2\delta}} + \frac 1 {d^{\delta}}\sqrt{\frac{ 2\nu + 1 }{x} + \frac{4}{108} }\right) \frac{|V|}{2} \\ & \leq \frac{(\nu -1)^2}{d^{1 + 2\delta}} \frac{|V|}{108} + \left(\frac {\nu(\nu -1)}{xd^{1 + 2\delta}} + \frac 1 {d^{\delta}}\sqrt{\frac{ 2\nu + 1 }{x} + \frac{4}{108} }\right) \frac{|V|}{2} \\ & \leq \left(\frac{(\nu -1)^2}{54 d^{1 + 2\delta}} + \frac {\nu(\nu -1)}{xd^{1 + 2\delta}} + \frac 1 {d^{\delta}}\sqrt{\frac{ 2\nu + 1 }{x} + \frac{4}{108} }\right) \frac{|V|}{2} \\ & \leq \left(\frac{(\nu -1)^2}{54 d} + \frac {\nu(\nu -1)}{xd} + \sqrt{\frac{ 2\nu + 1 }{x} + \frac{4}{108} }\right) \frac{|V|}{2d^{\delta}} \\ & \leq \begin{cases} \left(\frac 1{108}+ \frac {1}{x} + \sqrt{\frac{ 5 }{x} + \frac{4}{108} }\right) \frac{|V|}{2 d^{\delta}} & \text{ if } d =2, \\ \left(\frac 1{72} + \frac {5}{4x} + \sqrt{\frac{6}{x} + \frac{4}{108} }\right) \frac{|V|}{2 d^{\delta}} & \text{ if } d \geq 3, \end{cases} \\ & < \begin{cases} \frac{|V|}{2d^{\delta}} & \text{ if } x \geq 9, \\ \frac{|V|}{4d^{\delta}} & \text{ if } x \geq 36. \end{cases} \end{align*} So, under the hypothesis of each of statements (1), (2), (3), it follows that $$ |\theta_i(\calO)\cap \calO| < \frac{|V|}{2\mu} $$ for any $1\leq i \leq d$. Suppose two vertices $u, v$ of $\calO^\dag$ are adjacent in $(V, \widetilde E)$ where $\calO^\dag$ is one of $\calO, \calO^c = V \setminus \calO$. Let $H^\dag$ denote $H$ (resp. $H^c = \calG \setminus H$) if $\calO^\dag = \calO$ (resp.~$\calO^\dag = \calO^c$). Note that $\calO = H^\dag u = H^\dag v$. Using Equation~\eqref{Eqn:muBdd}, we obtain that $ |\theta_i(\calO)\cap \calO| = |\theta_i(H^\dag v) \cap H^\dag u | \geq \frac{|V|}{2\mu} $ for some $1\leq i \leq d$. It follows that $\calO$ and $\calO^c$ are independent subsets of $(V, \widetilde E)$, implying that $(V, \widetilde E)$ is bipartite, which in turn shows that $(V, E)$ is bipartite, contradicting the hypothesis. So, the vertex-Cheeger constant of the graph $(V, E)^2$ satisfies the claimed bounds. \end{proof} \begin{definition} \label{Defn:NearlyVertexTra} The graph $(V, \widetilde E)$ is said to be \textnormal{nearly vertex-transitive under a group}~$\calG$ if $\calG$ acts transitively on $V$ from the left, no index two subgroup of $\calG$ acts transitively on $V$, the set $ \widetilde \calN (\widetilde \calN(g(\scrA)))$ is contained in $g(\widetilde \calN(\widetilde \calN(\scrA))) $ for any $g\in \calG$, and for each~$\theta_i, 1\leq i\leq d$ and $v\in V$, there is an automorphism or an anti-automorphism $\psi_{i,v}$ of the group $\calG$ such that one of $$\theta_i(g\cdot v) = \psi_{i,v}(g) \cdot \theta_i(v), \quad \theta_i(g\cdot v) = \psi_{i, v}(g^\mo) \cdot \theta_i(v)$$ holds for any $g\in \calG$. In this situation, we say that $(V, \widetilde E)$ is \textnormal{nearly vertex-transitive under $\calG$ with respect to} $\{\psi_{i,v}\}$. \end{definition} It is worth considering nearly vertex-transitive graphs. We refer to Remark~\ref{Rk:NearlyVertexTra}. \begin{proposition} \label{Prop:Mu12d} \quad \begin{enumerate} \item If $(V, \widetilde E)$ is nearly vertex-transitive under $\calG$, then for any subgroup $H$ of $\calG$ of index two and $v\in V$, Equation~\eqref{Eqn:muBdd} holds for $\mu = 2$. \item If $(V, \widetilde E)$ is nearly vertex-transitive under $\calG$ with respect to $\{\psi_{i,v}\}$, and $\psi_{i, v}$ sends any index two subgroup of $\calG$ to itself, then for any subgroup $H$ of $\calG$ of index two and $v\in V$, Equation~\eqref{Eqn:muBdd} holds for $\mu = 1$. \item If $(V, \widetilde E)$ is vertex-transitive, then for any index two subgroup $H$ of any transitive subgroup $\calG$ of the automorphism group of $(V, \widetilde E)$ and $v\in V$, Equation~\eqref{Eqn:muBdd} holds for $\mu = d$. \end{enumerate} \end{proposition} \begin{proof} Note that for any two subgroups $H_1, H_2$ of $\calG$ of index two, the inequalities $|H_1\cap H_2| \geq \frac{|H_1|}{2}, |H_1^c\cap H_2^c| \geq \frac{|H_1|}{2}$ hold. A proof of it can be found in~\cite{CheegerTwisted}. Suppose $(V, \widetilde E)$ is nearly vertex-transitive under $\calG$. Let $H$ be an index two subgroup of $\calG$ and let $H^\dag$ denote one of $H, H^c$. For any $u,v\in V$ with $u = \theta_i(v)$, \begin{align*} |\theta_i(H^\dag v) \cap H^\dag u| & = |\psi_{i,v} (H^\dag) \theta_i(v) \cap H^\dag \theta_i(v)|\\ & \geq |(\psi_{i,v} (H^\dag) \cap H^\dag) \theta_i(v)| \\ & \geq \frac{|\psi_{i,v} (H^\dag) \cap H^\dag|}{t} \\ & \geq \frac{|H|}{2t} \\ &= \frac{|V|}{4} \end{align*} holds for any $1\leq i \leq d$. So, Equation~\eqref{Eqn:muBdd} holds for $\mu = 2$. This proves statement~(1). Moreover, if $\psi_{i, v}$ fixes any index two subgroup of $\calG$, then $$ |\theta_i(H^\dag v) \cap H^\dag u| \geq \frac{|\psi_{i,v} (H^\dag) \cap H^\dag|}{t} \geq \frac{|H|}{t} = \frac{|V|}{2} $$ holds for any $1\leq i \leq d$, and hence Equation~\eqref{Eqn:muBdd} holds for $\mu = 1$. This proves statement~(2). Note that for a vertex $v \in V$ and an automorphism $g$ of $(V, \widetilde E)$, the image of a neighbour of $v$ under $g^\mo$, is a neighbour of $g^\mo (v)$, and hence the neighbour $g^\mo (\theta_j(v))$ of $g^\mo(v)$ is equal to $\theta_{i_{g, v, j}} (g^\mo(v))$ for some $1\leq i_{g, v, j} \leq d$. Consequently, for any automorphism $g$ of the graph $(V, \widetilde E)$, and $v\in V$ and $1\leq j \leq d$, \[\theta_{i_{g, v, j}} (g^\mo (v)) = g^\mo (\theta_j(v))\] holds for some $1\leq i_{g, v, j} \leq d$. Suppose $\calG$ is a transitive subgroup of the automorphism group of $(V, \widetilde E)$. Let $H$ be an index two subgroup of $\calG$ and let $H^\dag$ denote one of $H, H^c$. Let $u,v$ be elements of~$V$ with $u = \theta_j(v)$. Consider the map $$\psi_{v, j} : H^\dag \to \{1, 2, \ldots, d\},\quad g \mapsto i_{g, v, j}.$$ Note that a fibre of this map having maximal size contains at least $\frac {|H^\dag|}d = \frac{|H|}d$ elements, and hence for some integer $1\leq i \leq d$, the inequality $|H^\ddag |\geq \frac {|H^\dag|}d$ holds where $H^\ddag = \psi_{v, j}^\mo(i)$. Thus, for any $g\in H^\ddag$, it follows that $i_{g, v, j} = \psi_{v, j}(g) = i$, which yields \[\theta_i(g^\mo(v)) = g^\mo (\theta_j (v)) .\] This implies that \begin{align*} |\theta_{i} (H^\dag v) \cap H^\dag u| & = |\{\theta_{i}(h^\mo v) \,|\, h\in H^\dag\}\cap H^\dag u|\\ & \geq |\{\theta_{i}(h^\mo v) \,|\, h\in H^\ddag\}\cap H^\dag u|\\ & \geq |\{h^\mo (\theta_j(v)) \,|\, h\in H^\ddag\}\cap H^\dag u|\\ & = |\{h^\mo (u) \,|\, h\in H^\ddag\}\cap H^\dag u|\\ & = |\{h^\mo (u) \,|\, h\in H^\ddag\}|\\ & \geq \frac{|H^\ddag|}{t} \\ & \geq \frac{|H|}{dt}\\ & = \frac{|V|}{2d} \end{align*} hold. So, Equation~\eqref{Eqn:muBdd} holds for $\mu = d$. \end{proof} \begin{theorem}\label{Thm:SpannSubgraVertexTra} \quad \begin{enumerate} \item If $(V, \widetilde E)$ is nearly vertex-transitive under $\calG$ with respect to $\{\psi_{i,v}\}$, and $\psi_{i, v}$ sends any index two subgroup of $\calG$ to itself, and $$ |V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d} \right) \left( \frac{ds}{\varepsilon^2} + \frac{dr}\varepsilon +\frac{ds}{\varepsilon}\right) + s $$ holds, then the vertex-Cheeger constant of the graph $(V, E)^2$ is greater than~$\frac{\varepsilon^{2}}{30d}$. \item If $(V, \widetilde E)$ is nearly vertex-transitive under $\calG$ and $$ |V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {72d} \right) \left( \frac{ds}{\varepsilon^2} + \frac{dr}\varepsilon +\frac{ds}{\varepsilon}\right) + s $$ holds, then the vertex-Cheeger constant of the graph $(V, E)^2$ is greater than~$\frac{\varepsilon^{2}}{72d}$. \item If $(V, \widetilde E)$ is vertex-transitive and $$ |V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d^3} \right) \left( \frac{d^3s}{\varepsilon^2} + \frac{d^3r}\varepsilon+ \frac{d^{3}s}{\varepsilon}\right) + s $$ holds, then the vertex-Cheeger constant of the graph $(V, E)^2$ is greater than~$ \frac{\varepsilon^{2}}{30d^3}$. \end{enumerate} \end{theorem} \begin{proof} This follows from Theorem~\ref{Thm:AlmostGraphAut}, Proposition~\ref{Prop:Mu12d}. \end{proof} \begin{remark} \label{Rk:NearlyVertexTra} The consideration of nearly vertex-transitive graphs may appear superfluous because a significant number of important graphs are vertex-transitive, being Cayley graphs. However, there are several reasons for studying them. First, the lower bound obtained for nearly vertex-transitive graphs through our method is stronger than the bound that our method yields for vertex-transitive graphs. Next, there are graphs of group-theoretic origin, other than Cayley graphs, which may fail to be vertex-transitive, for instance, Cayley sum graphs. Moreover, the class of nearly vertex-transitive graphs includes Cayley graphs, Cayley sum graphs, along with generalised Cayley graphs introduced by Maru\v{s}i\v{c}, Scapellato and Zagaglia Salvi~\cite{MarusicScapellatoZagagliaSalviGeneralizedCayleyGraph}, and twisted Cayley graphs and twisted Cayley sum graphs studied by the authors~\cite{CheegerTwisted}. Thus, the class of nearly vertex-transitive graphs includes plenty of graphs of interest and for this class, the lower bound obtained is stronger than the bound obtained for vertex-transitive graphs in general. \end{remark} \section{Bounds on the smallest eigenvalue of regular graphs} Let $-1+\lambda$ denote the smallest eigenvalue of a $d$-regular, non-bipartite graph $\Gamma$. Since~$\Gamma$ is non-bipartite, it follows that $\lambda \neq 0$. So, the second largest eigenvalue of the normalised adjacency operator of $\Gamma^2$ is $\geq (1- \lambda)^2$. This implies that the smallest nontrivial eigenvalue of the normalised Laplacian operator of $\Gamma^2$ is $\leq 1 - (1-\lambda)^2$. By the discrete Cheeger--Buser inequality~\cite[Theorem 2.2]{ChungSpectralGraphTheory}, it follows that the edge-Cheeger constant of $\Gamma^2$ is $\leq \sqrt {2 (1 - (1-\lambda)^2)} < 2\sqrt \lambda$. Hence, if the vertex-Cheeger constant of $\Gamma^2$ is $\geq \varpi$, then the inequality $2 \sqrt \lambda > \frac{\varpi}{d^2}$ holds, and hence the smallest eigenvalue of $\Gamma$ is $> -1 + \frac {\varpi^2}{4d^4}$. The above discussion, combined with Theorem~\ref{Thm:SpannSubgraVertexTra}, yields the following. \begin{proposition} \label{Cor:AlmostGraphAut} Suppose $(V, E)$ is regular and it is nearly vertex-transitive under~$\calG$. Then the smallest eigenvalue of the normalised adjacency operator of $(V, E)$ is greater than $-1+ \frac {\varepsilon^4}{2^{8}3^{4}d^6}$. Assume in addition that $(V, E)$ is nearly vertex-transitive under $\calG$ with respect to $\{\psi_{i,v}\}$ and $\psi_{i, v}$ sends any index two subgroup of $\calG$ to itself. Then the smallest eigenvalue of the normalised adjacency operator of $(V, E)$ is greater than $ -1+\frac {\varepsilon^4}{60^2 d^6}$. \end{proposition} \begin{proposition} \label{Cor:SpannSubgraVertexTra} If $(V, E)$ is vertex-transitive, then the smallest eigenvalue of its normalised adjacency operator is greater than $ -1+\frac {\varepsilon^4}{60^2 d^{10}}$. \end{proposition} \section{Bounds on the smallest eigenvalue of irregular graphs} Without any assumption on the regularity of $(V, E)$, one obtains the following results, which deals with a more general set-up, and under suitable hypotheses, obtains bounds similar to those of Propositions~\ref{Cor:AlmostGraphAut} and~\ref{Cor:SpannSubgraVertexTra}. \begin{proposition}\label{Prop:SpannSubgraVertexTraEigenBdd} \quad \begin{enumerate} \item If $(V, \widetilde E)$ is nearly vertex-transitive and $$ |V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {72d} \right) \left( \frac{ds}{\varepsilon^2} + \frac{dr}\varepsilon +\frac{ds}{\varepsilon}\right) + s .$$ then the smallest eigenvalue of the adjacency operator of $(V, E)$ is greater than~$ d (-1 + \frac{\varepsilon^4 }{2^{8}3^{4} d^{6}}) $. \item If $(V, \widetilde E)$ is nearly vertex-transitive under $\calG$ with respect to $\{\psi_{i,v}\}$, and $\psi_{i, v}$ sends any index two subgroup of $\calG$ to itself, and $$ |V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d} \right) \left( \frac{ds}{\varepsilon^2} + \frac{dr}\varepsilon + \frac{ds}{\varepsilon}\right) + s , $$ then the smallest eigenvalue of the adjacency operator of $(V, E)$ is greater than~$ d (-1 + \frac{\varepsilon^4 }{60^2 d^{6}}) $. \item If $(V, \widetilde E)$ is vertex-transitive, and $$ |V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d^3} \right) \left( \frac{d^3s}{\varepsilon^2} + \frac{d^3r}\varepsilon+ \frac{d^{3}s}{\varepsilon}\right) + s $$ then the smallest eigenvalue of the adjacency operator of $(V, E)$ is greater than~$ d (-1 + \frac{\varepsilon^4 }{60^2 d^{10}}) $. \end{enumerate} \end{proposition} \begin{proof} By Theorem~\ref{Thm:SpannSubgraVertexTra}, it suffices to show that the smallest eigenvalue of the adjacency operator $A$ of $(V, E)$ is greater than or equal to $ -d \left( 1 - \frac{\tth^2}{4d^4} \right)$. For an $n\times n$ Hermitian matrix $M$, let $\lambda_1(M)$ (resp. $\lambda_2(M), \lambda_{n-1}(M), \lambda_n(M)$) denote its largest (resp. second largest, second smallest, smallest) eigenvalue. By the Courant--Weyl inequality~\cite[Theorem 2.8.1]{BrouwerHaemersSpectraofGraphs}, we obtain $$\lambda_1(T) = \lambda_1(A^2 + T - A^2) \geq \lambda_2(A^2) + \lambda_{n-1}(T - A^2) $$ where $T = T_{(V, E)^2}$ denotes the diagonal matrix consisting of the degrees of the vertices of $(V, E)^2$. By~\cite[pp. 34--35]{ChungSpectralGraphTheory}, $$ \lambda_{n-1}(T - A^2) \geq \frac {\tth'^2}{2D} \geq \frac {\tth^2}{2D},$$ where $D$ denotes the maximum degree of $(V, E)^2$ and $\tth'$ denotes the isoperimetric number\footnote{We refer to~\cite[p. 34]{ChungSpectralGraphTheory} for the notion of isoperimetric number of a graph.} of $(V, E)^2$. It follows that $$\lambda_2(A^2) \leq \lambda_1(T) - \frac {\tth^2}{2D} \leq \lambda_1(T) - \frac {\tth^2}{2d^2} \leq d^2- \frac {\tth^2}{2d^2}. $$ Since $(V, E)$ is non-bipartite, by~\cite[Theorems 31.11, 31.12]{vanLintWilsonCourseCombi}, it follows that the smallest eigenvalue $\lambda_n(A)$ of $A$ and the largest eigenvalue $\lambda_1(A)$ of $A$ have distinct absolute values, and hence $\lambda_n(A)^2\neq \lambda_1(A)^2 = \lambda_1(A^2)$. This implies that the smallest eigenvalue of $A$ satisfies $\lambda_n(A)^2 \leq \lambda_2(A^2)$, and this yields $$\lambda_n(A) \geq -\sqrt{\lambda_2(A^2)} \geq -\sqrt{ d^2 - \frac {\tth^2}{2d^2} } = -d \left(1 - \frac {\tth^2}{2d^4} \right)^{1/2} \geq -d \left(1 - \frac {\tth^2}{4d^4} \right) ,$$ as required. \end{proof} For any finite, undirected, non-bipartite, vertex-transitive graph, Proposition~\ref{Prop:SpannSubgraVertexTraEigenBdd} establishes an explicit lower bound for the smallest eigenvalue of its normalised adjacency operator, which depends on the graph only through its degree and its vertex-Cheeger constant. From~\cite{CheegerTwisted}, it is known that there are non-vertex-transitive graphs possessing the same property. One may hope to obtain irregular graphs exhibiting this property. It seems that such a result can be deduced from Theorems~\ref{Thm:AlmostGraphAut} and~\ref{Thm:SpannSubgraVertexTra}. Indeed, we could begin with a vertex-transitive graph $(V, \widetilde E)$ and remove few edges to obtain an irregular graph $(V, E)$. However, to be able to apply Theorems~\ref{Thm:AlmostGraphAut} and~\ref{Thm:SpannSubgraVertexTra}, we need to prove that $|V|$ is large enough in terms of $d$, the number of removed edges and the vertex-Cheeger constant of $(V, E)$. The difficulty remains in estimating the vertex-Cheeger constant of $(V, E)$ in order to obtain a lower bound on the number of vertices in terms of the degree and the number of removed edges that ensures a lower bound on the smallest eigenvalue on the adjacency operator through an application of Proposition~\ref{Prop:SpannSubgraVertexTraEigenBdd}. \medskip \begin{theorem} \label{Thm:Irregular} \quad \begin{enumerate} \item If $(V, \widetilde E)$ is nearly vertex-transitive, no index two subgroup of $\calG$ acts transitively on $V$ and $\psi_{i, v}$ sends any index two subgroup of $\calG$ to itself, and $$ |V| \geq 224 \left( \frac{4d^2 }{\widetilde h^2} + \frac{2d^2 + 2}{\widetilde h}\right)dr + d^{2}r , \quad r \leq \frac{(d'+1)\widetilde h}4, \quad d \geq 3, $$ then the smallest eigenvalue of $A$ is greater than $d \left(-1 + \frac{h^4 }{60^2 d^{6}}\right) $, and the largest eigenvalue of $L_{(V, E)}$ is less than $d \left(2 - \frac{h^4 }{60^2 d^{6}}\right) $. \item If $(V, \widetilde E)$ is vertex-transitive, and $$ |V| \geq 217 \left( \frac{4d^2 }{\widetilde h^2} + \frac{2d^2 + 2}{\widetilde h}\right)d^3 r + d^2r, \quad r \leq \frac{(d'+1)\widetilde h}4, \quad d \geq 3, $$ then the smallest eigenvalue of $A$ is greater than $ d \left(-1 + \frac{h^4 }{60^2 d^{10}}\right) $, and the largest eigenvalue of $L_{(V, E)}$ is less than $d \left(2 - \frac{h^4 }{60^2 d^{10}}\right) $. \end{enumerate} \end{theorem} \begin{proof} Note that if $\Gamma$ is a finite, undirected graph with minimum degree $d_{\min}$ and vertex-Cheeger constant at most $1$, and if $X$ is a subset of the set of vertices of~$\Gamma$ where the vertex-Cheeger constant is attained, then $X$ contains at least $\frac {d_{\min}+1}{2}$ elements. Indeed, one has $$1\geq \frac{|\partial X|}{|X|} \geq \frac{d_{\min} -(|X|-1)}{|X|}, $$ which implies that $|X| \geq \frac{d_{\min}+1}{2}$. This shows that if $X$ is a subset of $V$ where the vertex-Cheeger $h$ constant of $(V, E)$ is attained, then $$ h = \frac{|\calN( X)\setminus X|}{|X|} \geq \frac {|\widetilde \calN( X)\setminus X| - r }{|X|} \geq \widetilde h - \frac{r}{|X|} \geq \widetilde h - \frac{2r}{d'+1} \geq \frac{\widetilde h}2 . $$ Note that $$ 224 \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d} \right) , \quad 217 \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d^3} \right) $$ for $d\geq 3$, and $$ \left(\frac{4d^2}{\widetilde h^2} + \frac{2d^2 + 2}{\widetilde h}\right)r \geq \frac{d^2r}{h^2} + \frac{(d^2 + 1)r}h \geq \frac{s}{h^2} + \frac{r}h + \frac{s}{h}. $$ So, under the hypothesis of part (1), we obtain $$|V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d} \right) \left( \frac{ds}{h^2} + \frac{dr}h + \frac{ds}{h}\right) + s,$$ and by Proposition~\ref{Prop:SpannSubgraVertexTraEigenBdd}(2), it follows that the smallest eigenvalue of $A$ is greater than $d \left(-1 + \frac{h^4 }{60^2 d^{6}}\right) $. Moreover, under the hypothesis of part (2), we obtain $$|V| \geq 108 \left( 2 + \frac {(\nu-1)(2\nu -1)} {30d^3} \right) \left( \frac{d^3s}{h^2} + \frac{d^3r}h + \frac{d^{3}s}{h}\right) + s,$$ and by Proposition~\ref{Prop:SpannSubgraVertexTraEigenBdd}(3), it follows that the smallest eigenvalue of $A$ is greater than $d \left(-1 + \frac{h^4 }{60^2 d^{10}}\right)$. For an $n\times n$ Hermitian matrix $M$, let $\lambda_1(M)$ (resp. $\lambda_n(M)$) denote its largest (resp. smallest) eigenvalue. By the Courant--Weyl inequality~\cite[Theorem 2.8.1]{BrouwerHaemersSpectraofGraphs}, we obtain $$ d \geq \lambda_1(T_{(V, E)}) = \lambda_1( A + L_{(V, E)}) \geq \lambda_n(A) + \lambda_1(L_{(V, E)}) .$$ Using the lower bound on $\lambda_n(A)$, the result follows. \end{proof} By the discrete Cheeger--Buser inequality, the vertex-Cheeger constant of a Ramanujan graph of degree $d$ is at least $\frac{d - 2\sqrt{d-1} }{2d} $. Thus, we obtain the following corollary of Theorem~\ref{Thm:Irregular}. \begin{corollary} \label{Thm:IrregularRama} Assume that $(V, \widetilde E)$ is a Ramanujan graph. \begin{enumerate} \item If $(V, \widetilde E)$ is nearly vertex-transitive, no index two subgroup of $\calG$ acts transitively on $V$ and $\psi_{i, v}$ sends any index two subgroup of $\calG$ to itself, and $$ |V| \geq 224 \left( \frac{16 d^4}{(d - 2 \sqrt {d-1})^2} + \frac{4d^3+ 4d}{d - 2 \sqrt {d-1}} \right) dr + d^{2}r , \quad r \leq \frac{(d'+1)\widetilde h}4, \quad d \geq 3, $$ then the smallest eigenvalue of $A$ is greater than $ d \left(-1 + \frac{h^4 }{60^2 d^{6}}\right) $, and the largest eigenvalue of $L_{(V, E)}$ is less than $d \left(2 - \frac{h^4 }{60^2 d^{6}}\right) $. \item If $(V, \widetilde E)$ is vertex-transitive, and $$ |V| \geq 217 \left( \frac{16 d^4}{(d - 2 \sqrt {d-1})^2} + \frac{4d^3 + 4d}{d - 2 \sqrt {d-1}}\right) d^3 r + d^{2}r , \quad r \leq \frac{(d'+1)\widetilde h}4, \quad d \geq 3, $$ then the smallest eigenvalue of $A$ is greater than $d \left(-1 + \frac{h^4 }{60^2 d^{10}}\right) $, and the largest eigenvalue of $L_{(V, E)}$ is less than $d \left(2 - \frac{h^4 }{60^2 d^{10}}\right) $. \end{enumerate} \end{corollary} Corollary~\ref{Thm:IrregularRama} has interesting applications to spanning subgraphs of existing explicit constructions of Ramanujan graphs. Lubotzky, Phillips and Sarnak~\cite{LPS88Ramanujan} and Margulis~\cite{Margulis88ExpandConcent} constructed arbitrarily large $(p+1)$-regular Ramanujan graphs when $p$ is an odd prime. Chiu~\cite{ChiuCubicRamanujan} constructed $3$-regular Ramanujan graphs. Further, Morgenstern~\cite{MorgensternJCTB94} proved that there are arbitrarily large $d$-regular Ramanujan graphs when $d-1$ is a prime power. These graphs are Cayley graphs, and hence are nearly vertex-transitive. By removing a small number of edges from any one of these graphs and applying Corollary~\ref{Thm:IrregularRama}(1), we obtain examples of irregular graphs whose normalised adjacency operators have their smallest eigenvalues bounded uniformly away from~$-1$. \longthanks{ We thank the anonymous reviewers and the editor for the constructive comments and suggestions. The work of the first author was supported by the ERC grant 716424 - CASe of Karim Adiprasito. The second author acknowledges the INSPIRE Faculty Award (IFA18-MA123) from the Department of Science and Technology, Government of India.} \bibliographystyle{mersenne-plain} \bibliography{ALCO_Biswas_680} \end{document}