## Project Details

### Description

Graphs and directed graphs are simple and pervasive mathematical objects which are studied both for their potential applications and for their intrinsic mathematical interest. Often these two viewpoints interact, but the emphasis in this project is on the latter. A graph consists of a set of vertices, certain pairs of which are joined by edges. In a directed graph (or digraph), the edges have a direction on them. For example, one could have a graph where the vertices represent certain towns and the edges represent roads between them. In a directed graph the roads would be one-way.

When studying a class of mathematical objects, it is often fruitful to focus on the objects in the class which possess a high degree of symmetry. Here we focus on highly arc transitive digraphs: ones where for any two directed paths of the same length in the digraph there is a symmetry of the digraph which moves one path to the other. In particular, the descendant set of a vertex, that is the collection vertices which can be reached by a directed path starting at the vertex, will look the same for all vertices in the digraph and will also have a high degree of symmetry.

In general there is no hope of describing all highly arc transitive digraphs, though there are many interesting open questions which can be asked about them. However, there is a natural subclass where recent work suggest a possibility of being able to classify the descendant sets, and doing this is one of the main aims of the project. This is where the group of symmetries of the digraph is also primitive on the set of vertices, and where there are only finitely many directed edges coming out of each vertex. In this case, the descendant sets look approximately like a finitely-branching tree, but this is only a crude approximation, as if looking at the structure from a distance, and it is important to have a better understanding of the real picture here. The project will also study properties of the groups of symmetries of highly arc transitive digraphs and investigate generalisations which assume less arc transitivity.

The main beneficiaries of the project will be other mathematicians, particuarly those interested in combinatorics, group theory and logic.

Status | Finished |
---|---|

Effective start/end date | 15/06/09 → 14/12/11 |

### Funding

- Engineering and Physical Sciences Research Council: £180,092.00