Monthly Archives: July 2011

In how many ways you can chose a committee of three students from a class of ten students?

The renewed interest in this old post, reminded me of a more recent event:

Question: In how many ways you can chose a committee of three students from a class of ten students?

My expected answer: {10} \choose {3} which is 120.

Alternative answer 1:(Lior)  There are various ways: you can use majority vote, you can use dictatorship (e.g. the teacher chooses); approval voting, Borda rule…

Alternative answer 2: There are precisely four ways: with repetitions where order does not matter; with repetitions where order matters; without repetitions where order matters; without repetitions where order does not matter,

Alternative answer 3: The number is truly huge. First we need to understand in how many ways we can choose the class of ten students to start with. Should we consider the entire world population? or just the set of all students in the world, or something more delicate? Once we choose the class of ten students we are left with the problem of chosing three among them.

Joe’s 100th MO question

MathOverflow is a remarkable recent platform for research level questions and answers in mathematics. Joe O’Rourke have asked over MO wonderful questions. (Here is a link to the questions) Many of those questions can be the starting point of a research project usually in discrete and computational geometry and sometimes in other areas. Many of the questions remained open, quite a few have led to definite quick solutions, and for many others substantial answers were offered. Usually Joe’s questions (and also his MO answers) contain beautiful and illuminating pictures. Amog the highlights: Joe’s question on Billiard knots; a poetic question about “light reflecting off christman-tree balls“; rolling a random walk on a sphere – with a definite answer by S. Carnahan; Pach animals of high genus; Fair irregular dice (with a nice answer by Bill Thurston); Parabolic envalope of fireworks; Coiling rope in a box;    A convex polyhedral analog of the pentagram map ; Random-polycube-shapes ; Which convex bodies roll along closed geodesics and many more. The 100th question is The rain hull and the rain ridge.

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.