How to construct a sequence of expander graphs with strictly decreasing Cheeger constants?

41 Views Asked by At

Let $c > 0$ be a real number. Let's say that a graph is a $c$-expander if its Cheeger constant is at least $c$. I am interested in knowing whether the following construction exists. Any references to this idea or similar ones would be appreciated.

Suppose that we start with a $c_0$-expander graph $G_0$. We would like to re-wire the edges of $G_0$ to obtain a $c_1$-expander $G_1$ that is not a $c_0$-expander. Then, we would like to re-wire the edges of $G_1$ to obtain a $c_2$-expander $G_2$ that is not a $c_1$-expander, and so on. Note that all of the graphs in this sequence should have the same number of edges and vertices, and $c_0 > c_1 > c_2 > \cdots$.

More generally, is there a way to obtain a sequence of expander graphs, with the same number of edges and vertices, which have strictly decreasing Cheeger constants?