## Return to Question

6 Typo

The combinatorial laplacian on a finite graph $G$ can be defined as $\Delta: \mathbb{C}^G \to \mathbb{C}^G$ sending the function $f:G \to \mathbb{C}$ to $(\Delta f)(v) = \sum_{v' \sim v} \big( f(v)-f(v') \big)$ where $v' \sim v$ means that $v'$ is a neighbour of $v$.

Let $\lambda_1$ be the smallest non-zero eigenvalue of $\Delta$. When the graph is $k$-regular this is $k-\mu_2(G)$ where $\mu_2(G)$ is the second largest eigenvalue of the adjacency matrix of $G$ (the largest being $k$).

Let $G$ be a finite graph with vertex set $V$ and edge set $E$. For a subsets $A,B \subset V$, let $E(A,B)$ be the set of edges joining $A$ and $B$, i.e.

$$E(A,B) = \big\lbrace \lbrace a,b \rbrace \in E \mid a \in A , b \in B \big\rbrace$$

Then the Cheeger constant of $G$, denoted $h(G)$, is defined as $$h(G) := \min \Big\lbrace \frac{|E(A,B)|}{\min(|A| \, |B|) } \quad \Big| \quad A \cup B = V, A \cap B = \emptyset \Big\rbrace$$

Results of Alon-Milman and Dodziuk give upper and lower bounds on $\lambda_1$ in terms of $h$. My concern is more with the lower bound: $$\lambda_1(G) \geq \frac{h(G)^2}{2m}$$ where $m$ is the maximal degree of $G$. Assume $G$ is connected and $k$-regular.

For a $2$-regular graph (i.e. a cycle), as $n=|V|$ gets bigger $\lambda_1$ behaves like $4 \pi^2 /n^2$ whereas $h$ behaves like $4/n$ (for even yielding $n$, almost 4/n^2$on the same for odd$n$).right-hand-side).$\textbf{Question}$: is there a sequence of connected$k$-regular graphs$G_n=(V_n,E_n)$,$k>2$such that$|V_n| \to \infty$and 1-$\lambda_1(G_n) = O(|V_n|^{-2})$? how small could the constant be? 2-$\frac{2k \lambda_1(G_n)}{h(G_n)^2} \to 1$? In some sense, what are [sequence of graphs] that are really far from being expanders? Presumably these would have bad connectivity. Thus this question should probably be asked under stronger hypothesis: graphs whose edge-connectivity is$k$, or, more interestingly, vertex-transitive graphs? PS: The reason for the$|V|^{-2}$is that, when the edge-connectivity is$\kappa$, there is a simple$2 \kappa /|V|$(for$|V|$even, almost the same for$|V|$odd) lower bound on$h$... PPS: Vertex-transitive graphs automatically have the highest possible edge-connectivity, see Lemma 3.3.3 on page 38 in C.Godsil & G.Royle "Algebraic Graph Theory" book. 5 Typos correction. # Sequence of graphs with small$\lambda_1$(the smallest nonzero eigenvalue of the a regular finite graph) The combinatorial laplacian on a finite graph$G$can be defined as$ \Delta: \mathbb{C}^G \to \mathbb{C}^G$sending the function$f:G \to \mathbb{C}$to$(\Delta f)(v) = \sum_{v' \sim v} \big( f(v)-f(v') \big)$where$v' \sim v$means that$v'$is a neighbour of$v$. Let$\lambda_1$be the smallest non-zero eigenvalue of$\Delta$. When the graph is$k$-regular this is$k-\mu_2(G)$where$\mu_2(G)$is the second largest eigenvalue of the adjacency matrix of$G$(the largest being$k$). Let$G$be a finite graph with vertex set$V$and edge set$E$. For a subsets$A,B \subset V$, let$E(A,B)$be the set of edges joining$A$and$B$, i.e. $$E(A,B) = \big\lbrace \lbrace a,b \rbrace \in E \mid a \in A , b \in B \big\rbrace$$ Then the Cheeger constant of$G$, denoted$h(G)$, is defined as $$h(G) := \min \Big\lbrace \frac{|E(A,B)|}{\min(|A| \, |B|) } \quad \Big| \quad A \cup B = V, A \cap B = \emptyset \Big\rbrace$$ Results of Alon-Milman and Dodziuk give upper and lower bounds on$\lambda_1$in terms of$h$. My concern is more with the lower bound: $$\lambda_1(G) \geq \frac{h(G)^2}{2m}$$ where$m$is the maximal degree of$G$. Assume$G$is connected and$k$-regular. For a$2$-regular graph (i.e. a cycle), as$n=|V|$gets bigger$\lambda_1$behaves like$4 \pi^2 /n^2$whereas$h$behaves like$8/n^2$4/n$ (for even $n$, almost the same for odd $n$).

$\textbf{Question}$: is there a sequence of connected $k$-regular graphs $G_n=(V_n,E_n)$, $k>2$ such that $|V_n| \to \infty$ and

1- $\lambda_1(G_n) = O(|V_n|^{-2})$? how small could the constant be?

2- $\frac{2k \lambda_1(G_n)}{h(G_n)^2} \to 1$?

In some sense, what are [sequence of graphs] that are really far from being expanders? Presumably these would have bad connectivity: when $k=3$, some elaboration on the "no perfect matching" graph (a $1$-edge-connected $3$-regular graph on $16$ vertices which does not admit a $1$-factor) answers both of the above (positively). . Thus this question should probably be asked under stronger hypothesis: graphs whose edge-connectivity is $k$, or, more interestingly, vertex-transitive graphs?

PS: The reason for the $|V|^{-2}$ is that, when the edge-connectivity is $\kappa$, there is a simple $4 2 \kappa /|V|^2$ |V|$(for$|V|$even, almost the same for$|V|$odd) lower bound on$h$... PPS: Vertex-transitive graphs automatically have the highest possible edge-connectivity, see Lemma 3.3 3.3.3 on page 38 in C.Godsil & G.Royle "Algebraic Graph Theory" book. 4 Restricted question to the interesting class of graphs, added reference for edge-connectivity of vertex-transitive graphs. The combinatorial laplacian on a finite graph$G$can be defined as$ \Delta: \mathbb{C}^G \to \mathbb{C}^G$sending the function$f:G \to \mathbb{C}$to$(\Delta f)(v) = \sum_{v' \sim v} \big( f(v)-f(v') \big)$where$v' \sim v$means that$v'$is a neighbour of$v$. Let$\lambda_1$be the smallest non-zero eigenvalue of$\Delta$. When the graph is$k$-regular this is$k-\mu_2(G)$where$\mu_2(G)$is the second largest eigenvalue of the adjacency matrix of$G$(the largest being$k$). Let$G$be a finite graph with vertex set$V$and edge set$E$. For a subsets$A,B \subset V$, let$E(A,B)$be the set of edges joining$A$and$B$, i.e. $$E(A,B) = \big\lbrace \lbrace a,b \rbrace \in E \mid a \in A , b \in B \big\rbrace$$ Then the Cheeger constant of$G$, denoted$h(G)$, is defined as $$h(G) := \min \Big\lbrace \frac{|E(A,B)|}{\min(|A| \, |B|) } \quad \Big| \quad A \cup B = V, A \cap B = \emptyset \Big\rbrace$$ Results of Alon-Milman and Dodziuk give upper and lower bounds on$\lambda_1$in terms of$h$. My concern is more with the lower bound: $$\lambda_1(G) \geq \frac{h(G)^2}{2m}$$ where is the maximal degree of$G$. Assume$G$is connected and$k$-regular. For a$2$-regular graph (i.e. a cycle), as$n=|V|$gets bigger$\lambda_1$behaves like$4 \pi^2 /n^2$whereas$h$behaves like$8/n^2$(for even$n$, almost the same for odd$n$).$\textbf{Question}$: is there a sequence of connected$k$-regular graphs$G_n=(V_n,E_n)$,$k>2$such that$|V_n| \to \infty$and 1-$\lambda_1(G_n) = O(|V_n|^{-2})$? how small could the constant be? 2-$\frac{2k \lambda_1(G_n)}{h(G_n)^2} \to 1$? In some sense, what are [sequence of graphs] that are really far from being expanders? Presumably these would have bad connectivity, so : when$k=3$, some elaboration on the same "no perfect matching" graph (a$1$-edge-connected$3$-regular graph on$16$vertices which does not admit a$1$-factor) answers both of the above (positively). Thus this question might make more sense should be asked under stronger hypothesis: graphs whose edge-connectivity is$k$, oreven , more interestingly, vertex-transitive graphs? [ PS: The reason for the$|V|^{-2}$is that, when the edge-connectivity is$\kappa$, there is a simple$4 \kappa /|V|^2$(for$|V|$even, almost the same for$|V|$odd) lower bound on$h$...]h$...

PPS: Vertex-transitive graphs automatically have the highest possible edge-connectivity, see Lemma 3.3 on page 38 in C.Godsil & G.Royle "Algebraic Graph Theory" book.

3 Corrrected a factor of 2 in the very last sentence.
2 Added the definition of $\lambda_1$ and corrected other typos
1