Graph theory

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

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

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

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.

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.

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

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

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

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.