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 $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. 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.

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$ (yielding $4/n^2$ on the 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|$ 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.

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: 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 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 \kappa /|V|^2$ (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 on page 38 in C.Godsil & G.Royle "Algebraic Graph Theory" book.

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 $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. 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.

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 the same question might make more sense under stronger hypothesis: graphs whose edge-connectivity is $k$, or even vertex-transitive graphs?

[The reason for the $|V|^{-2}$ is that, when the edge-connectivity is $\kappa$, there is a simple $4 \kappa /|V|^2$ lower bound on $h$...]

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: 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 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 \kappa /|V|^2$ (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 on page 38 in C.Godsil & G.Royle "Algebraic Graph Theory" book.