Tag Archives: Roth’s theorem

A Couple Updates on the Advances-in-Combinatorics Updates

Posted on July 10, 2011 by Gil Kalai

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 , | 4 Comments

Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier

Posted on November 24, 2010 by Gil Kalai

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 , , , , , | 12 Comments

Around the Cap-Set problem (B)

Posted on May 11, 2009 by Gil Kalai

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 →

Posted in Combinatorics, Open problems | Tagged , , | 4 Comments

An Open Discussion and Polls: Around Roth’s Theorem

Posted on March 25, 2009 by Gil Kalai

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 , , , | 30 Comments

Pushing Behrend Around

Posted on July 10, 2008 by Gil Kalai

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 , , | 15 Comments