Gil Kalai’s blog

## A Couple Updates on the Advances-in-Combinatorics Updates

Posted on July 10, 2011 by

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)?

A 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.

### Like this:

This entry was posted in Combinatorics, Open problems, Updates and tagged Independent sets in graphs, Roth's theorem. Bookmark the permalink.

### 4 Responses to A Couple Updates on the Advances-in-Combinatorics Updates

1. Terence Tao says:

Well, on a technical level the key improvement is that iterated sumsets such as A+A+A+A are much “smoother” than single sum sets A+A, in that the former are known to contain large structured sets (e.g. generalised arithmetic progressions or Bohr sets), whereas the latter can still have a lot of “holes”. Consider for instance the case when A is a subset of Z/NZ of the form $B \backslash -B$, where B is a random set of density 1/2. Then A has density 1/4 but A+A omits 0; nevertheless, A+A+A (and larger sumsets) are almost certain to fill up all of Z/NZ.

The equation $x_1+\ldots+x_5=5x_6$ is basically the assertion that the dilate $5 \cdot A$ cannot “hide” in the holes of the five-fold sumset $A+A+A+A+A$ (modulo a little technicality involving the trivial solutions). This will be a lot harder to be possible if, say, $A+A+A+A$ does not have many holes. In contrast, the set $A \hat{+} A$ (sums of distinct elements of A) has a lot more holes, and it is a priori conceivable that $2 \cdot A$ manages to completely miss this set.

Nevertheless, this is indeed a very nice psychological and conceptual breakthrough. The main tool is Sander’s near-solution to the polynomial Freiman-Ruzsa conjecture. It does raise the hope that further progress on the PFR conjecture will be useful in getting better bounds on other additive combinatorics problems.

• Gil Kalai says:

Dear Terry, this is very interesting. Probably it is very hard “to look behind the horizon” and all we can say is that Behrend’s bound would be tight unless we can eventually come up with a new type of construction showing otherwise. I think that for the cap set problem (say over $F_p^n$ it is not known that you can prove an upper bound of $(p-t)^n$ (for t>0) even if you consider one equaltion with many variables as Schoen and Shkredov do.

2. Yufei Zhao says:

I feel very honored to see my result featured on your blog. Thanks!
GK: My pleasure, Yufei

3. harrison says:

While I don’t mean to downplay Yufei’s result, it’s worth noting that we still can’t prove the analogous conjecture for other homomorphisms, in even as simple a case as 3-colorings. (Galvin and Tetali proved it for bipartite graphs using a method similar to Kahn’s, but Yufei’s reduction trick doesn’t work — although he does have, I believe, a preprint extending his method as far as it’ll go, it doesn’t work for colorings.)

Again, I don’t mean to insult anyone with that statement (although maybe I’d be insulted most of all, as I spent last summer doing an REU in which I tried to extend Yufei’s trick to 3-colorings) — it just seems to me to be a classic example of a problem which sounds like it should be much easier than it actually is. It’s definitely very interesting stuff, though!

• ### Blogroll

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 17, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9273872971534729, "perplexity_flag": "middle"}