On Directed and Undirected Diameters of Vertex-Transitive Graphs

Abstract

A directed diameter of a directed graph is the maximum possible distance between a pair of vertices, where paths must respect edge orientations, while undirected diameter is the diameter of the undirected graph obtained by symmetrizing the edges. In 2006 Babai proved that for a connected directed Cayley graph on $n$ vertices the directed diameter is bounded above by a polynomial in undirected diameter and $\log n$. Moreover, Babai conjectured that a similar bound holds for vertex-transitive graphs. We prove this conjecture of Babai, in fact, it follows from a more general bound for connected relations of homogeneous coherent configurations. The main novelty of the proof is a generalization of Ruzsa’s triangle inequality from additive combinatorics to the setting of graphs

1 Introduction

Given a (finite) connected directed graph $\Gamma$, let $\overrightarrow{\textrm{diam}}(\Gamma )$ denote the directed diameter, which is the maximum directed distance between a pair of vertices of $\Gamma$. The undirected diameter ${{\,\textrm{diam}\,}}(\Gamma )$ is the maximum undirected distance between a pair of vertices, that is, we forget about edge orientations in $\Gamma$ when measuring distances. Clearly ${{\,\textrm{diam}\,}}(\Gamma ) \le \overrightarrow{\textrm{diam}}(\Gamma )$.

In general, it is not possible to bound the directed diameter in terms of the undirected diameter only, yet it is interesting how close these two quantities are if the graph is symmetric enough. One of the classical examples when the difference between the directed and undirected diameters manifests itself, is the famous question of Babai about the diameters of Cayley graphs of finite simple groups. Given a finite group $G$ and its generating set $S \subseteq G$, recall that a Cayley graph $\textrm{Cay}(G, S)$ is a directed graph with the vertex set $G$, where two vertices $x, y \in G$ are joined by a directed edge if $y = xg$ for some $g \in S$. Let $\log n$ denote the base-2 logarithm of $n$. Babai proposed the following conjecture:

Conjecture 1.1

([4, Conjecture 1.7]) Given a nonabelian finite simple group $G$ generated by $S \subseteq G$, we have

$$\begin{aligned} {{\,\textrm{diam}\,}}(\textrm{Cay}(G, S)) \le (\log |G|)^C \end{aligned}$$

for some universal constant $C > 0$.

Although this conjecture is still open, there have been a plethora of results solving the conjecture in some particular cases and obtaining nontrivial bounds for the diameter (see [2, 4, 7, 11, 13], to name a few). These works often make heavy use of the fact that we may assume our generating set $S$ to be closed under taking inverses, for example, the proof of [2] requires taking commutators of group elements, i.e. words of the form $x^{-1}y^{-1}xy$ for $x, y \in G$. Such a word does not correspond to a proper path in the directed Cayley graph, so one has to work with undirected graphs instead.

Luckily, in 2006 Babai proved a result which resolved this issue for Cayley graphs.

Proposition 1.2

([1, Theorem 1.4]) Let $\Gamma$ be a connected Cayley graph on $n$ vertices. Then $\overrightarrow{\textrm{diam}}(\Gamma ) = O({{\,\textrm{diam}\,}}(\Gamma )^2 (\log n)^3)$.

In particular, it immediately follows that if ${{\,\textrm{diam}\,}}(\textrm{Cay}(G, S)) \le (\log |G|)^C$ for some group $G$ and a generating set $S$, then $\overrightarrow{\textrm{diam}}(\textrm{Cay}(G, S)) = O((\log |G|)^{2C+3})$, so it is enough to solve Babai’s conjecture for undirected Cayley graphs only.

The proof of Proposition 1.2 relies on a result of Babai and Erdős [3] about fast generating sets of finite groups, and a theorem of Babai and Szegedy on expansion in vertex-transitive graphs [5]. Since Cayley graphs are vertex-transitive, it is natural to ask if a similar bound on the directed diameter holds for vertex-transitive graphs. To this end, Babai makes the following conjecture:

Conjecture 1.3

([1, Conjecture 6.1]) Given a connected vertex-transitive graph $\Gamma$ on $n$ vertices, there exists a polynomial upper bound on $\overrightarrow{\textrm{diam}}(\Gamma )$ in terms of ${{\,\textrm{diam}\,}}(\Gamma )$ and $\log n$.

In the same paper Babai found such a bound under a condition that the outdegree of $\Gamma$ is bounded. If $k$ is the outdegree of $\Gamma$, then in [1, Theorem 1.1] it is proved that $\overrightarrow{\textrm{diam}}(\Gamma ) = O({{\,\textrm{diam}\,}}(\Gamma ) \cdot k \log n)$ and in [1, Corollary 1.2] that $\overrightarrow{\textrm{diam}}(\Gamma ) = O({{\,\textrm{diam}\,}}(\Gamma )^2 \cdot k \log k)$. If $\Gamma$ is edge-transitive, then by [1, Theorem 1.5] we have $\overrightarrow{\textrm{diam}}(\Gamma ) = O({{\,\textrm{diam}\,}}(\Gamma ) \log n)$, so the conjecture holds in this case.

The main result of this paper is the solution of the above conjecture of Babai on vertex-transitive graphs.

Theorem 1.4

Let $\Gamma$ be a connected vertex-transitive graph on $n$ vertices. Then

$$\begin{aligned} \overrightarrow{\textrm{diam}}(\Gamma ) = O({{\,\textrm{diam}\,}}(\Gamma )^2 (\log n)^2). \end{aligned}$$

Note that in the case of Cayley graphs our result improves Babai’s by a factor of $\log n$.

We derive Theorem 1.4 as a corollary of a more general result about homogeneous coherent configurations (also known as association schemes [6]). Namely, in Theorem 4.1 we prove that the above bound for the directed diameter holds when $\Gamma$ is a connected relation of a homogeneous coherent configuration. Since a vertex-transitive graph is a relation of a coherent configuration corresponding to its full automorphism group, Theorem 1.4 follows at once.

To prove Theorem 4.1 we employ a vertex expansion bound for undirected relations of homogeneous coherent configurations (Proposition 2.2), analogous to the Babai-Szegedy bound [5] for undirected graphs. In order to relate the vertex expansion of the original directed graph with the expansion of its symmetrization, we introduce the Ruzsa triangle inequality for graphs (Theorem 3.1), which we think might be of independent interest. To state the result, let $a, b \subseteq \Omega \times \Omega$ be some relations (or, equivalently, directed graphs) on the set $\Omega$ and let $ab \subseteq \Omega \times \Omega$ denote their product. Let $b^* \subseteq \Omega \times \Omega$ denote the transposed relation, and let $\Vert a \Vert$ be the maximum outdegree of a vertex in $a$ (we give precise definitions of these notions in Sects. 2 and 3). If $a, b, c \subseteq \Omega \times \Omega$ and $b$ is regular, then

$$\begin{aligned} \Vert ac \Vert \cdot \Vert b \Vert \le \Vert ab \Vert \cdot \Vert b^*c \Vert . \end{aligned}$$

When $a, b, c$ are Cayley graphs, this gives the classical Ruzsa inequality for groups [14], an indispensable tool in additive combinatorics. In Sect. 3 we show how this can be used to bound the directed diameter when the underlying coherent configuration has a certain commutativity condition (Proposition 3.4). For instance, if $\Gamma$ is a connected Cayley graph on $n$ vertices over an abelian group, then

$$\begin{aligned} \overrightarrow{\textrm{diam}}(\Gamma ) = O({{\,\textrm{diam}\,}}(\Gamma ) \log \log n). \end{aligned}$$

In Sect. 5 we show that in general it is not possible to bound the directed diameter or directed girth in terms of the undirected diameter only, even in the case of Cayley graphs over abelian groups. This answers two other questions of Babai [1, Problems 6.4 and 6.5], and the proof relies on a construction of Haight and Ruzsa [10, 15] of special subsets of cyclic groups.

The structure of the paper is as follows. In Sect. 2 we give preliminaries on coherent configurations and prove a generalization of the Babai-Szegedy bound [5] to relations of homogeneous coherent configurations (Proposition 2.2). In Sect. 3 we prove the Ruzsa inequality for graphs (Theorem 3.1) and give an application for coherent configurations with a commutativity condition (Proposition 3.4). The main result is proved in Sect. 4, and in Sect. 5 we give examples of Cayley graphs with bounded undirected diameter and unbounded directed diameter and girth.

2 Preliminaries

Let $\Omega$ be a finite set. Given two relations $a, b \subseteq \Omega \times \Omega$ let

$$\begin{aligned} ab = \{ (\alpha , \beta ) \in \Omega \times \Omega \mid (\alpha , \gamma ) \in a,\, (\gamma , \beta ) \in b \text { for some } \gamma \in \Omega \} \end{aligned}$$

denote the product relation. We write $1_\Omega = \{ (\alpha , \alpha ) \mid \alpha \in \Omega \}$ for the diagonal relation, and $a^* = \{ (\beta , \alpha ) \in \Omega \times \Omega \mid (\alpha , \beta ) \in a \}$ for the transposition of $a$. Note that $(a^*)^* = a$ and $(ab)^* = b^* a^*$.

We will view graphs on the vertex set $\Omega$ as relations on $\Omega$, and will use these two terms interchangeably. All our graphs are directed by default, and we say that a graph $a \subseteq \Omega \times \Omega$ is undirected, if $a = a^*$. If $a$ is a connected graph on $\Omega$, we write $\overrightarrow{\textrm{diam}}(a)$ for the directed diameter of $a$, that is, the largest possible distance between a pair of vertices in $a$, where paths between vertices must preserve edge orientations. Similarly, ${{\,\textrm{diam}\,}}(a)$ denotes the undirected diameter of $a$, which is the largest distance between a pair of vertices where paths are not required to preserve edge orientations; in other words, ${{\,\textrm{diam}\,}}(a) = \overrightarrow{\textrm{diam}}(a \cup a^*)$.

Let $S$ be a partition of $\Omega \times \Omega$ into relations. We say that a tuple ${{\,\mathrm{\mathfrak {X}}\,}}= (\Omega , S)$ is a homogeneous coherent configuration or, shortly, a scheme, if the following holds [9, Definition 2.1.3]:

• 1. $1_\Omega \in S$,

• 2. If $a \in S$, then $a^* \in S$,

• 3. For any $a, b, c \in S$ and any $(\alpha , \beta ) \in a$, the number

  $$\begin{aligned} |\{ \gamma \in \Omega \mid (\alpha , \gamma ) \in b,\, (\gamma , \beta ) \in c \}| \end{aligned}$$

  does not depend on the choice of $(\alpha , \beta ) \in a$.

The set $S = S({{\,\mathrm{\mathfrak {X}}\,}})$ is the set of basis relations of ${{\,\mathrm{\mathfrak {X}}\,}}$, and we define $S^\cup = S^\cup ({{\,\mathrm{\mathfrak {X}}\,}})$ as the set of all unions of basis relations of ${{\,\mathrm{\mathfrak {X}}\,}}$, in particular, $S \subseteq S^\cup$. It follows from the definition of a scheme that $S^\cup$ is closed under taking products and transpositions of relations [9, Proposition 2.1.4]. Moreover, if $a \in S^\cup$ then the indegree and outdegree of any vertex of $a$ are the same and do not depend on the vertex [9, Definition 2.1.10 and Corollary 2.1.13]. In particular, all graphs (relations) from $S^\cup$ are regular.

Given a transitive permutation group $G$ on $\Omega$ one can construct a scheme as follows (see also [9, Definition 2.2.3]). We set ${{\,\mathrm{\mathfrak {X}}\,}}= (\Omega , S)$ where $S$ is the partition of the set $\Omega \times \Omega$ into orbits of $G$ in its natural action on pairs; one can easily check that ${{\,\mathrm{\mathfrak {X}}\,}}$ is indeed a scheme. If $\Gamma$ is a vertex-transitive graph (for example, a Cayley graph) on $\Omega$ with the full automorphism group $G$, then $\Gamma$ can be partitioned into orbits of $G$ and hence $\Gamma \in S^\cup ({{\,\mathrm{\mathfrak {X}}\,}})$.

The following lemma is a generalization of the third property from the definition of a scheme.

Lemma 2.1

([9, Exercise 2.7.25]) Let ${{\,\mathrm{\mathfrak {X}}\,}}= (\Omega , S)$ be a scheme, and let $r$, $r_1, \dots , r_{m-1} \in S$, $m \ge 2$ and $(u, w) \in r$. Then the number of tuples $(v_1, \dots , v_m) \in \Omega ^m$ such that $(v_1, v_m) = (u, w)$ and $(v_i, v_{i+1}) \in r_i$, $i = 1, \dots , m-1$ does not depend on the choice of $(u, w) \in r$.

Let $b \subseteq \Omega \times \Omega$ be an undirected graph on $\Omega$. For a subset $T \subseteq \Omega$ let $\partial _b(T)$ denote the set of vertices outside of $T$ adjacent in $b$ to a vertex in $T$, i.e.

$$\begin{aligned} \partial _b(T) = \{ \beta \in \Omega \setminus T \mid \alpha \in T,\, (\alpha , \beta ) \in b \}. \end{aligned}$$

Babai and Szegedy [5, Theorem 2.2] showed that for a connected vertex-transitive graph $b$ and $T \subseteq \Omega$, $0 < |T| \le |\Omega |/2$, the vertex expansion ratio $|\partial _b(T)|/|T|$ can be bounded from below in terms of ${{\,\textrm{diam}\,}}(b)$. To prove Theorem 4.1, we show that this bound holds in the setting of schemes. The argument is essentially the same as in [5], but requires a few technicalities to count paths between vertices in relations of schemes.

Proposition 2.2

Let ${{\,\mathrm{\mathfrak {X}}\,}}= (\Omega , S)$ be a scheme, and let $b \in S^\cup$ be a connected relation with $b = b^*$. For any nonempty subset $T$ of $\Omega$ we have

$$\begin{aligned} \frac{|\partial _b(T)|}{|T|} \ge \frac{2(1 - |T|/|\Omega |)}{{{\,\textrm{diam}\,}}(b) + |T|/|\Omega |}. \end{aligned}$$

In particular, if $|T| \le |\Omega |/2$, then

$$\begin{aligned} \frac{|\partial _b(T)|}{|T|} \ge \frac{2}{2{{\,\textrm{diam}\,}}(b) + 1}. \end{aligned}$$

Proof

We may view $b$ as an undirected graph on $\Omega$. For $x, y \in \Omega$ let $d(x, y)$ denote the distance between $x$ and $y$ in $b$. A path $x_0, x_1, \dots , x_m$ in $b$ will be called a geodesic if $m = d(x_0, x_m)$. Note that a geodesic is an ordered sequence of points, so $x_m, \dots , x_1, x_0$ is a different geodesic.

By [9, Theorem 2.6.7] the distance-$i$ graph $\{ (u, v) \in \Omega \times \Omega \mid d(u, v) = i \}$ lies in $S^{\cup }$, in particular, the distance between points $x$ and $y$ depends only on the basis relation where $(x, y)$ lies.

Let $p(x, y)$ denote the number of geodesics between $x$ and $y$. If $z$ is some vertex, then we claim that the number

$$\begin{aligned} P_z = \sum _{x, y \in \Omega } \frac{1}{p(x, y)} |\{ L \mid L \text { is a geodesic from } x \text { to } y \text { passing through } z \}| \end{aligned}$$

does not depend on the choice of $z \in \Omega$. Indeed, by Lemma 2.1, the number $p(x, y)$ depends only on the basis relation where $(x, y)$ lies. The number of geodesics from $x$ to $y$ passing through $z$ can be expressed as

$$\begin{aligned} N_z(x, y) = {\left\{ \begin{array}{ll} p(x, z) \cdot p(z, y), &{} \text { if } d(x, z) + d(z, y) = d(x, y),\\ 0, &{} \text { otherwise.} \end{array}\right. } \end{aligned}$$

By the paragraph above, this number depends only on the basis relations where $(x, z)$, $(z, y)$ and $(x, y)$ lie. Therefore we have the following formula:

$$\begin{aligned} P_z = \sum _{r, s, t \in S} \sum _{\begin{array}{c} x, y \in \Omega ,\\ (x, z) \in r, (z, y) \in s, (x, y) \in t \end{array}} \frac{1}{p(x, y)} N_z(x, y). \end{aligned}$$

By applying Lemma 2.1 to the path $z, x, y, z$, we see that the number of tuples $(x, y) \in t$ satisfying $(x, z) \in r$, $(z, y) \in s$ does not depend on the choice of $z$. Hence $P = P_z$ does not depend on the choice of $z$, as claimed.

Set $n = |\Omega |$. We claim that

$$\begin{aligned} n \cdot P = \sum _{x, y \in \Omega } (d(x, y)+1). \end{aligned}$$

Since $P$ does not depend on the choice of $z \in \Omega$ we have

$$\begin{aligned} n \cdot P= & {} \sum _{z \in \Omega } \sum _{x, y \in \Omega } \frac{1}{p(x, y)} |\{ L \mid L \text { is a geodesic from } x \text { to } y \text { passing through } z \}|\\= & {} \sum _{x, y \in \Omega } \frac{1}{p(x, y)} \sum _{z \in \Omega } |\{ L \mid L \text { is a geodesic from } x \text { to } y \text { passing through } z \}|. \end{aligned}$$

There are $d(x,y)+1$ vertices in a geodesic from $x$ to $y$, and there are $p(x, y)$ such geodesics, hence

$$\begin{aligned}{} & {} \sum _{x, y \in \Omega } \frac{1}{p(x, y)} \sum _{z \in \Omega } |\{ L \mid L \text { is a geodesic from } x \text { to } y \text { passing through } z \}|\\= & {} \sum _{x, y \in \Omega } \frac{1}{p(x, y)} \cdot (d(x, y)+1)p(x, y) = \sum _{x, y \in \Omega } (d(x,y)+1), \end{aligned}$$

which proves the claim.

Now we are ready to prove the expansion bound. Let $T$ be a nonempty subset of $\Omega$. Consider a set of pairs

$$\begin{aligned} K = (T \times (\Omega \setminus T)) \cup ((\Omega \setminus T) \times (T \cup \partial _b(T))). \end{aligned}$$

A path between $T$ and $\Omega {\setminus } T$ must intersect $\partial _b(T)$, hence

$$\begin{aligned} |K| = \sum _{(x, y) \in K} \frac{1}{p(x, y)} |\{ L \mid L \text { is a geodesic from } x \text { to } y \text { through } \partial _b(T)\}|. \end{aligned}$$

We extend summation to the whole of $\Omega$ and derive

$$\begin{aligned} |K|\le & {} \sum _{x, y \in \Omega } \frac{1}{p(x, y)} |\{ L \mid L \text { is a geodesic from } x \text { to } y \text { through } \partial _b(T)\}|\\\le & {} \sum _{x, y \in \Omega } \frac{1}{p(x, y)} \sum _{z \in \partial _b(T)} |\{ L \mid L \text { is a geodesic from } x \text { to } y \text { through } z\}|\\= & {} \sum _{z \in \partial _b(T)} \sum _{x, y \in \Omega } \frac{1}{p(x, y)} |\{ L \mid L \text { is a geodesic from } x \text { to } y \text { through } z\}|\\= & {} \sum _{z \in \partial _b(T)} P = |\partial _b(T)| \cdot P = \frac{|\partial _b(T)|}{n} \sum _{x, y \in \Omega } (d(x, y)+1) \\\le & {} n \cdot |\partial _b(T)| \cdot ({{\,\textrm{diam}\,}}(b)+1). \end{aligned}$$

To compute the size of $K$, recall that $T$ and $\partial _b(T)$ are disjoint, hence

$$\begin{aligned} |K| = |T \times (\Omega \setminus T)| + |(\Omega \setminus T) \times (T \cup \partial _b(T))| = (n-|T|)(2|T| + |\partial _b(T)|). \end{aligned}$$

After substituting in the inequality above and dividing by $n|T|$ we derive

$$\begin{aligned} \left( 1 - \frac{|T|}{n}\right) \left( 2 + \frac{|\partial _b(T)|}{|T|}\right) \le \frac{\partial _b(T)}{|T|}({{\,\textrm{diam}\,}}(b)+1). \end{aligned}$$

The claimed result follows after rearranging terms in the inequality. $\square$

We note that a similar bound for the edge expansion of basis relations of coherent configurations was proved in [12, Proposition 2.8].

3 Ruzsa Inequality for Graphs

One of the central tools in additive combinatorics is the Ruzsa triangle inequality [14]. Let $G$ be an arbitrary group. Given subsets $A, B \subseteq G$ let $AB = \{ ab \mid a \in A, b \in B \}$ denote the product set and let $A^{-1} = \{ a^{-1} \mid a \in A \}$ be the inverse set. If $A, B, C \subseteq G$ are finite subsets, then the Ruzsa triangle inequality claims that

$$\begin{aligned} |AC| \cdot |B| \le |AB| \cdot |B^{-1}C|. \end{aligned}$$

The naming stems from the fact that Ruzsa’s inequality implies that the function

$$\begin{aligned} d(A, B) = \log \frac{|AB^{-1}|}{(|A|\cdot |B|)^{1/2}} \end{aligned}$$

obeys the usual triangle inequality $d(A, C) \le d(A, B) + d(B, C)$.

The proof of this beautiful result is rather simple: we construct an injective mapping $f: AC \times B \rightarrow AB \times B^{-1}C$ in the following manner. For all $x \in AC$ fix some decomposition $x = a_xc_x$, $a_x \in A$, $c_x \in C$. Now for $b \in B$ set $f(x, b) = (a_xb,\, b^{-1}c_x)$. This map is indeed injective, since if $f(x, b) = (y, z)$ then $x = a_xc_x = (a_xb)(b^{-1}c_x) = yz$, and $b = (a_x)^{-1}y$; in other words, one can recover $x$ and $b$ from $y$ and $z$.

We will now show that essentially the same argument applies to finite graphs. Let $\Omega$ be some finite set. Given a relation $a \subseteq \Omega \times \Omega$ and $\omega \in \Omega$, let $\omega a = \{ \beta \in \Omega \mid (\omega , \beta ) \in a \}$ denote the neighborhood of $\omega$ in $a$. For a subset $T \subseteq \Omega$ we similarly define $Ta = \{ \beta \in \Omega \mid (\alpha , \beta ) \in a,\, \alpha \in T \}$.

To make our results visually closer to analogous statements from additive combinatorics, we will write $\Vert a \Vert$ for the maximum outdegree of a relation $a \subseteq \Omega \times \Omega$, i.e. $\Vert a \Vert = \max _{\omega \in \Omega } |\omega a|$. For any relations $a, b \subseteq \Omega \times \Omega$ we trivially have $\Vert ab \Vert \le \Vert a \Vert \cdot \Vert b \Vert$. We say that the relation $a$ is regular, if $|\omega a|$ does not depend on the choice of $\omega \in \Omega$.

Theorem 3.1

(Ruzsa triangle inequality for graphs) Let $\Omega$ be a finite set, and let $a, b, c \subseteq \Omega \times \Omega$. If $b$ is regular, then

$$\begin{aligned} \Vert ac \Vert \cdot \Vert b \Vert \le \Vert ab \Vert \cdot \Vert b^*c \Vert . \end{aligned}$$

Proof

Fix a point $\omega \in \Omega$ such that $\Vert ac \Vert = |\omega ac|$. Set $m = \Vert ac \Vert$ and $k = \Vert b \Vert$. Then $m = |\omega ac|$, so $\{ \gamma _1, \dots , \gamma _m \} = \omega ac$ for some necessarily distinct points $\gamma _i$. Choose points $\alpha _i$, $i = 1, \dots , m$, such that $(\omega , \alpha _i) \in a$ and $(\alpha _i, \gamma _i) \in c$. For each $i \in \{ 1, \dots , m \}$ choose $k$ distinct points $\beta _{i1}, \dots , \beta _{ik}$ such that $(\alpha _i, \beta _{ij}) \in b$ for all $i = 1, \dots , m$, $j = 1, \dots , k$.

Define a map $f: \{ 1, \dots , m \} \times \{ 1, \dots , k \} \rightarrow \Omega \times \Omega$ by the rule $f(i, j) = (\beta _{ij}, \gamma _i)$. Let $I = \{ f(i, j) \mid i = 1, \dots , m,\, j = 1, \dots , k \}$ be the image of that map. Then

$$\begin{aligned} I = \bigcup _{\beta \in \omega ab} \{ f(i, j) \mid \beta _{ij} = \beta ,\, i = 1, \dots , m,\, j = 1, \dots , k \}. \end{aligned}$$

Observe that sets in that union are disjoint, therefore

$$\begin{aligned} |I| = \sum _{\beta \in \omega ab} |\{ \gamma _i \mid \beta _{ij} = \beta ,\, i = 1, \dots , m,\, j = 1, \dots , k \}|. \end{aligned}$$

Since $(\beta _{ij}, \alpha _i) \in b^*$ and $(\alpha _i, \gamma _i) \in c$, we have $\gamma _i \in \beta _{ij}b^*c$. Hence

$$\begin{aligned} |I| \le \sum _{\beta \in \omega ab} |\{ \gamma _i \in \beta b^*c \mid i = 1, \dots , m \}| \le \sum _{\beta \in \omega ab} \Vert b^*c \Vert \le \Vert ab \Vert \cdot \Vert b^*c \Vert . \end{aligned}$$

Now we show that $f$ is injective. Suppose $f(i, j) = f(i', j')$ for some $i \in \{ 1, \dots , m \}$ and $j \in \{ 1, \dots , k \}$. Then $\beta _{ij} = \beta _{i'j'}$ and $\gamma _i = \gamma _{i'}$. Last equality implies $i = i'$, so $\beta _{ij} = \beta _{ij'}$ and $j = j'$ follows.

Since $f$ is injective, we have $m \cdot k \le |I|$ which is the desired inequality. $\square$

As all relations of a scheme are regular, we have the following immediate corollary.

Corollary 3.2

(Ruzsa triangle inequality for schemes) Let ${{\,\mathrm{\mathfrak {X}}\,}}$ be a scheme and $a, b, c \in S^\cup ({{\,\mathrm{\mathfrak {X}}\,}})$. Then

$$\begin{aligned} \Vert ac \Vert \cdot \Vert b \Vert \le \Vert ab \Vert \cdot \Vert b^*c \Vert . \end{aligned}$$

To illustrate how this can be used, we apply Ruzsa’s inequality to bound the directed diameter in schemes with a certain commutativity condition.

Lemma 3.3

For a scheme ${{\,\mathrm{\mathfrak {X}}\,}}$ and $a, b \in S^\cup ({{\,\mathrm{\mathfrak {X}}\,}})$ we have

$$\begin{aligned} \Vert aa^* \Vert ^{1/2} \cdot \Vert b \Vert ^{1/2} \le \Vert ab \Vert . \end{aligned}$$

Proof

Ruzsa’s inequality gives $\Vert aa^* \Vert \cdot \Vert b \Vert \le \Vert ab \Vert \cdot \Vert b^*a^* \Vert = \Vert ab \Vert ^2$, where the last equality uses the fact that $\Vert c \Vert = \Vert c^* \Vert$ for any $c \in S^\cup ({{\,\mathrm{\mathfrak {X}}\,}})$. $\square$

Note that if $a$ is a connected relation from $S^\cup ({{\,\mathrm{\mathfrak {X}}\,}})$ for some scheme ${{\,\mathrm{\mathfrak {X}}\,}}$ on $\Omega$, then $\overrightarrow{\textrm{diam}}(a)$ is equal to the smallest $k$ such that

$$\begin{aligned} (a \cup 1_\Omega )^k = \underbrace{(a \cup 1_\Omega ) \cdot \dots \cdot (a \cup 1_\Omega )}_{k \text { times}} = \Omega \times \Omega . \end{aligned}$$

Here we used that $1_\Omega$ acts as a multiplicative identity, i.e. $a 1_\Omega = 1_\Omega a = a$. In its turn, ${{\,\textrm{diam}\,}}(a)$ is equal to the smallest $k$ such that $(a \cup a^* \cup 1_\Omega )^k = \Omega \times \Omega$.

Recall also that if $a \in S^\cup ({{\,\mathrm{\mathfrak {X}}\,}})$, then $\Vert a \Vert = \Vert a^* \Vert$ since ${{\,\mathrm{\mathfrak {X}}\,}}$ is a scheme. Hence if $\Vert a \Vert > n/2$ where $n = |\Omega |$, then $\Vert a^* \Vert > n/2$, and $aa = \Omega \times \Omega$ by the pigeonhole principle.

Proposition 3.4

Let ${{\,\mathrm{\mathfrak {X}}\,}}$ be a scheme on $n$ points and let $a \in S^\cup ({{\,\mathrm{\mathfrak {X}}\,}})$ be a connected relation such that $aa^* = a^*a$. Then $\overrightarrow{\textrm{diam}}(a) = O({{\,\textrm{diam}\,}}(a) \log \log n)$.

Proof

Set $k = {{\,\textrm{diam}\,}}(a)$. We may always assume that $1_\Omega \subseteq a$, so $(a \cup a^*)^k = \Omega \times \Omega$. By expanding the brackets and using commutativity we see that $a^k (a^*)^k = \Omega \times \Omega$, in particular, $\Vert a^k (a^*)^k \Vert = n$. Since $(a^*)^k = (a^k)^*$ we have

$$\begin{aligned} n = \Vert a^k (a^k)^* \Vert \le \Vert a^k \Vert \cdot \Vert (a^k)^* \Vert = \Vert a^k \Vert ^2 \end{aligned}$$

and thus $\Vert a^k \Vert \ge n^{1/2}$.

By Lemma 3.3, for any $m \ge 2$ we have

$$\begin{aligned} \Vert a^{m \cdot k} \Vert \ge \Vert a^k (a^k)^* \Vert ^{1/2} \cdot \Vert a^{(m-1)k} \Vert ^{1/2} \ge n^{1/2} \cdot \Vert a^{(m-1)k} \Vert ^{1/2}, \end{aligned}$$

so by induction we derive

$$\begin{aligned} \Vert a^{m\cdot k} \Vert \ge n^{\frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^m}} = n^{1 - \frac{1}{2^m}}, \end{aligned}$$

for any positive integer $m$. Now set $m = \lceil \log \log n \rceil + 1$. Then $\Vert a^{m \cdot k} \Vert > n/2$ and hence $\Vert (a^{m \cdot k})^* \Vert > n/2$, so $a^{2\,m \cdot k} = \Omega \times \Omega$. Therefore

$$\begin{aligned} \overrightarrow{\textrm{diam}}(a) \le 2{{\,\textrm{diam}\,}}(a) (\lceil \log \log n \rceil + 1), \end{aligned}$$

as claimed. $\square$

A Cayley graph can be viewed as a relation of a certain Cayley scheme [9, Definition 2.4.1], and the condition $aa^* = a^*a$ of the proposition above simply means that the generating set of the Cayley graph must commute with its inverse. Hence the above proposition applies to Cayley graphs over abelian groups or, more generally, to Cayley graphs with normal connection sets, so we have a considerable improvement to Babai’s bound in these cases. Connected relations of commutative schemes [9, Section 2.3.1] also satisfy the conditions of the proposition.

4 Proof of the Main Result

Theorem 1.4 is a consequence of the following more general result about relations of schemes.

Theorem 4.1

Let ${{\,\mathrm{\mathfrak {X}}\,}}= (\Omega , S)$ be a scheme on $n = |\Omega |$ points, and let $a \in S^\cup$ be a connected relation. Then

$$\begin{aligned} \overrightarrow{\textrm{diam}}(a) = O({{\,\textrm{diam}\,}}(a)^2 (\log n)^2). \end{aligned}$$

Proof

Without loss of generality we may assume that $1_\Omega \subseteq a$. Let $b = a \cup a^*$ be the symmetrization of $a$.

Suppose $t \in S^\cup$ is such that $\Vert t \Vert \le n/2$. Choose an arbitrary point $\omega \in \Omega$, and set $T = \omega t$. For brevity, let $d = {{\,\textrm{diam}\,}}(a) = {{\,\textrm{diam}\,}}(b)$. By Proposition 2.2,

$$\begin{aligned} \frac{|\partial _b(T)|}{|T|} \ge \frac{2}{2d + 1} \ge \frac{1}{2d}. \end{aligned}$$

As $1_\Omega \subseteq a$, we have $T \subseteq Ta$. Now, $T \cup \partial _b(T) = Ta \cup Ta^*$, and since $T$ and $\partial _b(T)$ are disjoint, we have $|T| + |\partial _b(T)| = |Ta \cup Ta^*|$. As $a \cup a^* \subseteq aa^*$, we derive $|Ta \cup Ta^*| \le |Taa^*|$. Since all relations of a scheme are regular, we have $\Vert taa^* \Vert = |\omega taa^*|$ and $\Vert t \Vert = |\omega t|$, hence

Let $k$ be the smallest positive integer such that $\Vert a^{k+1} \Vert \le (1 + \frac{1}{2d})^{1/2} \cdot \Vert a^k \Vert$. Notice that $k = O(d \log n)$, indeed, if $\Vert a^{m+1} \Vert > (1 + \frac{1}{2d})^{1/2} \Vert a^m \Vert$ for all $m < k$, then $\Vert a^{k} \Vert > (1 + \frac{1}{2d})^{(k-1)/2}$. Hence $n > (1 + \frac{1}{2d})^{(k-1)/2}$ and $k < 1 + 4d \log n$.

We now apply Ruzsa’s triangle inequality for schemes to obtain

$$\begin{aligned} \Vert taa^* \Vert \cdot \Vert a^k \Vert \le \Vert taa^k \Vert \cdot \Vert (a^k)^* a^* \Vert , \end{aligned}$$

and after dividing by $\Vert t \Vert \cdot \Vert a^k \Vert$ we get:

$$\begin{aligned} \frac{\Vert taa^* \Vert }{\Vert t \Vert } \le \frac{\Vert ta^{k+1} \Vert }{\Vert t \Vert } \cdot \frac{\Vert a^{k+1} \Vert }{\Vert a^k \Vert } \le \frac{\Vert ta^{k+1} \Vert }{\Vert t \Vert } \cdot \left( 1 + \frac{1}{2d} \right) ^{1/2}. \end{aligned}$$

This inequality together with ($\star$), implies that for any $t \in S^\cup$ with $\Vert t \Vert \le n/2$ we have

$$\begin{aligned} \frac{\Vert ta^{k+1} \Vert }{\Vert t \Vert } \ge \left( 1 + \frac{1}{2d} \right) ^{1/2}. \end{aligned}$$

We repeatedly apply the inequality above for $t$ equal to $a^{k+1}$, $a^{2(k+1)}$ etc., so if $\Vert a^{l(k+1)} \Vert \le n/2$ for some $l$, then

$$\begin{aligned} \Vert a^{(l+1)(k+1)} \Vert \ge \left( 1 + \frac{1}{2d} \right) ^{(l+1)/2}. \end{aligned}$$

Therefore for some $m = O(d \log n)$ we have $\Vert a^{m(k+1)} \Vert > n/2$. As we noted earlier, this implies $a^{2\,m(k+1)} = \Omega \times \Omega$. Therefore $\overrightarrow{\textrm{diam}}(a) \le 2\,m(k+1) = O(d^2 (\log n)^2)$ proving the claim. $\square$

If $\Gamma$ is a connected vertex-transitive graph on $\Omega$, then as mentioned in Sect. 2, its full automorphism group induces a scheme on $\Omega$ such that $\Gamma$ is a relation of that scheme. This immediately implies that the proposition above applies to $\Gamma$ and hence Theorem 1.4 follows.

It is interesting to know whether one can lower the exponent of ${{\,\textrm{diam}\,}}(\Gamma )$ in the upper bound. To this end, Babai states the following conjecture:

Conjecture 4.2

([1, Conjecture 6.3]) Given a connected vertex-transitive graph $\Gamma$ on $n$ vertices, we have $\overrightarrow{\textrm{diam}}(\Gamma ) = O({{\,\textrm{diam}\,}}(\Gamma ) (\log n)^C)$ for some universal constant $C$.

As far as the author is aware, this is not known even for Cayley graphs. Note that if one drops vertex-transitivity, then the directed diameter can grow quadratically in terms of the undirected diameter: for every $d \ge 1$ Chvátal and Thomassen [8, Theorem 4] constructed an undirected graph of diameter $d$ such that every orientation of the graph has directed diameter at least $d^2/2 + d$.

5 Negative Results

It is interesting whether one really needs the logarithmic factor in the upper bound on the directed diameter. Indeed, Babai asks

Question 5.1

([1, Problem 6.4]) Is it possible to bound the directed diameter of a vertex-transitive graph in terms of its undirected diameter only?

We give a negative answer to that question. The crux of the argument depends on the following construction of Haight and Ruzsa [10, 15]. Given a subset $A$ of some abelian group written additively, let $k \cdot A$ denote the $k$-fold sumset $A + \dots + A$.

Lemma 5.2

([15]) For any fixed $k \ge 1$ there exists $\alpha _k < 1$ such that for all sufficiently large integer $q$ there is a subset $A \subseteq \mathbb {Z}_q$ with $A - A = \mathbb {Z}_q$ and $|k \cdot A| < q^{\alpha _k}$.

Corollary 5.3

For any $k$ there exists a Cayley graph over an abelian group with undirected diameter at most $2$ and directed diameter at least $k$.

A weaker version of the previous question was also suggested in [1]:

Question 5.4

([1, Problem 6.5]) Does there exist a bound on the length of the shortest directed cycle in a vertex-transitive digraph, depending only on the undirected diameter?

The answer to this question is also negative, but we need a more involved construction.

Note that in the setting of Lemma 5.2 we can always replace $A$ by a shift $x + A = \{ x + a \mid a \in A \}$ where $x \in \mathbb {Z}_q$. Indeed, $(x+A) - (x+A) = A - A = \mathbb {Z}_q$ and $k \cdot (x+A) = k\cdot x + k \cdot A$, so $|k \cdot (x+A)| = |k \cdot A| < q^{\alpha _k}$. In particular, we can always assume that $0 \in A$.

Proposition 5.5

For any $k \ge 1$ there exists a Cayley graph over an abelian group with undirected diameter at most $2$ such that the length of the shortest directed cycle is at least $k$.

Proof

By the previous lemma, for all sufficiently large $q$ there exists a subset $A \subseteq \mathbb {Z}_q$ such that $0 \in A$, $A - A = \mathbb {Z}_q$ and $|k \cdot A| < q^{\alpha _k}$ where $\alpha _k < 1$. For $x \ne 0$ let $I_x = \{ x, 2 \cdot x, \dots , k \cdot x \}$ be an arithmetic progression in $\mathbb {Z}_q$. We claim that for $q$ large enough it is possible to find $x \ne 0$ such that $I_x \subseteq \mathbb {Z}_q {\setminus } (k \cdot A)$.

Indeed, set $P_i = \{ x \in \mathbb {Z}_q \mid i \cdot x \in k \cdot A \}$ for $i = 1, \dots , k$. We can assume that $q$ is a large prime number, in particular, $\mathbb {Z}_q$ is a field with $q > k$. Therefore $|P_i| = |k \cdot A|$ and $|P_1 \cup \dots \cup P_k| \le k|k \cdot A|< k q^{\alpha _k} < q-1$ for $q$ large enough. Hence there exists $x \ne 0$ such that $x \notin P_1 \cup \dots \cup P_k$ which implies $I_x \subseteq \mathbb {Z}_q {\setminus } (k \cdot A)$.

Notice that we can assume that $\{1, \dots , k\} = I_1 \subseteq \mathbb {Z}_q {\setminus } (k \cdot A)$. Indeed, consider $A' = \{ x^{-1}a \mid a \in A \}$. Clearly $A' - A' = \mathbb {Z}_q$ and $k \cdot A' = \{ x^{-1}a \mid a \in k \cdot A \}$, so we may replace $A$ by $A'$.

We first construct a Cayley graph with undirected diameter at most $4$ and the length of the shortest nontrivial directed cycle at least $k$. Let $V = \mathbb {Z}_q \times \mathbb {Z}_q$ be the underlying abelian group and let $B = \{ (a, -1),\, (-1, a) \mid a \in A \}$ be the connection set. As $A - A = \mathbb {Z}_q$, the difference $B - B$ contains $(\mathbb {Z}_q, 0) = \{ (x, 0) \mid x \in \mathbb {Z}_q \}$ and similarly $(0, \mathbb {Z}_q)$. Now $V = (\mathbb {Z}_q, 0) + (0, \mathbb {Z}_q)$, so $B - B + B - B = V$ and the undirected diameter of the Cayley graph $\textrm{Cay}(V, B)$ is at most $4$.

Consider a nontrivial directed cycle in our Cayley graph. It involves $n$ generators of the form $(a_1, -1), \dots , (a_n, -1)$ and $m$ generators of the form $(-1, a'_1), \dots , (-1, a'_m)$, where $a_1, \dots , a_n, a'_1, \dots , a'_m \in A$. Since it is a cycle, we have the following equalities modulo $q$:

$$\begin{aligned} {\left\{ \begin{array}{ll} a_1 + \dots + a_n - m = 0,\\ -n + a'_1 + \dots + a'_m = 0. \end{array}\right. } \end{aligned}$$

Assume that $n \le k$ and $m \le k$. If $m = 0$, then second equality implies that $n = 0$ modulo $q$, which is a contradiction with $q > k$ and the fact that we consider a nontrivial cycle. Hence $m \ge 1$ and, similarly, $n \ge 1$. Now, $m \in n \cdot A$ and $0 \in A$ implies $n \cdot A \subseteq k \cdot A$, so $m$ lies in $k \cdot A$. Recall that the interval $\{ 1, \dots , k \}$ lies fully outside of $k \cdot A$ hence we have a contradiction. Therefore $n$ or $m$ is larger than $k$ and the length of any nontrivial directed cycle is at least $k$.

Finally, to construct the required Cayley graph of undirected diameter at most $2$, use the argument above with $2k$ in place of $k$ to construct a Cayley graph $\textrm{Cay}(V, B)$, $B \subseteq V$, such that $B - B + B - B = V$ and the length of the shortest nontrivial directed cycle in the graph is at least $2k$. Now in $\textrm{Cay}(V, 2 \cdot B)$ a shortest nontrivial directed cycle has length at least $k$, and the undirected diameter of the graph is at most $2$, since $2 \cdot B - 2 \cdot B = V$. The claim is proved. $\square$

The examples above are Cayley graphs over abelian groups, so it would be interesting to know if it is possible to construct similar examples over groups which are far from being abelian, for example, over finite simple groups.