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.