Eccentricity in infinite tournaments

directed graphsgraph theoryinfinite-graphs

Definitions. A tournament is an oriented complete graph, that is, it's what you get by taking a (finite or infinite) complete graph and assigning a unique direction to each edge. If $T$ is a tournament, $V(T)$ is its set of vertices and $E(T)$ its set of (directed) edges. If $u,v$ are vertices of a tournament (or digraph for that matter), the distance $d(u,v)$ is the minimum length of a (directed) path from $u$ to $v$, so $d(u,u)=0$; we put $d(u,v)=\infty$ if there is no path from $u$ to $v$. The eccentricity of a vertex $u$ of a tournament $T$ is $e(u)=\sup\{d(u,v):v\in V(T)\}$.

Motivation. It is a common exercise in graph theory to show that every finite tournament has a vertex of eccentricity at most two. (In fact, an arbitrary tournament $T$ contains either a vertex $u$ with $e(u)\le2$ or else an infinite sequence of vertices $v_1,v_2,\dots,v_n,\dots$ such that $v_jv_i\in E(T)$ whenever $i\lt j$.) Thus the following problem is only of interest for infinite tournaments.

Problem 1. Show that, if a tournament has a vertex of finite eccentricity, then it has a vertex of eccentricity at most three.

Problem 2. Find a tournament in which the eccentricity of every vertex is exactly three.

Context. These problems occurred to me after considering this question about finite tournaments. They are rather easy but I found them amusing, maybe you will too.

Best Answer

Problem 1. Show that, if a tournament has a vertex of finite eccentricity, then it has a vertex of eccentricity at most three.

Solution. Let $u$ be a vertex with $e(u)=n\lt\infty$, and suppose $n\gt3$. Choose a vertex $w$ with $d(u,w)=n$. Now consider any vertex $v$. If $d(u,v)\le n-2$ then $d(w,v)=1$; if $d(u,v)=n-1$ then $d(w,v)\le2$; and if $d(u,v)=n$ then $d(w,v)\le2$. Hence $e(w)\le3$.

By the way, for a simple example of a strongly connected tournament with no vertex of finite eccentricity, take $V(T)=\mathbb N$ and $E(T)=\{(u,v):v=u+1\text{ or }v\lt u-1\}$.


Problem 2. Find a tournament in which the eccentricity of every vertex is exactly three.

Solution. Let $V(T)=\mathbb N$ and $E(T)=\{(u,v):v\equiv u+1\pmod3\}\cup\{(u,v): v\equiv u\pmod3,\ v\lt u\}$. Then $e(u)=d(u,u+3)=3$ for every vertex $u$.