Say you're throwing a dinner party and you want to have a nice mix.
If you want there to be at least three guests who know each other or at least
three who are strangers,
how many people do you need to invite?
The solution to this problem can be defined by what's called a Ramsey number.
Ramsey numbers are central to the field of math called graph theory.
Graph theory is a study of networks. Basically the question you ask is,
if you give me a certain system and maybe
you give me some information about the system,
what patterns can I expect?
Finding Ramsey numbers for networks
is one of the hardest problems in all of graph theory.
This year, in a surprise announcement...
I didn't know they were working on this before they invited me in,
so it was like a secret for we didn't tell anyone.
An international group of researchers revealed they made a major breakthrough on
the Ramsey Number Problem.
Networks can be abstracted as graphs,
basic structures consisting of collections of points called vertices,
connected by lines called edges.
Studying patterns in graphs can reveal the underlying structures of complicated
systems like computer networks or assist in problems like airline route
optimization.
When considering large graphs,
mathematicians like to ask: When will a pattern of a given size emerge?
This is where the Ramsey number comes in.
It's in some sense this threshold between order on the one hand and
randomness on the other.
Take a complete graph of N nodes where all the vertices are connected by edges.
Start coloring edges either red or blue.
The Ramsey number R of K is the point when structures or clique are forced to emerge.
The solution to the party problem turns out to be six guests,
which means the Ramsey number of three is six.
With six guests,
you are guaranteed to have a set or clique of three people who are either all friends
or all strangers.
What about the Ramsey number of four?
The answer is 18, but from here on it gets complicated.
We don't actually even know what the fifth Ramsey number is.
But for us, really the main and most exciting thing is the
growth. So as K grows, how does the Ramsey number grow?
In 1926, English mathematician,
Frank Ramsey introduced Ramsey numbers in a paper published just weeks before he died.
He showed the Ramsey number for any finite number is finite.
Five years later, Hungarian mathematician Paul Erdős,
who famously proposed hundreds of math problems alongside George Szekeres,
found an upper bound or limit for the Ramsey number.
12 years later, Erdős identified a lower bound.
They had bounds and they said it's between this and that,
but they didn't know the right answer. They didn't know the exact numbers.
Somehow everybody wanted to know what's the right number.
Someone amazingly, despite the interest and importance of this problem,
I mean there's an exponential gap between these two bounds.
Decades later, mathematicians, Julian Sahasrabudhe,
Rob Morris and Simon Griffiths decided to tackle the problem.
So it just seems like there's a lot there.
But there's sort of some important mystery hidden inside of this problem.
The team's first approach used a technique from Erdős and Szekeres' first bound proof.
The method sorts complete colored graphs in order to identify large cliques inside.
It works like this.
Start with any node.
Look at the connecting edges.
If there are more red ones,
then delete all the blue edges.
Put the original choice in the red bucket while still connected to the graph.
Put nodes with more blue edges in the blue bucket.
Repeat until everything is sorted.
To improve the efficiency of their clique sorting strategy,
the team turned to a tool called a book.
The book, it just says,
I want to try to take a bunch of red steps in the beginning.
By pulling out the monochromatic clique called the spine,
you can speed up the search for a large click with two easier searches.
It seemed that we had a viable approach fairly early on,
and it was just that,
we just need this one piece to make it all come together and it will all work.
We thought, okay, maybe in the first year we proved the piece, it was all fine,
but then later we collapsed.
In 2021,
graduate student Marcelo Campos joined the group to jumpstart the effort.
When I came in, they were working on it for three years already,
and we worked on it for two more years until we go to a solution.
Eventually, the team tried their techniques on a different problem,
a set of numbers called Off-Diagonal Ramsey numbers.
Basically what happens is we relate it to a very far off-diagonal Ramsey number,
and our algorithm actually works better on the off-diagonal.
This insight then led to an improved solution for Ramsey numbers.
By March, the team was ready to share their work publicly.
At first, we were just going to post the paper on arXiv, but then we thought,
okay, it might be nice to actually do some lectures.
And they all had very cryptic names,
"Recent Advances in Ramsey Theory" or something like that.
In three coordinated lectures across the globe from Oxford to Sao Paulo,
the team revealed their breakthrough.
I mean news spread like wildfire. By the time I walked out of the seminar,
my phone was blowing up.
The researchers succeeded in reducing the known upper bound of Ramsey numbers
exponentially.
After 80 years of trying,
this is the first improvement of this order of magnitude,
which is a very big deal.
So we have a new tool.
We developed this new algorithm for constructing books,
but we don't really know what other things it can be used for.
I think everybody is now trying to see what the technique does to their favorite problem.
That's what Feynman said,
every time I hear of a new idea, I try it on my three favorite problems.
Have a look at these tiles.
Can you tell whether any of these shapes might only fill a plane to infinity by
never repeating?
For more than half a century, mathematicians have sought a tile with this property,
what's called an aperiodic monotile.
This year, a tiling enthusiast together with a team of researchers published a remarkable
proof of it's existence.
There's no reason why this miracle should have happened.
It's all a bit of a blur to be honest.
Intricate tile patterns go back millennia from Roman mosaics to the geometric
patterns of Islamic palaces.
For researchers, the study of tiling theory is more than just an artistic pursuit.
Tilings are a good model for crystal structure,
the atomic structure of crystals and quasi crystals.
But the mathematics that leads to the monotile comes out of
the philosophy of logic.
The simplest tile patterns are ones that repeat like a checkerboard.
They're called periodic tilings.
But it's also possible to take this same set of two tiles and create patterns
that never repeat.
This is called non-periodic tiling.
But you could ask,
could I have a set of tiles that could make tilings of the plane,
but when they made the tilings,
those tilings were guaranteed to be non-periodic.
Infinitely tiling sets like this were repetition is impossible,
are called aperiodic.
In the 1960s,
graduate student, Robert Berger found
a tile set of more than 20,000 shapes
that could be combined to tile a plane, aperiodically.
His work set off a race to find an even smaller set.
By the 1970s Nobel Prize-winning physicist and mathematician,
Sir Roger Penrose
had discovered aperiodic tiling sets consisting of only two shapes.
The most famous of which are the kite and dart.
At the time, mathematicians wondered if it was possible to go even further.
It was natural to ask if you could get down to one shape.
But nobody knew how to do that,
and nobody knew how to prove that it was impossible.
This elusive shape was playfully named an 'Einstein' tile from a German
pun of the phrase for 'one piece.'
The question of whether an Einstein tile existed went unanswered for more than
50 years until David Smith,
a hobbyist interested in puzzles and tiling entered the picture.
Dave was just engaged in an open-ended exploration of
shapes and the kinds of interesting tilings they could create.
I've experimented with hundreds of shapes.
While playing around with a software tool called PolyForm Puzzlesolver.
Smith stumbled onto one especially interesting shape.
I thought, that's odd. I've not seen anything like that before.
And then I went on to cut out some shapes.
Dave glued the shapes together in larger and larger patterns until he hit the
limit of what he could do by hand.
Usually what happens is you find a periodic pattern early on.
But with this I didn't. But I didn't rule it out.
It was at this point he contacted computer scientist Craig Kaplan,
who creates pattern building software.
He said, can your software give us larger and larger patches of this shape
so that we can see whether the surrounding process eventually peters out or
whether it looks like we can keep going forever?
The shape Smith discovered can be constructed by subdividing,
a honeycomb grid of hexagons.
First connect the midpoints of the opposite sides of the hexagons.
This divides the hexagons into six smaller kites.
Smith's shape is made up of eight adjacent kites combined from neighboring hexagons.
The pair named the new shape the 'hat' tile.
With his software.
Kaplan constructed concentric rings of the hat tile finding no repeating patterns.
I was able very quickly with my software to go like, okay,
10 layers of surrounds, 12, 16.
It was around then that Dave said:
Could this be an answer to the so-called Einstein problem?
Kaplan and Smith knew they were onto something,
but to prove that the hat tile was in fact an aperiodic monotile,
they needed some assistance.
So they reached out to others in the tiling community,
mathematician Chaim Goodman-Strauss,
and software engineer Joseph Myers who took it from there.
In just over a week, they had a solution.
We've got to credit Joseph for bringing together the rest of the proof because
he, in record time, he just put all the pieces in order,
got it all lined up and said QED. It's true, it works.
Their proof involved piecing together tiles into recursively larger versions of
themselves
like this.
First, take the hat tile shape and create four metatiles named
H, T, P, F.
These four metatiles can be compiled into four larger versions of themselves
called supertiles.
Then these four supertiles can be combined into even larger supertiles,
eventually tiling the whole plane.
Remarkably, while the researchers were working on this proof,
Smith made another surprising discovery.
He sent me a second shape, one that we eventually called the 'turtle'.
And he said, his email was
amusingly apologetic. I'm sorry about this, but I think I have another one?
An analysis of the turtle shape by Myers led to a remarkable revelation.
Joseph stunned us by saying, the turtle is also aperiodic,
and then he said, in fact, the turtle and the hat are part of a continuum,
and all the shapes in that continuum are aperiodic and tile in the same way.
At either end of this continuum lie,
two unique tiles named the chevron and the comet,
both of which are periodic.
In between these outliers,
the hat and the turtle shapes fall on a continuum of an infinite set of 13-sided,
aperiodic tiles.
News of this discovery spread quickly.
This particular paper is probably one of the most heavily peer-reviewed
papers in existence.
We all downloaded it and we all read it immediately.
But amid all the attention came a specific criticism of their breakthrough.
After we put our hat paper online in March,
there was one objection to it that was raised more than any other.
About one seventh of the hats had to be flipped over.
To some, the two reflections of this one tile were,
in fact two different shapes and not a monotile.
Which begged the question:
Does there exist an aperiodic monotile that never uses reflection?
That's a fantastic follow-up question that we had no insight into.
Astonishingly less than a week after their initial paper was published,
Smith discovered another new shape.
I thought, well, it's got a lot more freedom than the others,
and all the sides are equal.
Dave said, well, hang on.
What if I force myself to tile with that shape,
never using reflection.
This intriguing shape dubbed the 'spectre' turned out to lie at the exact middle
of the hat-tile continuum.
Another round of analysis led to a proof that the spectre shape tiles the plane
aperiodically
without reflection.
A true Einstein tile.
Again, a miracle, no reason to expect that,
but just good luck that Dave stumbled onto it.
It still is a bit of a dream, to be honest.
Because I've always felt that
I wanted to discover something and it happened.
Given a set of numbers, say from one to a million,
how many can you choose from so that no three of them are equally spaced.
If you choose too many of them, and then unavoidably,
there are some three of them which are equally-spaced.
The study of number patterns like these is a central pursuit of the field of
additive combinatorics.
The biggest unsolved problem left at the moment is to do with
arithmetic progressions.
So it came as a shock when two computer scientists announced they'd made a
significant breakthrough on what's called the three arithmetic progression
problem blowing past the previous record.
It was a big surprise, and my immediate reaction was, of course, skepticism.
Graduate student, Zander Kelly, and associate professor Raghu Meka,
didn't set out to find this proof.
We were working on this problem called parallel repetition,
which is this classical question in theoretical computer science.
We thought it had connections to additive combinatorics.
We started digging into it, and that kind of led us to this problem.
It's a pretty famous problem. I mean,
certainly in pure math,
but also it's well-known in theoretical computer science because of the
techniques used to attack it.
An arithmetic progression of length
three is just three numbers with the same step in between them.
For example, 1, 2, 3,
or 3, 7, 11,
or 5, 10, 15.
So you just have three numbers, and then one of them is in the middle,
and it's exactly in the middle. It's the average of the other two.
The three progression problem dates back to 1936 to a paper by
mathematicians Paul Erdős and Paul Turán.
The pair wanted to know how many numbers smaller than some ceiling N can be put
in a set without creating any three term progressions.
In 1946,
a method was found to construct sets without producing these progressions,
giving mathematicians a floor to work with.
In 1953,
a ceiling was discovered,
a threshold beyond which a set must inevitably contain
a three-term progression.
Since then,
there has been only slow progress on lowering this ceiling.
As far as I know, the actual
fundamental technique itself seems to be suboptimal.
Zander and Meka looked through the existing body of work on the problem in search
of new approaches.
So the surprising thing I would say is some of the tools, or the main
set of tools, were there in previous works.
The pair combined two tools that hadn't been used together before on this problem.
The density increment strategy focuses on a structured window inside a set.
You find some subset of your set
where you can zoom in on that subset.
So you're shrinking the universe of what you're looking at.
The density of the set has increased.
We've made some progress in the sense that it's always easier to find a
three-progression in a denser set.
An algorithmic procedure called sifting
is used to find universes in which the set is dense.
So basically you start off with this set that you're trying to find three-term
progressions in, and it could look very chaotic.
So there's sort of numbers flying all over the place.
It takes the whole set and it shifts it by a random amount
in different directions, like a couple times.
It sifts out the noise, right? You're just left with this sort of kernel.
We're able to find this hidden structure planted inside.
With these combined tools,
Kelley and Meka were able to dramatically lower the ceiling on the three-progression problem.
But as outsiders to the field,
the pair sought input on their paper before publishing.
Just sent it to a couple people to see if they wanted to take
a look before we've released it publicly.
It was just like a pretty big claim, so.
Kelly sent his paper to mathematicians, Thomas Bloom and Olaf Sisasks,
the previous record holders on the problem.
Given the huge leap forward of the bound that they were claiming, I thought,
well, it can't be done that easily.
And then we basically spent the rest of the day on a Zoom call going through the
paper, and by the end of the day on Monday,
we were convinced that it was correct.
Yeah, so we're very excited about how these methods could be useful for
questions in, going back to theoretical computer science.
Questions in computational complexity, finding better algorithms.
But there've been so many cases even in the past year or two,
where out of nowhere there's this sort of decades old problem that's just been
sort of solved in a beautiful,
fantastic way
using tools that we thought weren't strong enough, and they are.