We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.
Quanta Homepage
  • Physics
  • Mathematics
  • Biology
  • Computer Science
  • Topics
  • Archive

What's up in

graph theory

Latest Articles

Shang-Hua Teng in a blazer on a street
Q&A

The Computer Scientist Who Finds Life Lessons in Games

By Ben Brubaker
January 25, 2023
Comment
Read Later

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

graph theory

Finally, a Fast Algorithm for Shortest Paths on Negative Graphs

By Ben Brubaker
January 18, 2023
Comment
Read Later

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

cryptography

How Do You Prove a Secret?

By Sheon Han
October 11, 2022
Comment
Read Later

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

combinatorics

Hypergraphs Reveal Solution to 50-Year-Old Problem

By Leila Sloman
July 14, 2022
Comment
Read Later

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 with a polyhedron.
2022 Fields and Abacus Medals

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

By Jordana Cepelewicz
July 5, 2022
Comment
Read Later

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.

Points connected by lines.
graph theory

Mathematical Connect-the-Dots Reveals How Structure Emerges

By Leila Sloman
June 23, 2022
Comment
Read Later

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

Aerial view of a complicated interchange full of flowing traffic
networks

Researchers Achieve ‘Absurdly Fast’ Algorithm for Network Flow

By Erica Klarreich
June 8, 2022
Comment
Read Later

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

An illustration of a person walking across a surface with many holes.
topology

Unimaginable Surfaces Discovered After Decades-Long Search

By Leila Sloman
June 2, 2022
Comment
Read Later

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

Three circles that have dots connected by lines, as in a graph.
graph theory

Elegant Six-Page Proof Reveals the Emergence of Random Structure

By Jordana Cepelewicz
April 25, 2022
Comment
Read Later

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.


Previous
  • 1
  • 2
  • 3
  • 4
  • ...
  • 5
Next
Follow Quanta
Facebook
Facebook

Twitter
Twitter

Youtube
YouTube

Instagram
Instagram

RSS
RSS

Newsletter

Past Month

Most Read Articles

This Data is Current Loading...
This Data is Current Loading...
This Data is Current Loading...
The Quanta Newsletter

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

Recent newsletters
Quanta Homepage
Facebook
Twitter
Youtube
Instagram

  • About Quanta
  • Archive
  • Contact Us
  • Terms & Conditions
  • Privacy Policy
  • Simons Foundation
All Rights Reserved © 2023