## Project Details

### Description

The project will study certain infinite directed graphs with rich automorphism groups: primitive and with a high degree of transitivity on directed paths. The work will focus mainly on the case where the directed graphs have infinite in-valency and finite out-valency. Such directed graphs arise naturally as one of three cases in a rough categorization of infinite primitive permutation groups. Examples of these were first constructed in an ad hoc way about 10 years ago by the PI, but more recent work suggests that, rather surprisingly, there is a strong structure theory for them. The main aims are to construct new examples of highly arc transitive digraphs and primitive groups, to provide a partial classification of a natural subclass of these, and to study the group-theoretic structure of the resulting automorphism groups.

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.

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