What's up in

Graph theory

Latest Articles

Q&A

The Computer Scientist Who Finds Life Lessons in Games

January 25, 2023

In Shang-Hua Teng’s work, theoretical and practical questions have long been intertwined. Now he’s turning his focus to the impractical.

Finally, a Fast Algorithm for Shortest Paths on Negative Graphs

January 18, 2023

Researchers can now find the shortest route through a network nearly as fast as theoretically possible, even when some steps can cancel out others.

How Do You Prove a Secret?

October 11, 2022

Zero-knowledge proofs allow researchers to prove their knowledge without divulging the knowledge itself.

Hypergraphs Reveal Solution to 50-Year-Old Problem

July 14, 2022

In 1973, Paul Erdős asked if it was possible to assemble sets of “triples” — three points on a graph — so that they abide by two seemingly incompatible rules. A new proof shows it can always be done.

He Dropped Out to Become a Poet. Now He’s Won a Fields Medal.

July 5, 2022

June Huh wasn’t interested in mathematics until a chance encounter during his sixth year of college. Now his profound insights connecting combinatorics and geometry have led to math’s highest honor.

Mathematical Connect-the-Dots Reveals How Structure Emerges

June 23, 2022

A new proof identifies precisely how large a mathematical graph must be before it contains a regular substructure.

Researchers Achieve ‘Absurdly Fast’ Algorithm for Network Flow

June 8, 2022

Computer scientists can now solve a decades-old problem in practically the time it takes to write it down.

Surfaces Beyond Imagination Are Discovered After Decades-Long Search

June 2, 2022

Using ideas borrowed from graph theory, two mathematicians have shown that extremely complex surfaces are easy to traverse.

Elegant Six-Page Proof Reveals the Emergence of Random Structure

April 25, 2022

Two young mathematicians have astonished their colleagues with a full proof of the Kahn-Kalai conjecture — a sweeping statement about how structure emerges in random sets and graphs.

Get highlights of the most important news delivered to your email inbox