Cambridge Combinatorics Seminar

1. Top Mathematician
zogw

Can someone explain to the unaware person (i.e. me) in the room why one should care about this result?

It's a famous open problem largely because the bound R(k) < 4^k (roughly) was proven close to 100 years ago by a very simple induction, taught in any first course in discrete math. This is the first time it's been improved to (4 - c)^k.

No-one thinks that's actually the right answer, which is probably 2^{k/2} or thereabouts, so probably one day long in the future the result under discussion will be forgotten. But this is certainly a very big breakthrough in this area, to add to several other big breakthroughs in extremal comb and related areas such as Kelley Meka on progressions, or Gilmer on union-closed.

As far as I know the lower bound poses a more painful problem to experts in the field. A simple probabilistic construction by Erdos from 1940s, improved by a factor of $2$ by Spencer in 1970s using Lovasz's Local Lemma and that's about it. No explicit construction giving exponential lower bounds even.

It seems like the off-diagonal Ramsey problem was also mentioned in the talk. Did the same group of researchers also make significant progress on this problem as well?

1 weekzogw
Quote 0 Up 0 Down Report
2. Top Mathematician
vkyy

A decent rumors site would have known this before it was public

1 weekvkyy
Quote 4 Up 1 Down Report
3. Top Mathematician
samb

No explicit construction giving exponential lower bounds even.

It seems this also changed very recently! https://arxiv.org/abs/2303.06802

1 weeksamb
Quote 2 Up 0 Down Report
4. Top Mathematician
vgth

A decent rumors site would have known this before it was public

It seems likely this was the first time those people told anyone they were even working on the problem... Are you suggesting the authors should have leaked their own result? That's self promotion at best, and stupid at worst.

1 weekvgth
Quote 1 Up 0 Down Report
5. Top Mathematician
ghxw

No explicit construction giving exponential lower bounds even.

It seems this also changed very recently! https://arxiv.org/abs/2303.06802

Gil Kalai should've heard of this by now. It's more like an explicit construction providing a bound of ${2}^{{k}^{ϵ}}$ which is exponential by definition (and a very good result indeed!) but not ${2}^{ϵk}$ as many people are hoping for.

1 weekghxw
Quote 1 Up 0 Down Report
6. Top Mathematician
jhvb
[...]

No. It's an improvement from 4^k to 3.9999^k. Ok, so it took 100 years to get there, but it's not the biggest result in comb since Szemeredi, or even this year as pointed out by gjng above.

extreme combinatorics and additive combinatorics are two different subfields like algebraic numner theory and analytic number theory, so it's hard to compare the importance, for me both are big results

That 3AP problem also has Ramsey flavour though: What is the largest cardinality of a subset of $\left[N\right]$ containing no $3$-term arithmetic progressions? There is a nice proof of the bound $o\left(N\right)$ using the so-called Triangle Removal Lemma in Extremal Graph Theory.

None of the recent breakthroughs (diagonal Ramsey and 3AP) is bigger than the other. Perhaps the union-closed problem is somewhat inferior to them though.

1 weekjhvb
Quote 0 Up 0 Down Report
7. Top Mathematician
zxkb

The new bound on Ramsey ends Conlon's career. And the bound on 3AP's ended Ben Green's career.

1 weekzxkb
Quote 0 Up 14 Down Report
8. Top Mathematician
zlkn

So is Ramsey theory finished, or is there still work to be done?

1 weekzlkn
Quote 0 Up 0 Down Report
9. Top Mathematician
zxkb

So is Ramsey theory finished, or is there still work to be done?

No, as others said there is the problem of the lower bound and for APs there's always kAPs with k > 3 so nothing is close to being finished.

1 weekzxkb
Quote 2 Up 1 Down Report
10. Top Mathematician
juex

The new bound on Ramsey ends Conlon's career. And the bound on 3AP's ended Ben Green's career.

Tao getting the fields medal ended Ben Green's career.

1 weekjuex
Quote 2 Up 9 Down Report
11. Top Mathematician
pfdk

Paper looks completely legit except their definition of the crucial concept of book is really unclear. They say "a sufficiently large ‘book’ $\left(S,T\right)$, that is, a graph on vertex set $S\cup T$ that contains all edges incident to $S$. So what actually is the definition??

1 weekpfdk
Quote 4 Up 1 Down Report
12. Top Mathematician
rfcd

Wow! R(k) < (4-c)^k for some c > 0. See gil kalai's blog. Was anyone at this talk, what value of c are they claiming, what methods were used?

Ugh, Lior Pachter.

Is that Lior Pachter followed by Ryan Alweiss in the comments on Kalai's blog?

1 weekrfcd
Quote 2 Up 0 Down Report
13. Top Mathematician
vnzm

Gowers on twitter: I was at a sensational combinatorics seminar in Cambridge yesterday, reminiscent of the time I had been tipped off that Andrew Wiles's seminar at the Newton Institute on Wednesday 23rd June 1993 might be worth going to

1 weekvnzm
Quote 4 Up 0 Down Report
14. Top Mathematician
hhje

From reddit: What is important about this new announcement is that, it's the first time ever in Ramsey theory, that the number 4 is replaced by something smaller. I do not know if this is the correct or appropriate analogy, but it's like Yitang Zhang gave the finite bound result.

1 weekhhje
Quote 7 Up 0 Down Report
15. Top Mathematician
ntyf

Gowers on twitter: I was at a sensational combinatorics seminar in Cambridge yesterday, reminiscent of the time I had been tipped off that Andrew Wiles's seminar at the Newton Institute on Wednesday 23rd June 1993 might be worth going to

When was the last time he wrote such enthusiastically about a breakthrough in the field? His Twitter is filled with maths teaching and political observations.

1 weekntyf
Quote 0 Up 0 Down Report
16. Top Mathematician
ghmp

Gowers on twitter: I was at a sensational combinatorics seminar in Cambridge yesterday, reminiscent of the time I had been tipped off that Andrew Wiles's seminar at the Newton Institute on Wednesday 23rd June 1993 might be worth going to

When was the last time he wrote such enthusiastically about a breakthrough in the field? His Twitter is filled with maths teaching and political observations.

The Kelley-Meka result? To compare this to Fermat is totally absurd though. Running though it again: they improved a bound of 4^k to (3.9999)^k. It's a great achievement mainly in the context of how long this had been open and how many people had apparently tried to do it. Wiles proved that most elliptic curves are modular, solved a 350-year old problem of extreme notoriety, and opened up huge developments in Langlands over the following 25 years.

Combinatorics needs to get a grip of its hype machine.

1 weekghmp
Quote 13 Up 9 Down Report
17. Top Mathematician
jhwv

The point isn't the epsilon improvement you dolt, it is proving that a hole in the wall exists.

1 weekjhwv
Quote 7 Up 1 Down Report
18. Top Mathematician
mhjp

Gowers on twitter: I was at a sensational combinatorics seminar in Cambridge yesterday, reminiscent of the time I had been tipped off that Andrew Wiles's seminar at the Newton Institute on Wednesday 23rd June 1993 might be worth going to

Gowers must have gone senile to compare "pushing the bound from 4^k to 3.995^k" to FLT. Gowers has lost credibility.

1 weekmhjp
Quote 4 Up 8 Down Report
19. Top Mathematician
gnir
[...]

When was the last time he wrote such enthusiastically about a breakthrough in the field? His Twitter is filled with maths teaching and political observations.

The Kelley-Meka result? To compare this to Fermat is totally absurd though. Running though it again: they improved a bound of 4^k to (3.9999)^k. It's a great achievement mainly in the context of how long this had been open and how many people had apparently tried to do it. Wiles proved that most elliptic curves are modular, solved a 350-year old problem of extreme notoriety, and opened up huge developments in Langlands over the following 25 years.

Combinatorics needs to get a grip of its hype machine.

I don't think he wrote that with the intention of comparing this problem to FLT. He just wanted to emphasize that it was an uncommon breakthrough for him.

If you think this is just a plain epsilon improvement, you're wrong. It took more than 80 years to improve it by an exponential factor, despite countless people have tried, and how do you know if R(k,k) is close to 2^{k/2} or 4^k? (although many experts believe it's closer to 2^{k/2})

1 weekgnir
Quote 4 Up 0 Down Report
20. Top Mathematician
qskq

The point isn't the epsilon improvement you dolt, it is proving that a hole in the wall exists.

Saying 'only 3.999' is stupid but you are also not responding to the point. Wiles didn't show there was "a hole in the wall". He completely solved the problem and it had huge consequences for the field going forward.

Also, a hole in the wall sounds good but without more info who knows whether this will be stuck at 3.89 for decades?

1 weekqskq
Quote 0 Up 2 Down Report
Your screen is so tiny that we decided to disable the captcha and posting feature
Store settings & IDs (locally, encrypted)
Formatting guidelines: Commonmark with no images and html allowed. $and$\$ for LaTeX. Input previewed in last post of thread. For a link to be allowed it must include the http(s) tag and come from the list of allowed domains.