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 independent sets in regular graphs. The conjecture asserts that the number of independent sets in an N-vertex d-regular graph is at most (2^{d+1}-1)^{N/2d}. Alon proved in 1991 a weaker form of the conjecture that was posed by Granville. Kahn proved in 2001 the conjecture for bipartite graphs. In 2010, Yufei Zhao, an undergraduate student, proved the conjecture.  (The number of independent sets in a regular graph, Combinatorics, Probability and Computing 19 (2010), 315-320. A link to the arxived paper.) The proof is based on a surprising reduction to the bipartite case.  Zhao’s result came as a surprise to several experts in the field who were working on this problem.

Around Roth’s theorem

The second development is about Roth’s theorem that we often discuss (E.g., here, and here and here).

Suppose that R_n is a subset of \{1,2,\dots, n \} of maximum cardinality not containing an arithmetic progression of length 3. Let g(n)=n/|R_n|. The gap between the upper and lower bounds for g(n) is exponential. Can we look behind the horizon and make an educated guess about the true behavior of g(n)?

recent paper entitled “Roth’s theorem in many variables” by Tomasz Schoen and  Ilya D. Shkredov contains a remarkable piece of evidence which is strong enough for me to update my beliefs on the problem.

Schoen and Shkredov proved that if a subset A of {1, 2,…, N} has no nontrivial solution to the equation x_1+x_2+x_3+x_4+x_5=5y then the cardinality of A is at most N e^{-c(log N)^{1/7-t}}, where t>0 is an arbitrary number, and c>0 is an absolute constant. In view of the well-known Behrend construction their estimate is close to best possible.

Roth’s theorem is about the equation x_1+x_2=2y. I used to think that much better bounds than Behrend are quite possible. (But I was aware that most experts have the opposite view.) Schoen and Shkredov’s result is a strong piece of evidence that the truth is near the Behrend’s bound. Two comments: First, if there are conceptual differences between the case of 6 variables and the case of 3 variables I will be happy to know about them.   Second, additional interesting examples of sets without 3-term AP are still very welcome.

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 R_n is a subset of \{1,2,\dots, n \} of maximum cardinality not containing an arithmetic progression of length 3. Let g(n)=n/|R_n|.

Roth proved that g(n) \ge log logn. Szemeredi and Heath-Brown improved it to g(n) \ge log^cn for some 0″ src=”http://l.wordpress.com/latex.php?latex=c%3E0&bg=ffffff&fg=000000&s=0″ alt=”c>0″ /> (Szemeredi’s argument gave c=1/4.) Jean Bourgain improved the bound in 1999 to c=1/2 and in 2008 to c=2/3 (up to lower order terms).

Erdös and Turan who posed the problem in 1936 described a set not containing an arithmetic progression of size n^c.  Salem and Spencer improved this bound to g(n) \le e^{logn/ loglogn}. Behrend’s upper bound from 1946 is of the form g(n) \le e^{C\sqrt {\log n}}. A small improvement was achieved recently by Elkin and is discussed here.  (Look also at the remarks following that post.)

In an earlier post we asked: How does g(n) behave? Since we do not really know, will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is? (I still don’t know if softly discussing this or other mathematical problems is a fruitful idea, but it can be enjoyable.)

We even had a poll collecting people’s predictions about g(n).  Somewhat surprisingly 18.18% of answerers predicted that g(n) behaves like (\log n)^c for some c<1. Be the answer as it may be, reaching  the logarithmic barrier was considered extremely difficult.

A couple of months ago Tom Sanders was able to refine Bourgain’s argument and proved that g(n) \ge (\log n)^{3/4}. Very recently Tom have managed to reach the logarithmic barrier and to prove that

g(n) \ge (\log n)/(\log \log n)^{5}.

Quoting from his paper: “There are two main new ingredients in the present work: the first is a way of transforming sumsets introduced by Nets Katz and Paul Koester in 2008, and the second is a result on the L_p-invariance of convolutions due to Ernie Croot and Olof Sisask (2010).”

This is a truly remarkable result.

Continue reading

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 A to make it compatible with various posts of polymath1 which consider similar objects. We write \Gamma(n) = \{0,1,2\}^n and \Gamma_{a,b,c} denotes all vectors of length n with a 0’s, b 1’s and c 2’s.

An affine line are three vectors x,y,z so that x_i + y_i + z_i = 0 (mod~3) for every i. A cap set is a subset of \Gamma(n) without an affine line. The cap set problem asks for the maximum size of a cap set. For information on the cap set problem itself look here.  For questions regarding density of sets avoiding other types of lines look here.

In the first part we considered the case that n=3m and considered “modular lines” , i.e., three vectors  x,y,z so that the number of solutions to x_i+y_i+z_i=a(mod~3)  is divisible by m for every a. When n is divisible by 9 the Frankl-Rodl theorem implies that a subset of \Gamma with more than (3-\epsilon)^n elements must contain a modular line, and even a modular line with two equal elements. (Question: does the same statement follow from Frankl-Rodl theorem when n is divisible by 3 and not by 9?) 

10. Some propositions in the desired direction.

Proposition 6:  Suppose that n=3m, and that m=1 (mod~3). If every set of size > (3-\epsilon)^n has a modular line, then every set of size > (3-\epsilon)^n has a modular line which is either an affine  line, or  the number of is such that x_i + y_i + z_i =a is precisely m for a=0,1,2.

(So we can get rid of a few “types” of modular lines which are not really affine  lines, but not all of them.)

Proposition 6 follows from the much more transparent  proposition:

Proposition 7:  There are sets of constant density which do not contain a modular line \{x,y,z\} for which the numbers of solutions of x_i + y_i + z_i =a(mod~3) for a=0,1,2 is never a permutation of (0,m,2m).

Proof: Consider all vectors where the sum of the coordinates is zero modulo 3. This property is preserved under sums but it does not hold for the sums we are looking at. (All the quantities: 0+m+4m, 0+0 +4m, 0+2m+2m, 0+2m+0, m, 2m are not divisible by 3.)  

11. A strong variant form of the problem

Here are innocent-looking variants of Problem 1: (the existence of modular lines)

Problem 6:  How large can a set F in \Gamma(7m)  be without three vectors x, y and z such that |\{i:x_i+y_i+z_i=a\}|=o(mod~m)  for a=0,1,2,3,4,5,6?

Problem 7:  How large can a set F in \Gamma (7m)  be without three vectors x, y and z such that |\{i: x_1+y_i+z_i=a\}| = m for every a=0,1,2,3,4,5,6? Continue reading

An Open Discussion and Polls: Around Roth’s Theorem

Suppose that R_n is a subset of \{1,2,\dots, n \} of maximum cardinality not containing an arithmetic progression of length 3. Let g(n)=n/|R_n|.

How does g(n) behave? We do not really know. Will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is?

Update 1: for the discussion: Here are a few more specific questions that we can wonder about and discuss.

1) Is the robustness of Behrend’s bound an indication that the truth is in this neighborhood.

2) Why arn’t there analogs for Salem-Spencer and Behrend’s constructions for the cup set problem?

3) What type of growth functions can we expect at all as the answer to such problems?

4) Where is the deadlock in improving the upper bounds for AP-free sets?

5) What new kind of examples one should try in order to improve the lower bounds? Are there some directions that were already extensively explored?

6) Can you offer some analogies? Other problems that might be related?


Continue reading

Pushing Behrend Around

Erdos and Turan asked in 1936: What is the largest subset S of {1,2,…,n} without a 3-term arithmetic progression?

In 1946 Behrend found an example with |S|=\Omega (n/2^{2 \sqrt 2 \sqrt {\log_2n}} \log^{1/4}n.)

Now, sixty years later, Michael Elkin pushed the the log^{1/4} n factor from the denominator to the enumerator, and found a set with  |S|=\Omega (n \log^{1/4}n/2^{2 \sqrt 2 \sqrt {\log_2n}} ). !

Here is a description of Behrend’s construction and its improvment as told by Michael himself:

“The construction of Behrend employs the observation that a sphere in any dimension is convexly independent, and thus cannot contain three vectors  such that one of them is the arithmetic average of the two other. The new construction replaces the sphere by a thin annulus. Intuitively, one can produce larger progression-free sets because an annulus of non-zero width contains more integer points than a sphere of the same radius does. However, Continue reading