Articles
BY OUR STUDENT CONTRIBUTORS
Nitya Nigam Graph theory is having a great year. Following the proof of lower bounds on Ramsey numbers (link is to our coverage) from Asaf Ferber and David Conlon in late 2020, a new proof has proved a special case of the Erdős-Hajnal conjecture. Essentially, the conjecture implies that forbidding certain structures at a small scale impacts the macroscopic structure of the graph, which has powerful consequences for graph theory (we'll go into more detail later in the article). The new proof, published in February by Maria Chudnovsky and Paul Seymour of Princeton University, Alex Scott of the University of Oxford, and Sophie Spirkl of the University of Waterloo, proves two special cases of the conjecture, so although a complete proof still evades us, significant progress is being made. More formally, the Erdős–Hajnal conjecture states that if a graph does not contain a certain structure (known as an induced subgraph), then the graph will inevitably have either a large clique or a large independent set. Let's define these terms: 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. Independent set: A subset of vertices in a graph such that every vertex in the subset is not connected to any of the other vertices in the subset. Large: A large clique or independent set in a certain graph with V vertices is defined as a clique or independent set with more vertices than would arise if a random graph with V vertices was drawn. Chudnovsky and her colleagues proved the conjecture for two special cases. One was the specific forbidden induced subgraph of a "five-cycle" - a set of 5 vertices where each vertex is connected to exactly two others in the set. The other was a "five-cycle with a hat" - a set of 6 vertices similar to a 6-cycle, but with an extra edge joining two vertices (shown on the left). While most conjectures are formed with mathematical consensus agreeing they are likely to be true, the mathematicians working on this problem actually expected that they would disprove the conjecture: that is, that it would be false. “We were all a little shocked,” said Chudnovsky. Prior to this paper, the conjecture had only been proven true for induced subgraphs of four vertices or fewer, as well as another special 5-vertex subgraph ("The Bull" below) by Chudnvosky and Shmuel Safra in 2005. This leaves just the five-vertex path as the last possible five-vertex induced subgraph, and the clear next step for eventually proving the full conjecture. “The five-vertex path has to be next. If you can’t do that, you’re still nowhere,” said Paul Seymour. We're excited to see what developments are still to come!
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
|