# 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
show 1 more comment

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