Fri. Oct 18th, 2019

A young Russian denies a conjecture with more than half a century of life | Science


Almost coinciding with his 30th birthday (it was last June 3), the name of Yaroslav Shitov has appeared in a good part of the world press. This young Russian has proven that a conjecture with more than half a century of life on a problem of graph theory is false, giving a counterexample, that is, providing a case in which what the conjecture predicted that always happened is not fulfilled.

Graphs are one of the simplest and, at the same time, most versatile structures of mathematics, with a large number of applications (from the design of communications networks, to the distribution of goods and planning of production). They are composed of two types of elements: vertices or points, and edges, which are pairs of points. A graph is usually represented by a drawing in which the vertices are points in the plane and the edges are segments that join them.

A graph formed by six vertices and seven edges.


A graph formed by six vertices and seven edges.

One of the most studied problems in this field is to find the minimum number of colors that can be assigned to the vertices in such a way that there are no two with the same color that are joined by an edge.

A coloring of the previous graph using three colors that, in addition, you can verify that it uses the minimum number of possible colors


A coloring of the previous graph using three colors that, in addition, you can verify that it uses the minimum number of possible colors

The problem of graph coloring is often used to classify objects or to optimize processes. For example, vertices can be tasks to be completed by a set of workers, and an artist between two vertices indicates that those two tasks must be performed by the same worker, or that they are incompatible for some other reason. If each color represents a time slot, we can ensure that the tasks represented in the previous graph need at least three time slots to complete.

The history of graph coloring is very extensive and can be traced back to the mid-nineteenth century when Francis Guthrie (or his brother) conjectured that any graph that can be drawn on the plane so that two different edges do not intersect, except in one common vertex, you can always color with four colors or less. This is the call problem of the map of the four colors, which was definitely solved by mathematicians Kenneth Appel and Wolfgang Hanken in 1976, more than 125 years later.

Although they look like children's games, coloring problems can be dauntingly complicated: determining if a graph can be colored with less than a fixed amount of colors is an NP-complete problem. This means that if they give us a possible color, we can check whether they have less than the colors they ask for and if it is valid, but it is extremely difficult to find that color if they do not give it to us. Therefore, if we find an algorithm that efficiently solves the problem of coloring graphs (with an amount of operations less than an amount related to the number of vertices of the graph), we can go to the Clay Institute and claim a million dollars, because we will have shown that P is different from NP, and with that one of the famous problems of the millennium and that they are assigned that prize. If any of the readers has the algorithm but does not understand why it implies that P is different from NP, the authors of this article offer to clarify the doubts. Sharing part of the prize, of course.

Stephen Hedetniemi.


Stephen Hedetniemi.

Given the complication of coloring problems, an advance would be to know what is the minimum number of colors needed for some types of graphs. And in this context appears the Hedetniemi conjecture. In 1966 Stephen Hedetniemi conjectured in his doctoral thesis that given two graphs G and H, the number of colors needed to color the graph tensor product GXH is the smallest of the colors needed to color G and H. This graph is obtained by combining in a certain way the vertices and edges of G and H.

This was true for all the examples that had been found until a month ago, but nobody had been able to prove it formally. And for a good reason: because it is false. The young Russian mathematician Shitov has found two graphs G and H such that his tensor product needs fewer colors than those required to color both G and H, thus demonstrating that the conjecture of Hedetniemi is false.

Examples G and H of Shitov are huge graphs: it is possible that G has 2200 vertices, which is an immense number, of an order of magnitude close to the number of elementary particles that we can find in the entire visible universe. But H is even bigger, much bigger, with more than 220000 vertices. In fact he does not build them explicitly in his short article (two and a half pages). But it shows that they exist on the basis of known properties, with which the problem is solved.

Alberto Márquez is Professor of Applied Mathematics of the Sevilla University

Agate A. Timón G Longoria is responsible for Communication and Disclosure in the Institute of Mathematical Sciences (ICMAT)

Coffee and Theorems is a section dedicated to mathematics and the environment in which they are created, coordinated by the Institute of Mathematical Sciences (ICMAT), in which researchers and members of the center describe the latest advances in this discipline, share points of contact between the mathematics and other social and cultural expressions and remind those who marked their development and knew how to transform coffee into theorems. The name evokes the definition of the Hungarian mathematician Alfred Rényi: "A mathematician is a machine that transforms coffee into theorems".

Editing and coordination: Agate Rudder (ICMAT).

You can follow Matter in Facebook, Twitter, Instagram or subscribe here to our newsletter

(tagsToTranslate) young (t) Russian (t) disprove (t) guess (t) medium (t) century (t) life (t) discovery (t) suppose (t) new (t) advance (t) color ( t) graph



Source link