What's up in

# graph theory

## Latest Articles

### A Very Big Small Leap Forward in Graph Theory

Four mathematicians have found a new upper limit to the “Ramsey number,” a crucial property describing unavoidable structure in graphs.

### The Number 15 Describes the Secret Limit of an Infinite Grid

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.

### How Randomness Improves Algorithms

Unpredictability can help computer scientists solve otherwise intractable problems.

### The Colorful Problem That Has Long Frustrated Mathematicians

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

### Quantum Field Theory Pries Open Mathematical Puzzle

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

### The Computer Scientist Who Finds Life Lessons in Games

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

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?

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

### Hypergraphs Reveal Solution to 50-Year-Old Problem

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.