Category Archives: Open problems

A Few Mathematical Snapshots from India (ICM2010)

Can you find Assaf in this picture? (Picture: Guy Kindler.)

In my post about ICM 2010 and India I hardly mentioned any mathematics. So here are a couple of mathematical snapshots from India. Not so much from the lectures themselves but from accidental meetings with people. (Tim Gowers extensively live-blogged from ICM10.) First, the two big problems in analysis according to Assaf Naor as told at the Bangalore airport waiting for a flight to Hyderabad.  Next, a lecture on “proofs from the book” by Günter Ziegler. Then, some interesting things I was told on the bus to my hotel from the Hyderabad airport by François Loeser, and finally what goes even beyond q-analogs (answer: eliptic analogs) as explained by Eric Rains. (I completed this post  more than two years after it was drafted and made major compromises on the the quality of my understanding of the things I tell about. Also, I cannot be responsible today for the 2-year old attempts at humor.)

The two big problems in analysis according to Assaf, and one bonus problem

Continue reading

Looking Again at Erdős’ Discrepancy Problem

Over Gowers’s blog Tim and I will make an attempt to revisit polymath5. Last Autumn I prepared three posts on the problems and we decided to launch them now. The first post is here. Here is a related MathOverflow question. Discrepancy theory is a wonderful theory and while I am not an expert we had several posts about it here. (This post on Beck-Fiala and related matters; and this news item on Beck’s 3-permutation conjecture.) I am aware of at least one important recent development in the theory that I did not report.  My posts go around the problem and do not attack it directly but I hope people will have a chance to think about the problem again and perhaps also about polymathing again. Meanwhile, polymath7 (over the polymath blog) is in a short recess but I hope a new research thread will start soon.

Satoshi Murai and Eran Nevo proved the Generalized Lower Bound Conjecture.

Satoshi Murai and Eran Nevo have just proved the 1971 generalized lower bound conjecture of McMullen and Walkup, in their  paper On the generalized lower bound conjecture for polytopes and spheres . Let me tell you a little about it. For more background see the post: How the g-conjecture came about.

Face numbers and h-numbers

Let P be a (d-1)-dimensional simplicial polytope and let f_i(P) be the number of i-dimensional faces of P. The fvector (face vector) of P is the vector f(P)=(f_{-1}(P),f_0(P),f_1(P),...).

Face numbers of simplicial d-polytopes  are nicely expressed via certain linear combinations called the h-numbers. Those are defined by the relation:

\sum_{0\leq i\leq d}h_i(P)x^{d-i}= \sum_{0\leq i\leq d}f_{i-1}(P)(x-1)^{d-i}.

What’s called “Stanley’s trick” is a convenient way to practically compute one from the other, as illustrated in the difference table below, taken from Ziegler’s book `Lectures on Polytopes’, p.251:

1

1           6

1          5            12

1          4           7            8

h= (1        3          3            1)

Here, we start with the f-vector of the Octahedron (1,6,12,8) (bold face entries) and take differences as shown in this picture to end with the h-vector (1,3,3,1).

The Euler-Poincare relation asserts that h_d(P)=(-1)^{d-1}\tilde{\chi}(P)=1=h_0(P). More is true. The Dehn-Sommerville relations state that h(P) is symmetric, i.e. h_i(P)=h_{d-i}(P) for every 0\leq i\leq d.

The generalized lower bound conjecture

In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture (GLBC):

Let P be a simplicial d-polytope. Then

(A) the h-vector of P, (h_0,h_1,...,h_d) satisfies h_0 \leq h_1 \leq ... \leq h_{\lfloor d/2 \rfloor}.

(B) If h_{r-1}=h_r for some r \leq d/2 then P can be triangulated without introducing simplices of dimension \leq d-r.

The first part of the conjecture was solved by Stanley in 1980 using the Hard Lefschetz theorem for toric varieties. This was part of the g-theorem that we discussed extensively in a series of posts (II’, II, IIIB). In their paper, Murai and Nevo give a proof of part (B). This is remarkable!

Earlier posts on the g-conjecture:

I: (Eran Nevo) The g-conjecture I

I’ How the g-conjecture came about

II (Eran Nevo) The g-conjecture II: The commutative-algebra connection

III (Eran Nevo) The g-conjecture III: Algebraic shifting

B: Billerafest

Cup Sets, Sunflowers, and Matrix Multiplication

This post follows a recent paper On sunflowers  and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens (ASU11) which rely on an earlier paper Group-theoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), and refers also to a paper by Don Coppersmith and Shmuel Winograd (CW90).

Three famous problems

The Erdos-Rado sunflower conjecture

The Erdos-Rado sunflower (Delta system) theorem and conjecture was already menioned in this post on extremal set theory.

A sunflower (a.k.a. Delta-system) of size r is a family of sets A_1, A_2, \dots, A_r such that every element that belongs to more than oneofthe sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that

Erdos-Rado sunflower theorem: There is a function f(k,r) so that every family \cal F of k-sets with more than f(k,r) members contains a sunflower of size r.

One of the most famous open problems in extremal combinatorics is:

The Erdos-Rado conjecture: Prove that f(k,r) \le c_r^k.

Here, c_r is a constant depending on r. This is most interesting already for r=3.

Three term arithmetic progressions

The cup set problem (three terms arithmetic progressions in (Z/3Z)^n):

The cup set problem was also discussed here quite extensively. (See, e.g. this post.)

Let \Gamma=\{0,1,2\}^n. The cap set problem  asks for the maximum number of elements in a subset of \Gamma which contains no arithmetic progression of size three or, alternatively, no three vectors that sum up to 0(modulo 3). (Such a set is called a cup set.) If A is a cap set of maximum size we can ask how the function h(n)=3^n/|A| behaves. Roy Meshulam proved, using Roth’s argument, that h(n) \ge n. Edell found an example of a cap set of size 2.2^n. So h(n) \le (3/2.2)^n.  The gap is exponential.

The strong cap set conjecture: h(n) \ge (1+\epsilon)^n for some \epsilon >0.

Of course, the cap set problem is closely related to

Erdos-Turan problem (for r=3): What is the larget size r_3(n) of a subest of {1,2,…,n} without 3-term arithmetic progression?

Matrix multiplications

Let ω be the smallest real number so that there is an algorithm for multiplying  two n \times n matrices which requires O(n^\omega ) arithmetic operations.

The ω=2 conjecture: ω=2.

A very recent breakthrough by Virginia Vassilevska Williams (independently) following an earlier breakthrough by Andrew Stothers improved the Coppersmith-Winograd algorithm which gave ω =2.376, to 2.374 and 2.373 respectively. (See the discussions over Lipton’s blog (1,2), Shtetl optimized, and Computational Complexity.)

It turns out that these three conjectures are related. (The connection of matrix multiplication and the Erdos-Turan problem is fairly old, but I am not sure what an even drastic improvment of Behrends’s lower bound would say about \omega.)

Three combinatorial conjectures that imply ω=2.

Remarkably, an affarmative answer for the ω=2 conjecture would folow from each one of three combinatorial conjectures. One conjecture goes back to CW90 and two were described in CKSU05. I will not present the precise formulations in order to encourage the readers to look at the original papers. (Maybe I will add the formulations later.)

The no disjoint equivoluminous subsets conjecture (CW90).

The Strong UPS conjecture (CKSU05).

Theorem: Conjecture CW90 implies the strong UPS conjecture.

CKSU’s two-family conjecture (CKSU05).

Relations between these problems

Here are some results taken from ASU11 about the relations between these combinatorial questions. The first result goes back to Erdos and Szemeredi.

The weak sunflower conjecture: A family \cal F of subsets of {1,2,…,n}  with no sunflower of size 3 can have at most (2-\epsilon)^n sets.

The following results are not difficult.

Theorem: The strong sunflower conjecture implies the weak sunflower conjecture.

Theorem: The strong cup set conjecture also implies the weak sunflower conjecture.

Theorem: The weak sunflower conjecture implies that the CW90 conjecture is false.

It follows that CW90 conjecture is in conflict both with the Erdos Rado sunflower conjecture and with the strong cup set conjecture.

Theorem: The strong cup set conjecture implies that the strong UPS conjecture is false.

While two family theorems are quite popular in extremal combinatorics (see this post and this one), CKSU’s two family conjecture is still rather isolated from other combinatorics.

What to believe?

This is a nice topic for discussion.

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.