Reference request: maximal Cheeger constant for 3-regular graphs

Question

Given a connected graph $G$, the Cheeger constant $h(G)$ (a.k.a. Cheeger number or isoperimetric number) roughly measures the "bottleneckedness" of $G$. See Wikipedia for the precise definition.

I want to have an approximate value of the maximal Cheeger constant among all trivalent (or $3$-regular) graphs with a large fixed number of vertices, but couldn't find an answer by googling. The precise problem is:

Question: Let $\mathcal{T}_n$ denote the set of all $3$-regular graphs with $n$ vertices. How does $h_n:=\max_{G\in\mathcal{T}_n}h(G)$ behave asymptotically as $n\to+\infty$?

Any comments are appreciated!

Answer 1

This is expander territory and someone will doubtless give a reference soon.

Meanwhile, here's a simple proof that $\liminf h_n \le 1$.

Consider a connected induced subgraph $H$ with $n_1,n_2,n_3$ vertices of degree 1,2,3, respectively. Since $H$ is connected, we have $n_1+2n_2+3n_3\ge 2(n_1+n_2+n_3)-2$ (sharp for a tree); that is, $n_3\ge n_1-2$, say $n_3=n_1-2+\delta$. Also $|\partial H|\le 2n_1+n_2$, so in summary, the Cheeger constant is at most $$ \frac{2n_1+n_2}{2n_1+n_2-2+\delta}, $$ which is bounded above by $1+o(1)$ as $H$ grows in size.

I think you need a good expander graph to get a lower bound.

Also see this.

ADDED: I just realised there is a much simpler way to show that $h_n\le 1$ except for tiny $n$: Take $H$ to be a cycle.