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

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...

-
Using these definitions, the disjoint union of an amenable graph and a non-amenable graph is amenable, giving a trivial example. – Ori Gurel-Gurevich Sep 17 '11 at 23:48
Or even: it is not hard to find a covering sequence of sets with positive $j$ in, say, $\mathbb{Z}^2$ (or even in $\mathbb{Z}$, if you don't require connectedness). – Ori Gurel-Gurevich Sep 17 '11 at 23:51
OK, thanks. Above I have proposed a more specific question that is the one that I am really interested in. – Valerio Capraro Sep 18 '11 at 9:10
Now your sets $A_n$ look like unions of odd and even spheres - why don't you formulate your question just in more usual terms of balls and spheres? – R W Sep 18 '11 at 11:46
I am sorry, I am very new in the topic and I don't know if there is some usual formulation. What would it be? Something like: let x∈X and let $B_n$ be the ball of radius $n$ about $x$ and $S_n=\partial B_n$. Denote by $j(x)$ the infimum of the $\frac{|S_n|}{|B_n|}$′s. Is it possible that there are two vertex $x$ and $y$ suchthat $j(x)\neq j(y)$? In case of positive answer, let $j$ be the infimum of the $j(x)$′s, is it possible that $j=0$ and there is $x$ such that $j(x)>0$. Is usual this formulation? Anyway, thanks for helping to improve my question – Valerio Capraro Sep 18 '11 at 12:35

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$.

-
Maybe I am misunderstanding something, but it seems to me that this graph is not locally finite, since the neighborhood of $a$ of radius $1$ contains infinitely many points. Am I wrong? Anyway, I am also very interested in the counterexample to the first question in locally finite graph. It would be great if you can add some details. – Valerio Capraro Sep 19 '11 at 16:18
Perhaps I did not explai carefully. We identify the vertices for each $d$ separately; that is, we unite all the vertices at distance 3 from $a$ into a vertex $v_1$, all the vertices at distance 6 from $a$ --- into a (different!) vertex $v_2$, and so on. So the degree of $a$ in the (resulting) graph is 2. – Ilya Bogdanov Sep 19 '11 at 16:56
I've added a counterexample of a bounded degree. – Ilya Bogdanov Sep 19 '11 at 17:13
Yes, it seems clear. Thank you. – Valerio Capraro Sep 19 '11 at 21:16

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$.

-
Many thanks for the example. Actually I was probably misled by the fact that I was thinking to a more specific situation. Above I have propose it. – Valerio Capraro Sep 18 '11 at 9:12