What's up in

graph theory


Universal Method to Sort Complex Information Found

August 13, 2018

The nearest neighbor problem asks where a new point fits into an existing data set. A few researchers set out to prove that there was no universal way to solve it. Instead, they found such a way.

Illustration for "Four Is Not Enough"
Quantized Academy

Four Is Not Enough

June 18, 2018

How many colors do you need to color an infinite plane so that no points 1 unit apart are the same color?

Lede art for "First Big Steps Toward Proving the Unique Games Conjecture"
computational complexity

First Big Steps Toward Proving the Unique Games Conjecture

April 24, 2018

The latest in a new series of proofs brings theoretical computer scientists within striking distance of one of the great conjectures of their discipline.

Illustration of 826-vertex graph for "Decades-Old Graph Problem Yields to Amateur Mathematician"
graph theory

Decades-Old Graph Problem Yields to Amateur Mathematician

April 17, 2018

By making the first progress on the “chromatic number of the plane” problem in over 60 years, an anti-aging pundit has achieved mathematical immortality.

Abstractions blog

The Tricky Translation of Mathematical Ideas

June 28, 2017

Big advances in math can happen when mathematicians move ideas into areas where they seem like they shouldn’t belong.

Abstractions blog

A Simple Visual Proof of a Powerful Idea

April 13, 2017

Ramsey’s theorem predicts a surprising (and useful) consistency in the organization of graphs. Here’s a simple visual proof of how it works.

Illustration: boxing gloves
Abstractions blog

Graph Isomorphism Vanquished — Again

January 14, 2017

Just five days after posting a retraction, László Babai announced that he had fixed the error in his landmark graph isomorphism algorithm.

Illustration: boxing glove & graph
Abstractions blog

Complexity Theory Problem Strikes Back

January 5, 2017

The legendary graph isomorphism problem may be harder than a 2015 result seemed to suggest.

Computer Science

Landmark Algorithm Breaks 30-Year Impasse

December 14, 2015

Computer scientists are abuzz over a fast new algorithm for solving one of the central problems in the field.