Finding trees in tournaments

 

mug_2018_image1The 2018 School of Mathematics mug featured the problem displayed above - on this page you can find solutions and more.

Further explanation

This problem is about embeddings of directed graphs. A directed graph (or digraph for short) consists of a set of points called vertices and a set of edges, where each edge is directed from one vertex to another vertex.

A tree is a connected graph which contains no cyclesand an oriented tree is a digraph formed by giving a direction to each edge of a tree. The digraph T shown on the mug is an example of an oriented tree. Since this problem is about directed graphs, for the rest of this page we simply say tree to mean oriented tree.

A complete graph is a graph in which there is an edge between every pair of vertices, and a tournament is a digraph formed by giving a direction to each edge of a complete graph. The digraphs G1G2, and G3 shown on the mug are examples of tournaments.

Whether you can find a copy of a given digraph within another given digraph is a fundamental question of graph theory, and the mug depicts one instance of this problem: can you find a copy of T in G for G = G2 and G = G3? This means that you must map each vertex x of T to a vertex f(x) of G so that

  1. different vertices of T map to different vertices of G, i.e. if x ≠ y then f(x) ≠ f(y), and
  2. the directions of edges are respected, meaning that if there is an edge in directed from x to y then there must be an edge in G directed from f(x) to f(y).

The bold edges in the tournament G1 show where you can find a copy of T in G1; the image below makes clear which vertex maps to which in this copy.

mug_2018_image5

Solution

One way to find the tree T in the tournaments G2 and G3 is shown below (these are not the only solutions).

mug_2018_image2

 

 

 

What about other tournaments on 5 vertices?

In fact, the tree T depicted is unavoidable, meaning that it is contained in every tournament on the same number of vertices (in this case, five). This can be proved by hand using a case analysis or by running all possibilities through a computer. Indeed, there are 12 different tournaments on five vertices*. These 12 tournaments are shown below, along with the tree T in each of them.

 All 5-vertex tournaments

* = here we count two tournaments as being the same if you can transform one to the other simply by rearranging the vertices, which makes sense for this problem since if one contains a copy of T then the second must also.

Not all trees are unavoidable, as shown in the diagram below: the tree on the left is a star, in which all edges are directed outwards from a central vertex. This is not contained in the tournament on the right, since the central vertex of the tree has four edges directed outwards from it, whilst every vertex in the tournament has only two vertices directed outwards from it.

mug_2018_image4

What is the wider significance?

We have seen that some trees (like the tree on the mug) are unavoidable, whilst others (like the star) do not have this property. It is natural to ask if this property of trees is typical or unusual. Bender and Wormald conjectured in 1988 that the former is true, i.e. that almost all trees are unavoidable. More precisely they proposed that if we choose a tree T with vertices 1, 2, ... , n uniformly at random (meaning that every tree is equally likely to be chosen) then the probability that T is unavoidable tends to one as n tends to infinity.

In support of this conjecture Bender and Wormald showed that almost all trees are 'almost-unavoidable', meaning that they are contained in almost all tournaments on the same number of vertices.

In recent research Dr Richard Mycroft and Tássio Naia (both University of Birmingham) proved this conjecture by using structural methods to break up a given tournament into parts and then applying a randomised embedding algorithm to embed T within these parts. This research will be published in the journal Random Structures & Algorithms, and you can find a preprint of the paper at the following link: www.arxiv.org/abs/1609.03393 

An open problem

There remain many interesting open questions about finding trees in tournaments, such as the following example. A binary tree of depth d is formed as follows. Take a single vertex as the root, and then add two edges directed outwards from this vertex to two new vertices. Next, for each of the new vertices add two edges directed outwards from this vertex to two additional new vertices. The binary tree of depth d is the tree obtained by d rounds of additions of this type; is this unavoidable? It seems likely that this is the case for every d ≥ 3, but a proof remains elusive.

To find out more about cutting-edge mathematics research at the University of Birmingham, please follow the link below:

School of Mathematics Research