Graph theory

The “packing coloring” problem asks how many numbers are needed to fill an infinite grid so that identical numbers never get too close to one another. A new computer-assisted proof finds a surprisingly straightforward answer.

Unpredictability can help computer scientists solve otherwise intractable problems.

The four-color problem is simple to explain, but its complex proof continues to be both celebrated and despised.

Mathematicians have struggled to understand the moduli space of graphs. A new paper uses tools from physics to peek inside.

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.