What's up in
Graph theory
Latest Articles
‘Stunning’ Percolation Proof Solves Decades-Old Puzzle About Phase Transitions
Mathematicians found that a broad class of networks will abruptly shift behavior past a critical point.
A Master of the Traveling Salesperson Problem Finds His Own Path
Shayan Oveis Gharan has won the Abacus Medal for using tools from across mathematics to boost the power of algorithms.
After 80 Years, Mathematicians Give Famed ‘Erdős Method’ an Upgrade
Decades ago, Paul Erdős used randomness to illuminate the vast and weird world of networks. Now mathematicians are making his technique even more powerful.
Networks Hold the Key to a Decades-Old Problem About Waves
Mathematicians are still trying to understand fundamental properties of the Fourier transform, one of their most ubiquitous and powerful tools. A new result marks an exciting advance toward that goal.
A New Bridge Links the Strange Math of Infinity to Computer Science
Descriptive set theorists study the niche mathematics of infinity. Now, they’ve shown that their problems can be rewritten in the concrete language of algorithms.
New Method Is the Fastest Way To Find the Best Routes
A canonical problem in computer science is to find the shortest route to every point in a network. A new approach beats the classic algorithm taught in textbooks.
Why the Key to a Mathematical Life is Collaboration
Fan Chung, who has an Erdős number of 1, discusses the importance of connection — both human and mathematical.
How Does Graph Theory Shape Our World?
Maria Chudnovsky reflects on her journey in graph theory, her groundbreaking solution to the long-standing perfect graph problem, and the unexpected ways this abstract field intersects with everyday life.
The Fastest Way Yet to Color Graphs
Researchers have devised a scheme for painting the edges of a graph that’s almost as speedy as possible.