How much local is the information encoded by the isoperimetric constant of a graph?

Question

Upload: the general question has been answered in the negative. Now I am proposing a more specific question, which is actually the one that I am interested in.

I think that this is a quite natural question, but I was able neither to find anything in literature, nor to find an argument by myself.

Let $G=(V,E)$ be an infinite, locally finite, connected graph (maybe without loops and multiple edges) equipped with the shortest path metric. Given a finite subset $A$ of $V$, let $\partial A$ denote the set of vertex at distance $1$ from $A$. There are many definitions of isoperimetric constant. I am adopting the following one: $\iota(G)$ is the infimum of $\frac{|\partial A|}{|A|}$, when $A$ runs over the finite non-empty subsets of $V$.

Now, take an increasing and covering sequence $A_n$ of finite non-empty subsets of $V$ and define the number $j$ to be the infimum of the $\frac{|\partial A_n|}{|A_n|}$'s.

The general question concerned possible relations between $j$ and $\iota(G)$. In particular, I was interesting in the following

Original question: Is it possible that $\iota(G)=0$ and $j>0$?

It has trivially negative answer: take a tree with degree $\geq3$ and attach a copy of $\mathbb Z$ to one vertex.

The question that I am interested in is actually more specific. Fix a point $x$ and consider the sequence $A_0=x$, $A_1=\partial A_0$, ... $A_n=\partial A_{n-1}$. Define $j(x)$ to be the infimum of the $\frac{|\partial A_n|}{|A_{n-1}|}$'s. Let $j$ be the infimum over $x$ of the $j(x)$'s. What about the following question?

New question 1: Is it possible that there are vertex $x$ and $y$ such that $j(x)\neq j(y)$?

New question 2: Is it possible that $j=0$ and there exists $x$ such that $j(x)>0$?

Basically I am looking for some local version of the isopetric constant...

Answer 1

As far as I understand, you suppose that $\partial A$ is disjoint from $A$, and in the process you define $A_n=A_{n-1}\cup \partial A_{n-1}$,

Under these assumptions, the answer to both questions is negative.

Consider a binary tree with a root vertex $a$ (that is, $a$ has degree 1, and each other vertex has degree 3). Next, for every positive integer $d$, identify all the vertices at distance $3d$ from $a$ (obtaining a vertex $v_d$; the vertices $v_d$ are different for differet $d$). Finally, take two disjoint copies of this graph and identify their root vertices (denote the resulting vertex by $a$ again).

Now, $j=j(a)=0$ since $|\partial A_{3d-1}|=2$. On the other hand, let $b$ be one of the two neighbors of $a$. Then $|A_n|\leq 2^{n+2}$, but $|\partial A_n|\geq 2^{n-1}$, so $j(b)\geq 1/8$. Thus we have constructed a counterexample to both conjectures.

On the other hand, you may ask the same questions for a graph with a bounded degree. Then the answer to the second question is affirmative, though there still exist counterexamples to the first one.

Here is a counterexample in this case. Instead of glueing vertices, we will thin out a tree. First, take the same binary tree with a rot vertex $a$. Now, for some $n_1$ large enough, delete some vertices of the $n_1$th layer so that $|\partial A_{n_1-1}|\approx |A_{n_1-1}|/1000$ (we delete each vertex together with a subtree hanging on it). Note that now we have, say, $|\partial A_{n_1}|\geq |A_{n_1}|/800$. Next, take $n_2$ much larger than $n_1$ and thin out $n_2$th layer in the same manner, and so on. Finally, glue two copies of such tree at vertex $a$ again. The we have $j(a)=1/1000$ but $j(b)>1/1000$ if $b$ is a neighbor of $a$.

Answer 2

Of course not. It is a common misconception that the Folner condition should involve increasing or exhausting sequences of subsets. In fact, there is nothing in the amenability, strong isoperimetric or spectral gap conditions which would require any kind of monotonicity or exhaustion.

From a somewhat different angle, the point is that amenability of graphs is not inherited when passing to subgraphs. Examples are manifold. For instance take a homogeneous tree $T$ of degree $\ge 3$ and attach a geodesic ray (a copy of $\mathbb Z_+$) just to one vertex of $T$.