Monthly Archives: March 2009

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

A Proposal Regarding Gilad Shalit

Since an agreement for the release of Gilad Shalit in exchange for the release of Hamas prisoners could not be reached, I propose to initiate negotiations (perhaps with Egyptian help) on the improvement of Gilad Shalit’s captivity conditions.

In return for letting Shalit have frequent visits of the red cross,  letter exchange and perhaps also visits by his family, Israel can offer the release  of many dozens of prisoners, such as Hamas Parliament members, and other prisoners not directly involved in violent activities.

מאחר שלא ניתן היה להגיע להסכמה על שחרור גלעד שליט תמורת שחרור אסירים, יש לנסות לפתוח משא ומתן (למשל באמצעות המצרים) רק על שיפור תנאי השבי של גלעד שליט ואפילו להיות מוכנים לשחרר אסירים כמו עשרות חברי הפרלמנט של חמאס שנעצרו  תמורת שיפור תנאי השבי בלבד -מכתבים, ביקורי צלב אדום, ואם ניתן ביקורים של המשפחה


Gilad Shalit 

Colorful Caratheodory Revisited



Janos Pach wrote me:   “I saw that you several times returned to the colored Caratheodory and Helly theorems and related stuff, so I thought that you may be interested in the enclosed paper by Holmsen, Tverberg and me, in which – to our greatest surprise – we found that the right condition in the colored Caratheodory theorem is not that every color class contains the origin in its convex hull, but that the union of every pair of color classes contains the origin in its convex hull. This already guarantees that one can pick a point of each color so that the simplex induced by them contains the origin. A similar version of the colored Helly theorem holds. Did you know this?”

I did not know it. This is very surprising! The paper of Holmsen, Pach and Tverberg mentions that this extension was discovered independently by  J. L. Arocha, I. B´ar´any, J. Bracho, R. Fabila and L. Montejano.

Let me just mention the colorful Caratheodory agai. (we discussed it among various Helly-type theorems in the post on Tverberg’s theorem.)

The Colorful Caratheodory Theorem: Let S_1, S_2, \dots S_{d+1} be d+1 sets in R^d. Suppose that x \in conv(S_1) \cap conv (S_2) \cap conv (S_3) \cap \dots \cap conv (S_{d+1}). Then there are x_1 \in S_1, x_2 \in S_2, \dots x_{d+1} \in S_{d+1} such that x \in conv (x_1,x_2,\dots,x_{d+1}).

And the strong theorem is:

The Strong Colorful Caratheodory Theorem: Let S_1, S_2, \dots S_{d+1} be d+1 sets in R^d. Suppose that x \in conv(S_i \cup S_j)  for every 1 \le i <j \le d+1. Then there are x_1 \in S_1, x_2 \in S_2, \dots x_{d+1} \in S_{d+1} such that x \in conv (x_1,x_2,\dots,x_{d+1}).

Janos, whom I first met thirty years ago,  and who gave the second-most surprising introduction to a talk I gave, started his email with the following questions:

“Time to time I visit your lively blog on the web, although I am still not quite sure what a blog is… What is wordpress? Do you need to open an account with them in order to post things? Is there a special software they provide online which makes it easy to include pictures etc? How much time does it take to maintain such a site?”

These are excellent questions that may interest others and I promised Janos that I will reply on the blog. So I plan comments on these questions in some later post. Meanwhile any comments from the floor are welcome.

A Beautiful Garden of Hypertrees

We had a series of posts (1,2,3,4) “from Helly to Cayley” on weighted enumeration of Q-acyclic simplicial complexes. The simplest case beyond  Cayley’s theorem were Q-acyclic complexes  with n vertices, {n \choose 2} edges, and {{n-1} \choose {2}} triangles. One example is the six-vertex triangulation of the real projective plane. But here, as in many other places, we are short of examples.

Nati Linial,  Roy Meshulam and Mishael Rosenthal wrote a paper with very surprising examples of Q-acyclic simplicial complexes called “sum complexes”. The basic idea is very simple: The vertices are \{1,2,\dots , n\}. Next you pick three numbers a,b and c and consider all the triples i,j,k so that i+j+k is either a or b or c. And let’s assume that n is a prime.

So how many triangles do we have? A fraction of 3/n of all possible triangles which is what we want ({{n-1} \choose {2}}).

If the three numbers form an arithmetic progression then the resulting simplicial complex is collapsible. In all other cases it is not collapsible. The proof that it is Q-acyclic uses a result of Chebotarëv on Fourier analysis. (So what does Fourier analysis have to do with computing homology? You will have to read the paper!) The paper considers the situation in all dimensions.

What about such combinatorial constructions for Q-homology spheres?

Extremal Combinatorics on Permutations


We talked about extremal problems for set systems: collections of subsets of an n element sets, – Sperner’s theorem, the Erdos-Ko-Rado theorem, and quite a few more. (See here, here and here.) What happens when we consider collections of permutations rather than collection of sets? Not so much is known on extremal problems for families of permutations.

David Ellis, Ehud Friedgut, and Haran Pilpel have recently proved an old conjecture of Deza and Frankl regarding an analog for permutations of the Erdos-Ko-Rado Theorem. They showed that for every k if n is sufficiently large, any family of permutations on an n-element set such that every two permutations in the family agree in at least k places, contains at most (n-k)! permutations.

The proof uses spectral methods and representations of the symmetric group.

Polymath1: Success!


 polymath” based on internet image search

And here is a link to the current draft of the paper.

Update:  March 26, the name of the post originally entitled “Polymath1: Probable Success!” was now updated to “Polymath1: Success!” It is now becoming clear that there are  three (perhaps four) new emerging proofs of DHJ. (April 2: See this post by Terry Tao. As this update was also based on briefly talking with Terry,  Terry’s new post gives a better description on the state of affairs and relations between the different proofs.)

The proof directly emerged from the project indeed looks conceptually different and simpler than all other proofs, and may indeed lead to the simplest known proof for Szemeredi’s theorem. (But for this we will have to wait for the details.) In addition, there is a new Ergodic proof by Tim Austin, which was partially inspired by and which used (among several other ingredients developed by Austin) some ideas and  results discovered in the polymath project. Both the original  ergodic proof and Austin’s proof were (at least roughly) “combinatorialized”. 

In what sense was it a massive open collaboration? It is true that in the crucial phases of polymath, the phases where two concrete strategies for proofs were considered, the number of pivotal participants was not large. But there was an initial phase were probably more than a hundred mathematicians took part as observers and as commentators. The comments in this early phase played some role in the later developments but what is more important is that this stage have led to the (emerging) selection of the team that developed the proof. Among the hundreds, those who felt they have ideas that can be crucial, or methods that could be helpful, and were smart or lucky to be correct,  and had the persistence to follow these ideas and how these ideas can be combined with other ideas, became the pivotal players. The team that played the game was not so large, but the main massive ingredient of the project which accounts for its accessive mathematical power was in the “draft”. The team emerged from a massive number of participants. (So if you believe there were 10 pivotal players out of a hundred, think about the emergence of the team among {{100} \choose {10}}  possible (but, of course, not equally plausible) teams, as a point were  polymath had extra power.) 

Two related posts: Tim Gowers raised inthis post  interesting questions regarding the possibility of projects were the actual number of provers will be massive. Here on my blog we have a post  with an “open discussion”  on what are the correct bounds for Roth type problems.  The emphasis is on “small-talk discussion” and not on actual “hard-nose researching”.

We took the opportunity to spend three days of “Purim” visiting northern Israel. Coming back I saw two new posts on Tim Gowers’s blog entitled “Problem solved probably” and “polymath1 and open collaborative mathematics.” It appears that “polymath1” has led to a new proof for the density version of Hales-Jewett’s theorem for k=3 which was the original central goal! Also it looks like the open collaboration mode (while not being a massive collaboration) was indeed useful.

Perhaps the most important thing is to make sure that a complete proof for the k=3 case is indeed in place (as these famous problems sometimes “fight back,” as Erdos used to say).  The outline is described here. If everything is OK as Tim and other participants expect, there are already some discussions or even plans about an extension to the general k case. This seems to be the next major step in the project.  There are also other fruits from the various threads of the polymath1 project. Overall, this looks very exciting! The mathematical result is a first-rate achievement, and the mode of cooperation is novel, interesting and appears genuinely useful.

Let me quote what Tim writes about it: “Better still, it looks very much as though the argument here will generalize straightforwardly to give the full density Hales-Jewett theorem. We are actively working on this and I expect it to be done within a week or so. (Work in progress can be found on the polymath1 wiki.) Better even than that, it seems that the resulting proof will be the simplest known proof of Szemerédi’s theorem.” sababa!