Bounding the cheeger constant of a cover of a graph?

116 Views Asked by At

Suppose that $G$ and $H$ are connected graphs, and that $\phi : G \to H$ is a $n$-fold covering. Let $h$ denote the Cheeger constant. I know that $h(G) \leq h(H)$.

Question: Is it also the case that $h(G) \geq h(H)/n$, or something similar

(Cycle graphs satisfy this formula, roughly.)

I suspect that there is no such formula - in that case, I would appreciate an illuminating example (e.g. something like: a family of graphs $H_n$ with $h(H_n) = c$, and $m$ fold covers $G_n \to H_n$ such that $h(G_n)/h(H_n) \to 0$).

(Note that I have required $G$ to be connected.)

If there is a formula describing expansion in covers that is easier to give through one of the other interpretations, e.g. eigenvalues or mixing time, I'd also like to see that.

Thank you!

Update: I've been told that a good example where the 2-fold cover can mix much more slowly than the base is the Ising model (under some temperature, not sure which ). In this case the stationary distribution has most of its mass on either most of the particles spinning up or most of the particles spinning down, and there is conjecturally(?) a bottleneck between them, but within the bottleneck the mixing is rapid. (In other words, you can efficiently get an almost uniform sample by running the Markov chain for a (polynomial) while, then flipping a coin to decide whether to flip the colors.) The $\mathbb{Z}/2\mathbb{Z}$ action is a covering action here. Not sure about a reference for this presently.

1

There are 1 best solutions below

0
On BEST ANSWER

We don't need to do anything as exotic as Ising models here. Just let $G$ consist of two complete graphs $K_t$ with some bridges between them:

enter image description here

In this example with $t=5$, $H$ is the graph on vertex set $\{a,b,c,d,e,f\}$ we get by forgetting the indices on the vertices of $G$; we do the same thing for general $t$.

Then $h(G) = \frac2{t+1}$ is achieved by taking the left $K_t$ and one of the bridge vertices (in the example, we can take $\{a_1, b_1, c_1, d_1, e_1, f_1\}$). However, $H$ is clique plus a vertex of degree $2$, and $h(H)$ is large: probably $\frac12$ from taking the degree-$2$ vertex.

In general, we can prove that whenever some $A \subseteq V(G)$ achieves a low $\frac{|\partial A|}{|A|}$, then $B = \phi(A) \subseteq V(H)$ will also have low $\frac{|\partial B|}{|B|}$. As above, we can run into the problem that $|B| > \frac12|V(H)|$, so that while $A$ makes $h(G)$ small, $B$ does not make $h(H)$ small. But this is essentially the only problem.