What's up in
Graph theory
Latest Articles
Tinkertoy Models Produce New Geometric Insights
An upstart field that simplifies complex shapes is letting mathematicians understand how those shapes depend on the space in which you visualize them.
Universal Method to Sort Complex Information Found
The nearest neighbor problem asks where a new point fits into an existing data set. A few researchers set out to prove that there was no universal way to solve it. Instead, they found such a way.
Four Is Not Enough
How many colors do you need to color an infinite plane so that no points 1 unit apart are the same color?
First Big Steps Toward Proving the Unique Games Conjecture
The latest in a new series of proofs brings theoretical computer scientists within striking distance of one of the great conjectures of their discipline.
Decades-Old Graph Problem Yields to Amateur Mathematician
By making the first progress on the “chromatic number of the plane” problem in over 60 years, an anti-aging pundit has achieved mathematical immortality.
The Tricky Translation of Mathematical Ideas
Big advances in math can happen when mathematicians move ideas into areas where they seem like they shouldn’t belong.
A Simple Visual Proof of a Powerful Idea
Ramsey’s theorem predicts a surprising (and useful) consistency in the organization of graphs. Here’s a simple visual proof of how it works.
Graph Isomorphism Vanquished — Again
Just five days after posting a retraction, László Babai announced that he had fixed the error in his landmark graph isomorphism algorithm.
Complexity Theory Problem Strikes Back
The legendary graph isomorphism problem may be harder than a 2015 result seemed to suggest.