Articles
BY OUR STUDENT CONTRIBUTORS
Nitya Nigam After over 70 years of effort, mathematicians have finally made headway on one of graph theory’s most confounding puzzles. In September (sorry for the article backlog, we’ve been swamped), Asaf Ferber of UC Irvine and David Conlon of Caltech, published a proof that provides the closest approximation yet for “multicolour Ramsey numbers”, which are measures of how large graphs can get before they start to contain patterns. Graphs are groups of nodes (points) and edges (lines connecting the points) - Malhar’s articles on search algorithms make extensive use of these mathematical constructs. This development gives mathematicians a deeper understanding of the relationship between order and randomness in graphs, which is of fundamental importance to the field. As described by Maria Axenovich of the Karlsruhe Institute of Technology in Germany, “there are always clusters of order [in graphs], and the Ramsey numbers quantify it.” More specifically, the Ramsey number for a given pair of parameters (number of colours and clique size) is the minimum number of vertices a perfect graph can have for which it is impossible to colour the graph without having a monochromatic clique of the specific clique size. There’s a lot of unfamiliar terminology in this definition, so let’s unpack some of the words that are probably new to you in this context: Colour: In the context of Ramsey numbers, mathematicians are interested in finding out the ways in which the edges of a graph can be coloured. Colouring is essentially just a simple way to separate edges into distinct groups. Clique: A subset of vertices in a graph such that every vertex is connected to every other member of the subset via at least one edge. Monochromatic clique: A clique where all of the edges are the same colour. Perfect graph: A perfect graph of size k is a graph with k vertices where every vertex is connected to every other vertex by exactly one edge. Now that we understand these terms, let’s take a look at an example (diagrams from Quanta Magazine): Ramsey numbers are difficult to calculate because the complexity of a graph increases extremely quickly as vertices are added. There are simply too many ways to apply colours for these numbers to be calculated manually, and the task quickly becomes too complicated even for computers. In 1935, Paul Erdos and George Szekeres proved that the lower and bounds on 2-colour Ramsey numbers were sqrt(2)^t and 4^t respectively, where t is the clique size. Clearly, there is a huge difference between these bounds, especially as t gets large.
Using a mixture of deterministic and probabilistic methods (described both in this article and in the original paper - let us know in the comments if you’d like us to give you a more basic explanation of their methods), Ferber and Conlon improved Erdos’ lower bounds for the three- and four-colour cases from sqrt(3)^t and sqrt(4)^t = 2^t to 1.834^t and 2.135^t. While these not may seem like huge differences, these new bounds prove that exponentially larger 3- and 4-coloured graphs exist which don’t have monochromatic cliques of the specific sizes. Essentially, they established that disorder is present in larger graphs than was previously thought. Let us know in the comments if you'd like to learn more about Ramsey numbers of graph colouring!
0 Comments
Leave a Reply. |
Our AuthorsWe are high school and college students from around the world who are passionate about maths, and want to share that passion with others. Categories
All
|