Diophantine approximation, chromatic number, and equivalence classes of separated nets

In the branch of mathematics called combinatorics, a graph is an abstract object which can be thought of as a collection of points (called vertices), some of which are connected by line segments (called edges). We say that two vertices in a graph are adjacent if there in an edge connecting them. A colouring of a graph is a rule that assigns a label (called a colour) to each vertex, and the chromatic number of the graph is the minimum number of colours necessary to colour the graph so that no two adjacent vertices are the same colour.

Graph colourings have a multitude of practical applications. As an example, suppose you would like to invite a number of people for interviews on the same day but that there are certain pairs of candidates whom you don't want to interview at the same time. What is the minimum number of time slots that you need? Think of the candidates as the vertices of a graph, with an edge connecting one to another if they are to be put in different time slots. If we let our different colours represent different time slots, then answering our question is equivalent to determining the chromatic number of the graph. This is merely an example to demonstrate the ease with which one can turn a common logistics problem into a problem about graph colourings. There are many problems like this in biology, physics, industry, computer science, and in the social sciences and media (for example social networking). Part of our proposal is to identify these problems and to use our mathematical techniques to solve them.

Our approach to studying chromatic number is via an unexpected route. We will be considering the chromatic number of important families of infinite graphs, by connecting them with problems in Diophantine approximation (the study of approximation of numbers by fractions) and dynamical systems. This is a promising new direction which will push the boundary of current knowledge in mathematics and open the door for the flow of new ideas between many subjects.

The research in this proposal is mostly concentrated on problems in pure mathematics. Most of the impact that it will generate will be realized first in mathematics and the rest of the sciences. However there very well could be some non-academic impacts, and although we don't know ahead of time what applications we will find, we anticipate that some of the non-academic impacts could be:

1. A better understanding of deformation properties of certain metallic alloys and polymers: Some of the separated nets which come from the cut and project method (described in the Case for Support) give rise to aperiodic patterns in Euclidean space which actually occur naturally in special materials called quasicrystals. This remarkable and unanticipated discovery was made in the 1980s by Prof. Dan Shechtman, and he won the Nobel Prize for his discovery in 2011. Our results about separated nets imply that these quasicrystals can be deformed to a lattice structure, and this could have real world applications to materials science.

2. Increased efficiency in logistics, engineering, and computer processing: Many everyday problems can be written in terms of graph colorings in a way that chromatic number plays a prominent role. As a prototypical example, suppose you would like to invite a number of people for interviews on the same day but that there are certain pairs of candidates whom you don't want to interview at the same time. What is the minimum number of time slots that you need? We can think of the candidates as the vertices of a graph, with an edge connecting one to another if they are to be put in different time slots. Then if our different colors represent different time slots, our problem is equivalent to determining the chromatic number of the graph. This is merely an example to demonstrate the ease with which one can turn a common logistics problem into a problem about graph colorings. There are many problems like this in industry, computer science, and in the social sciences and media (for example social networking).

3. Helping to maintain the international standing and image of the UK as a leader in science in technology: The UK's strength in certain areas of mathematics (for example Diophantine approximation and dynamical systems) enhances our reputation and image in the eyes of the rest of the world, and it also helps us to attract and train the brightest students from around the world. This proposal will aid in strengthening existing world-class research in the UK, and it will lay the groundwork for new connections between mathematics and other disciplines.