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.
