Topics in Graph Theory

Lead Research Organisation: University of Oxford
Department Name: Mathematical Institute

Abstract

Graphs provide a useful structure to represent many real-world networks across a wide range of areas with examples including friendship links in social media, physical connections between servers on the Internet and the predator-prey relationships of an ecosystem. The structure of these graphs is often important on both the local and global level. For example, the presence of a clique of a given size in the graph is a local property, whereas the chromatic number of the graph is a global property, but both are often of interest. These two properties are also clearly linked, the chromatic number of a graph is at least as large as the size of the largest clique. It is therefore natural to ask whether a graph with a large chromatic number must have a large clique. This is not the case: we can construct graphs with arbitrarily high chromatic number which are triangle-free (this was originally proved by Tutte in the 1940s). However, given some additional information about the local structure, we can link the two. For example, the famous Strong Perfect Graph Theorem, proved by Chudnovsky, Robertson, Seymour and Thomas in 2006, says that, for a graph with no odd holes and no odd antiholes, the chromatic number equals the size of the largest clique.

In the last few years, there has been rapid progress on similar questions. One example is a well-known sequence of conjectures made by Gyarfas in the 1980s that have recently been proved: it is enough to consider graphs with no odd holes, or graphs with no long hole, or even graphs that do not have holes of lengths in every residue class mod k. There are a number of new techniques available, and it seems likely that it should be possible to push them further to prove more refined results about the local structure of graphs with large chromatic numbers. It also opens up further questions on what can be said about the constraints that local and global structure impose upon each other.

The proposed research will look to find new relationships between the local structure and global structure of graphs and to improve numerical bounds in cases where some relationship has already been shown. To obtain these results we will begin by applying existing techniques and methods to prove different links between the local structure and global structure. The research will then look to develop new methods to find more links and to improve already existing bounds. The results are likely to require a combination of extremal, structural and probabilistic methods.

This research falls into the EPSRC Mathematical Sciences area and, in particular, classes as extremal combinatorics, an area EPSRC is looking to maintain as an area of key UK strength.

Publications

10 25 50
publication icon
Groenland C (2020) Intersection sizes of linear subspaces with the hypercube in Journal of Combinatorial Theory, Series A

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509711/1 01/10/2016 30/09/2021
1941686 Studentship EP/N509711/1 01/10/2017 31/03/2021 Thomas Johnston
 
Description Suppose that a person walks on a square grid of roads following a list of random directions for an infinite amount of time. It is a classical result of Pólya that the person will almost surely return to where they started infinitely many times, but what happens if some of the roads are closed? In this case the walker will ignore any direction which takes them down a road which is closed and instead move on to the next direction. Since this is a subgraph of the grid, the person will again almost surely return to the start infinitely often for any fixed set of road closures. However, if an adversary can read the directions and choose which roads to close accordingly, I showed that, with probability 1, they can force the person to return only a finite number of times. In fact, I showed that an adversary can do this simultaneously for infinitely many walkers.

Motivated by a problem in quantum information, Melo and Winter considered the possible sizes of a k-dimensional subspace with the n-dimensional hypercube in Euclidean space. The largest intersection is clearly of size 2^k and the smallest has size 1, but what sizes in between are possible? Melo and Winter prove that the second largest intersection size is 3 ยท 2^(k-2), but they left open the problem of classifying the remaining "large" intersection sizes. By studying the structure of the "shape" hypergraphs and proving that they must take specific forms, I completely determined the large intersection sizes, showing that a conjecture of Melo and Winter was nearly true. By refining the argument I also showed that the largest "small" intersection sizes follow a similar pattern, which disproves another conjecture of Melo and Winter and shows that the intersection sizes are not as simple as they originally looked.

Recently I studied the problem of cyclically covering subspaces. By combining results from many different areas of pure maths I was able to determine the minimum size of a cyclically covering subspace for every Artin prime. This result is the combination of many areas of pure mathematics and requires rephrasing the problem in terms of polynomials, theorems from additive combinatorics, and studying cycles in directed Cayley graphs. This answered a question originally posed by Peter Cameron in 1991.
Exploitation Route The techniques used in proving these results may be applicable to a wide variety of different problems and could help other academics in solving problems across mathematics.
Sectors Digital/Communication/Information Technologies (including Software),Other