Graph decompositions via probability and designs

点击翻译按钮获取中文摘要

The notion of decomposition, or splitting a larger object into smaller pieces, is ubiquitous in mathematics. Sometimes one does this to better understand the larger object, for example representing a function by a Fourier series, or factorising an integer. On the other hand, we may wish to understand which pieces can possibly partition a given larger object. With which shapes can we tile the plane? Is it possible to 'decompose' the computationally expensive operation of division into only addition, subtraction and multiplication (as in an algorithm used by a computer to divide real numbers)? This proposal seeks to investigate these problems in graphs, or networks. A graph is a collection of nodes in which some pairs are joined by edges, to represent some relationship or connection between them. More complicated relationships are encoded by hypergraphs, where more than two nodes can lie in an edge together. Graphs are used to model and describe many different systems in biology, communications and computer science and their theoretical study comes under the mathematical field of combinatorics.In the graph setting, the goal of a decomposition problem is to start with a large 'host' graph with many edges, and a collection of 'guest' graphs each with few edges, and to try to fit the guest graphs perfectly into the host graph, using each edge exactly once. This type of problem is one of the oldest in combinatorics, going back to a 1792 question of Euler. The case where each guest graph contains few nodes is by now fairly well-understood and constitutes the area of design theory. This project investigates the other end of the spectrum where guest graphs may contain a number of nodes comparable with the host graph. An example of such a question that can be expressed in the language of graphs, the recently solved Oberwolfach problem, asks for a sequence of seating plans which allow each person in a group to sit next to each other person exactly once over the course of several meals.Very recent successes in this area, including work in which I was involved, solved a number of longstanding conjectures and overcame the barriers met in previous works by novel application of tools from disciplines outside of combinatorics. I seek to build on these successes and draw from tools in probability and design theory to obtain graph decompositions. For example, an effective strategy has been to use a randomised algorithm that makes successive coin flips to choose where to put each guest edge; tools from probability are needed to analyse its evolution. Such an algorithm is very unlikely to be able to place the final pieces correctly; tools from design theory will help complete the decomposition.