Graphs and groups

Groups are mathematical objects that can be understood as an abstract model for symmetry. While the concept has been around since the 19th century, group theory is still a very active research field. This is due to the fact that symmetry plays a central role not only in mathematics, but also in natural sciences such as physics and chemistry as well as in computer science. In geometric group theory, we don`t investigate abstract group properties directly, but look at Cayley graphs instead. Cayley graphs are geometric objects which encode information about the structure of the group. In general there are many different Cayley graphs for a group. A geometric group property in this context is a property of those Cayley graphs which only depends on the underlying group and not on the specific choice of the graph. Some particularly interesting geometric group properties are closely related to random processes taking place on those graphs. Originally motivated by physical applications the study of such processes has now taken a mathematical life of its own and has become an active and fast growing branch of mathematics. The project Graphs and groups aims to contribute to our understanding of random processes on Cayley graphs. This will be achieved by two complementary lines of research: The first part of the project continues ongoing research on the structure of so called graph wreath products of groups. We are interested in those products mainly because they can potentially be utilised to construct groups with unexpected properties. Among other things this could lead to a counterexample to a conjectured connection between the cost and l2-Betti numbers of groups. The second part of the project is concerned with substructures of Cayley graphs that could greatly simplify studying random processes on Cayley graphs. Specifically we aim to find certain suitably embedded substructures (grids and trees) of Cayley graphs. Since random processes are rather well understood on grids and trees this will lead to a significantly better understanding of random processes on more general Cayley graphs.

Graphs are mathematical structures consisting of nodes (also called vertices) and connections between these nodes (called edges). They can be seen as abstract models of networks, but also as approximations of geometric spaces by picking some points in the geometric space as nodes and connecting any two them by an edge when they are near each other. Groups are algebraic structures that capture the notion of symmetry. This includes everyday notions such as mirror symmetry, but but also more complex notions; usually any structure preserving map is considered a symmetry. There is a rich interplay between graphs and groups. Some of the most interesting graphs have the property that they are highly symmetric, that is, they look similar everywhere; moreover, groups can be studied through their Cayley graphs, these are graphs encoding a lot of information about the group. Most graphs and groups studied throughout this project were infinitely large, in fact, some of the main outcomes are only meaningful if the structures are infinite. More precisely, our main results deal with graphs which can be disconnected into two infinite parts by removing a finite number of vertices. It is known that such graphs can be built by gluing together smaller graphs in a tree-like manner. The first main result says that for highly symmetric graphs this can be done in a way that all parts are highly symmetric and connected, and the parts and the ways they are glued together `look alike'. Such decompositions can be powerful tools in the study of highly symmetric graphs. Assume that a problem is easy to solve for the parts. If we would like to solve it for the glued-together graph, it suffices to investigate how the solutions fit together at the gluing positions. The second main result constitutes an application of the above procedure. A self-avoiding walk on a graph is a process where we move along edges from vertex to vertex, but never visit the same vertex twice. In order to study asymptotic properties of this process, it is crucial to know the approximate number of self-avoiding walks of a given length; however, there are only few graphs where this number is known. We were able to show that any self-avoiding walk can be glued together from so-called configurations on the parts of the decomposition; if all parts are finite this provides a means to calculate the number of self-avoiding walks. For instance, it allows us to compute the number of self-avoiding walks on any Cayley graph of any group which has the property of being virtually free (which we will not define here); it moreover enables us to link self-avoiding walks on such groups to certain formal languages.