Introduction

L. Babai has pointed out that results on local expansion of vertex-transitive graphs [BS] limit the possible pathologies (i.e., hills and valleys) in the distance sequences of locally finite undirected vertex-transitive graphs, and has asked if ``valleys'' can occur in the locally infinite case[B]. In this note we prove that no valleys can occur in the locally infinite case for undirected graphs and give a full characterization of possible distance sequences.

For directed graphs (digraphs), we show that the infinite terms of the out-distance sequences of vertex-transitive digraphs are nonincreasing, and additionally that any nonincreasing sequence of infinite cardinals is the out-distance sequence of some vertex-transitive digraph. Additionally, we offer constructions to show that any out-distance sequence of a vertex-transitive digraph of finite degree can be `mimicked' by the tail of the out-distance sequence of a vertex-transitive digraph of infinite out-degree (in particular, valleys can occur in the directed case).

Definition 1.1   The positive $n$ -sphere, $S^{+}(k,x)$ , about a vertex $x$ in a digraph is the set of vertices at directed distance $k$ from $x$ .

Definition 1.2   The diameter diam($G$ ) is the supremum of the pairwise distances of vertices of $G$ . This is either an integer or $\infty$ .

Definition 1.3   A digraph $G$ is vertex-transitive if every pair of vertices in $G$ is equivalent under the automorphism group of $G$ .

Let ${f^{+}}(k)$ denote the cardinality of $S^{+}(k,x)$ for some vertex $x$ in the digraph $G$ . Because $G$ is vertex-transitive, ${f^{+}}(k)$ does not depend on the choice of the vertex $x$ . We call the sequence ${f^{+}}(0), {f^{+}}(1), {f^{+}}(2), \ldots$ the `out-distance sequence' of $G$ . For $k>{\rm diam}(G)$ we set ${f^{+}}(k)=0$ . For undirected graphs, we denote the $n$ -sphere and distance sequence by $S(k,x)$ and $\{f(k)\}$ , respectively.

Our main results are the following.

Theorem 1.4   Let $G$ be an infinite, vertex-transitive, undirected graph of infinite degree $d$ . Then, for $0< k < {\rm diam}(G)$ we have $f(k)=d$ .

Noting that for infinite cardinals we have $d\cdot d=d$ and therefore $f(k)\leq d$ for all $k$ , Theorem 1.4 implies the following options for the distance sequence of a locally infinite vertex-transitive undirected graph.

Corollary 1.5   Let $G$ be an infinite, vertex-transitive, undirected graph of infinite degree $d$ . If $G$ has infinite diameter then its distance sequence is $1,d,d,\dots$ . If $G$ has finite diameter then its distance sequence is $1,d,\dots ,d,e$ , where $e\leq d$ .

In Section 3 we shall prove that all possibilities permitted by Corollary 1.5 can actually occur, so Corollary 1.5 gives a full characterization of the distance sequences of locally infinite vertex-transitive undirected graphs.

For directed graphs, we prove the following.

Theorem 1.6   Let $G$ be an infinite, vertex-transitive digraph of infinite out-degree $d$ . Then, for all $k>0$ for which ${f^{+}}(k+1)$ is infinite, we have ${f^{+}}(k)\geq {f^{+}}(k+1)$ .

Theorems 1.4 and 1.6 follow from the following lemma.

Lemma 1.7   For a vertex-transitive digraph of finite or infinite out-degree, the out-distance sequence $\{{f^{+}}(k)\}$ satisfies ${f^{+}}(k+1)\leq {f^{+}}(k)^2$ , for $k\geq 1$ .

Note 1   A sequence $a_0, a_1, a_2, \ldots$ is log-concave if $(\forall i) (a_i^2 \geq a_{i-1}\cdot a_{i+1})$ . For positive integers, log-concavity implies unimodality (the sequence increases up to a point, then decreases). For a sequence of infinite cardinals, log-concavity implies that the sequence is constant except for its first and last terms. Therefore Corollary 1.5 can be restated as follows:

If $G$ is a vertex-transitive undirected graph of infinite degree then its distance sequence is log-concave.

In Section 4 we will give constructions of directed graphs of infinite out-degree whose distance sequences are not log-concave, or even unimodal. For comments on the analogous question in the locally finite case for undirected graphs, see Section 5.

For information about combinatorial parameters of vertex-transitive graphs, we refer to the survey [B1].

Acknowledgment

I'd like to thank László Babai for posing the questions I consider here, and for helping me polish the proofs.