Finite Voronoi decompositions of infinite vertex transitive graphs

Details Finite Voronoi decompositions of infinite vertex transitive graphs Finite Voronoi decompositions of infinite vertex transitive graphs

2011-11-02

arxiv.org/abs/1111.0472v1

Mathematics

Metric Geometry

Scientific paper

In this paper, we consider the Voronoi decompositions of an arbitrary infinite vertex-transitive graph G. In particular, we are interested in the following question: what is the largest number of Voronoi cells that must be infinite, given sufficiently (but finitely) many Voronoi sites which are sufficiently far from each other? We call this number the survival number s(G). The survival number of a graph has an alternative characterization in terms of covering, which we use to show that s(G) is always at least two. The survival number is not a quasi-isometry invariant, but it remains open whether finiteness of the s(G) is. We show that all vertex transitive graphs with polynomial growth have a finite s(G); vertex transitive graphs with infinitely many ends have an infinite s(G); the lamplighter graph LL(Z), which has exponential growth, has a finite s(G); and the lamplighter graph LL(Z^2), which is Liouville, has an infinite s(G).

Affiliated with

Also associated with

No associations

Rating

Finite Voronoi decompositions of infinite vertex transitive graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finite Voronoi decompositions of infinite vertex transitive graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite Voronoi decompositions of infinite vertex transitive graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-328125