13
$\begingroup$

It is known that for metric graphs the concepts of Gromov's hyperbolicity and strictly positive Cheeger constant are related. Let us first recall the definition of the Cheeger constant. Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. For a collection of vertices $A \subseteq V(G)$, let $\partial A$ denote the collection of all edges going from a vertex in $A$ to a vertex outside of $A$, $$ \partial A := \{ (x, y) \in E : x \in A, y \in V(G) \setminus A \}. $$

Then the Cheeger constant of G, denoted $h(G)$, is defined as $$ h(G) := \inf \left\{ \frac{|\partial A|}{|A|} : A \subseteq V(G)\quad\text{and}\quad |A|<\infty \right\}. $$

However, neither Gromov's hyperbolicity nor strictly positive Cheeger constant implies the other. For instance, the graph $\mathbb{Z}$ is hyperbolic in the sense of Gromov but its Cheeger constant is zero. On the other hand, the Cayley graph of the group $\mathbb{F}_{2}\times\mathbb{F}_2$ has positive Cheeger constant but it is not hyperbolic since $\mathbb{Z}\times \mathbb{Z}$ sits as a subgroup.

Does there exist a planar graph with positive Cheeger constant but not hyperbolic?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Could you explain how 'the concepts of Gromov's hyperbolicity and strictly positive Cheeger constant are related'? $\endgroup$
    – HJRW
    Commented Mar 27, 2011 at 18:10
  • 1
    $\begingroup$ I think this is one definition of a Gromov hyperbolic graph: any two of its geodesics are either parallel or diverge exponentially. Maybe Gabriel can elaborate further ... $\endgroup$
    – Joseph O'Rourke
    Commented Mar 27, 2011 at 19:20
  • 2
    $\begingroup$ @HW: See the paper for a more detailed discussion: "Cheeger Isoperimetric Constants of Gromov-Hyperbolic Spaces with Quasi-Poles" by J. Cao, published in Communications in Contemporary Mathematics, Vol. 2, No. 4, pp. 511–533, 2000. @Joseph: The definition of Gromov's hyperbolic graph is that there exists $\delta>0$ such that all the geodesic triangles in the graph are $\delta$ thin. This means that any side of a triangle is in the $\delta$ neighborhood of the other two. As you said this implies that every two geodesic rays starting in a point diverge exponentially $\endgroup$
    – ght
    Commented Mar 27, 2011 at 19:36
  • 2
    $\begingroup$ @Gabriel, thanks for the reference. Regarding Joseph's comment, there are many definitions of $\delta$-hyperbolicity - indeed, the definition that you give is, I believe, due to Rips, not Gromov. I think the heart of Joseph's claim is that the converse of the proposition you state is also true. $\endgroup$
    – HJRW
    Commented Mar 27, 2011 at 20:08

1 Answer 1

Reset to default
9
$\begingroup$

If I add the assumption that the given graph has bounded degree, and the same holds for the dual graph, then the answer to your question is no. A positive Cheeger constant implies a linear isoperimetric inequality which in turn implies Gromov hyperbolicity.

However, if you allow the dual graph to have unbounded degree (say), there are examples. Let $T$ be the regular degree $3$ tree. Note that $h(T) > 0$. Properly embed $T$ in the plane. Let $C_i$ be an ordering of the complementary regions. Now add a single edge $e_i$, in the interior of $C_i$, so that $C_i$ is divided into two regions, one compact and the other not compact. We add the edge so that the compact region is bounded by a cycle of length $i$.

Let $T' = T \cup (\cup e_i)$. The cycles created above prevent $T'$ from being Gromov hyperbolic. However $h(T') \geq h(T)$ as adding edges does not decrease the Cheeger constant.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks Sam. That was my intuition also! Do you have a reference for this result or a sketch of the proof? $\endgroup$
    – ght
    Commented Mar 27, 2011 at 19:50
  • 2
    $\begingroup$ For the first paragraph: Let $\gamma$ be a simple loop in the plane, transverse to the given graph and meeting every complementary region at most once. We need to prove that there is a constant $K$ so that the area of $\gamma$ is bounded by $K$ times its length. So we must define length and area. Length will be the number of edges traversed in the dual graph and area to be number of vertices contained in the bounded disk. The linear isoperimetric inequality now follows from positivity of $h$. $\endgroup$
    – Sam Nead
    Commented Mar 27, 2011 at 20:35
  • $\begingroup$ Bowditch has many references, and some course notes, at the webpage for his class: warwick.ac.uk/~masgak/ggt/course.html. Bridson and Haefliger's book is particularly nice to read. $\endgroup$
    – Sam Nead
    Commented Mar 27, 2011 at 20:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .