Recent Comments
Vijay Vazirani on To cheer you up in difficult t… Vijay Vazirani on To cheer you up in difficult t… Gil Kalai on To cheer you up in difficult t… Victory Omole on To cheer you up in difficult t… To cheer you up in d… on Test Your Intuition (27) about… To cheer you up in d… on Jim Geelen, Bert Gerards, and… To cheer you up in d… on Timothy Chow Launched Polymath… Thomas Bloom on To cheer you up in difficult t… William Gasarch on To cheer you up in difficult t… Thomas Bloom on To cheer you up in difficult t… Gil Kalai on To cheer you up in difficult t… William Gasarch on To cheer you up in difficult t…
Tag Archives: Roth’s theorem
A Couple Updates on the Advances-in-Combinatorics Updates
In a recent post I mentioned quite a few remarkable recent developments in combinatorics. Let me mention a couple more. Independent sets in regular graphs A challenging conjecture by Noga Alon and Jeff Kahn in graph theory was about the number of … Continue reading
Posted in Combinatorics, Open problems, Updates
Tagged Independent sets in graphs, Roth's theorem
4 Comments
Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier
Click here for the most recent polymath3 research thread. I missed Tom by a few minutes at Mittag-Leffler Institute a year and a half ago Suppose that is a subset of of maximum cardinality not containing an arithmetic progression of length 3. Let . … Continue reading
Posted in Combinatorics, Open problems
Tagged Endre Szemeredi, Jean Bourgain, Klaus Roth, Roger Heath-Brown, Roth's theorem, Tom Sanders
10 Comments
Around the Cap-Set problem (B)
Part B: Finding special cap sets This is a second part in a 3-part series about variations on the cap set problem that I studied with Roy Meshulam. (The first post is here.) I will use here a different notation than in part … Continue reading
An Open Discussion and Polls: Around Roth’s Theorem
Suppose that is a subset of of maximum cardinality not containing an arithmetic progression of length 3. Let . How does behave? We do not really know. Will it help talking about it? Can we somehow look beyond the horizon and try to guess what … Continue reading
Posted in Combinatorics, Open discussion, Open problems
Tagged Cap sets, polymath1, Roth's theorem, Szemeredi's theorem
28 Comments
Pushing Behrend Around
Erdos and Turan asked in 1936: What is the largest subset of {1,2,…,n} without a 3-term arithmetic progression? In 1946 Behrend found an example with Now, sixty years later, Michael Elkin pushed the the factor from the denominator to the enumerator, … Continue reading
Posted in Combinatorics, Updates
Tagged Arithmetic progressions, Roth's theorem, Szemeredi's theorem
11 Comments
