Author: Adam Zhang
Institution: Georgia Institute of Technology
Mathematicians at Georgia Tech have recently announced a proof for graph theory's Kelmans-Seymour Conjecture. The conjecture, proved by mathematician Xingxing Yu and his team, goes as follows: "If a graph is 5-connected and non-planar, then G has a TK5."
Though Yu's proof itself encompasses over 120 pages and four distinct papers, we can begin to interpret the conjecture by examining its parts. We start with a graph and, thereby, the study of graph theory. Research in graph theory is used to analyze systems in every domain, ranging from mapping biochemical reactions mechanisms to analyzing follower-followed relationships on social media.
"Graph Theory is used, for example, in designing microprocessors and the logic behind computer programs. It's helpful in detailed networks to get quick solutions that are reasonable and require low complexity," says Xingxing Yu (1).
A graph is composed of nodes, or vertices, that represent distinct entities connected by lines, or edges, to denote a connection. From here we can visualize a graph with five vertices, but what does nonplanar mean? A planar graph is one that can be drawn in such a way that no edges cross each other, so it follows that a non-planar graph contains intersecting edges. This becomes important in things like plane flight paths that may intersect in limited airspace, or designing circuits in electronic devices. In microprocessors, electrons travel down large tangles of connecting paths, and a single meeting of different paths would short the entire processor. To model these systems, they need to be optimized, which would mean they need to be simplified.
"You want to get as close to planar as you can in these situations," says Yu.
A graph is connected if there is a path between two vertices; connectivity denotes the minimum number of elements that need to be removed to disconnect all remaining elements (3), making this very important for network flow problems. Therefore, a k-vertex-connected graph, or k-connected graph, has more than k vertices and still remains connected when fewer than k vertices are removed (4). This brings us to TK5 graphs, which are smaller subgraphs of a K5 graph, pictured below:
By asserting that this type of graph is always present given a series of constraints, we can get quicker solutions in very detailed networks to achieve more efficient solutions.
The conjecture was first proposed in 1977 by Paul Seymour at Princeton, and Alexander Kelmans independently formulated the conjecture just two years later. Robin Thomas, now a Regents' Professor at Georgia Tech, began working on the proof in the 90s. He now heads the Algorithms, Combinatorics and Optimization graduate program at Georgia Tech and, in 2010, was appointed Regents' Professor, the highest academic rank awarded in the University System of Georgia.
“I tried moderately hard to prove the Kelmans-Seymour conjecture in the 1990s, but failed,” Thomas said.
However, Thomas was able to pass on insights to his then postdoc Xingxing Yu. Now a professor in the School of Mathematics, Yu picked up the problem ten years later.
“Around 2000, I was working on related concepts and around 2007, I became convinced that I was ready to work on that conjecture,” Yu said.
He planned to involve graduate students but waited a year to develop a more structured and coherent approach. He eventually took on graduate student Jie Ma in 2008 to work on the proof, making significant headway. Yan Wang and Dawei He joined later in 2010, and together the research group published the first half of the proof and completed the rest shortly after. The team has since submitted two papers and are in the process of submitting two more.
If this proof is true, it will confirm Mader's proof of Dirac's Conjecture and inch us closer to a proof of the Hajos conjecture. However, even now the race to the proof continues as other researchers look for ways to break and tear the proof. Wang isn't worried, though.
“We spent lots and lots of our time trying to wreck it ourselves and couldn’t, so I hope things will be fine,” he said (4).
Sources
- http://www.news.gatech.edu/2016/05/23/40-year-math-mystery-and-four-generations-figuring
- D. He, Y. Wang and X. Yu, The Kelmans-Seymour conjecture I, special separations, Submitted.
- D. He, Y. Wang and X. Yu, The Kelmans-Seymour conjecture II, 2-vertices in K4-, Submitted.
- https://cosmosmagazine.com/mathematics/maths-mystery-solved-after-40-years