3
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.