EPSRC logo

Details of Grant 

EPSRC Reference: EP/L001462/1
Title: Diophantine approximation, chromatic number, and equivalence classes of separated nets
Principal Investigator: Haynes, Dr A
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Mathematics
Organisation: University of Bristol
Scheme: Standard Research
Starts: 01 July 2013 Ends: 30 September 2013 Value (£): 228,143
EPSRC Research Topic Classifications:
Algebra & Geometry Logic & Combinatorics
Mathematical Analysis
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
22 May 2013 Developing Leaders Meeting - CAF Announced
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.bris.ac.uk