So I've been messing around with expander graphs, and since their advantage is to maintain a high 'connectivity' with a fixed degree, I wondered about their edge connectivity.
Formally, fix $k \ge 2$ and lets say we have a sequence of $c$-expander graphs $(G_n) = ((V_n,E_n))_{n\in \mathbf{N}}$ if it satisfies the followings :
- $|V_n| \longrightarrow +\infty$ as $n\rightarrow +\infty$
- $G_n$ is $k$-regular for all $n$
- there exists a constant $c>0$ such as $h(G_n) > c$ for every $n$.
where $h(G)$ is the Cheeger constant defined as $$h(G) = \min_{W\subseteq V, |W| \le \frac{|V|}{2}} \frac{|\partial W|}{|W|}$$ and $\partial W = \{y \in V\backslash W | \exists x \in W, (x,y)\in E \}$
Is there a way to uniformely have a lower bound on the sequence of the edge connexity $(\kappa(G_n))$ ? I actually have prooved $\kappa(G_n) \ge \min(k,c\cdot k)$ but that seems rather low in my opinion. Moreover the expander mixing lemma seems to give a lower bounds that tends to $-\infty$ which therefore isn't much interesting.
I have also wondered about a probabilistic approach on $2n$-expanders as there is an easy model based on permutations, and that may be easier to compute the number of indepedents path in probability, which then would give an estimate of $\kappa(G)$ thanks to Menger's theorem.
Does anyone have an idea of an approach for this question ?