Andriy Bondarenko Showed that Borsuk’s Conjecture is False for Dimensions Greater Than 65!

The news in brief

Andriy V. Bondarenko proved in his remarkable paper The Borsuk Conjecture for two-distance sets  that the Borsuk’s conjecture is false for all dimensions greater than 65. This is a substantial improvement of the earlier record (all dimensions above 298) by Aicke Hinrichs and Christian Richter.

Borsuk’s conjecture

Borsuk’s conjecture asserted that every set of diameter 1 in d-dimensional Euclidean space can be covered by d+1 sets of smaller diameter. (Here are links to a post describing the disproof by Kahn and me  and a post devoted to problems around Borsuk’s conjecture.)

Two questions posed by David Larman

David Larman posed in the ’70s two basic questions about Borsuk’s conjecture:

1) Does the conjecture hold for collections of 0-1 vectors (of constant weight)?

2) Does the conjecture hold for 2-distance sets? 2-distance sets are sets of points such that the pairwise distances between any two of them have only two values.

Reducing the dimensions for which Borsuk’s conjecture fails

In 1993 Jeff Kahn and I disproved Borsuk’s conjecture in dimension 1325 and all dimensions greater than 2014. Larman’s first conjecture played a special role in our work.   While being a special case of Borsuk’s conjecture, it looked much less correct.

The lowest dimension for a counterexample were gradually reduced to  946 by A. Nilli, 561 by A. Raigorodskii, 560 by  Weißbach, 323 by A. Hinrichs and 320 by I. Pikhurko. Currently the best known result is that Borsuk’s conjecture is false for n ≥ 298; The two last papers relies strongly on the Leech lattice.

Bondarenko proved that the Borsuk’s conjecture is false for all dimensions greater than 65.  For this he disproved Larman’s second conjecture.

Bondarenko’s abstract

In this paper we answer Larman’s question on Borsuk’s conjecture for two-distance sets. We found a two-distance set consisting of 416 points on the unit sphere in the dimension 65 which cannot be partitioned into 83 parts of smaller diameter. This also reduces the smallest dimension in which Borsuk’s conjecture is known to be false. Other examples of two-distance sets with large Borsuk’s numbers will be given.

Two-distance sets

There was much interest in understanding sets of points in R^n  which have only two pairwise distances (or K pairwise distances). Larman, Rogers and Seidel proved that the maximum number can be at most (n+1)(n+4)/2 and Aart Blokhuis improved the bound to (n+1)(n+2)/2. The set of all 0-1 vectors of length n+1 with two ones gives an example with n(n+1)/2 vectors.

Equiangular lines

This is a good opportunity to mention another question related to two-distance sets. Suppose that you have a set of lines through the origin in R^n so that the angles between any two of them is the same. Such  a set is  called an equiangular set of lines. Given such a set of cardinality m, if we take on each line one unit vector, this gives us a 2-distance set. It is known that m ≤ n(n+1)/2 but for a long time it was unknown if a quadratic set of equiangular lines exists in high dimensions. An exciting breakthrough came in 2000 when Dom deCaen constructed a set of equiangular lines in R^n with 2/9(n+1)^2 lines for infinitely many values of n.

Strongly regular graphs

Strongly regular graphs are central in the new examples. A graph is strongly regular if every vertex has k neighbors, every adjacent pair of vertices have λ common neighbors and every non-adjacent pair of vertices have μ common neighbors. The study of strongly regular graphs (and other notions of strong regularity/symmetry) is a very important area in graph theory which involves deep algebra and geometry. Andriy’s construction is based on a known strongly regular graph G_2(4).

New Ramanujan Graphs!

margulis1

margulis2

Margulis’ paper

Ramanujan graphs were constructed independently by Margulis and by Lubotzky, Philips and Sarnak (who also coined the name). The picture above shows Margulis’ paper where the graphs are defined and their girth is studied. (I will come back to the question about girth at the end of the post.) In a subsequent paper Margulis used the girth property in order to construct efficient error-correcting codes. (Later Sipser and Spielman realized how to use the expansion property for this purpose.)

The purpose of this post is to briefly tell you about new Ramanujan graphs exhibited by Adam Marcus, Daniel Spielman, and Nikhil Srivastava. Here is the paper. This construction is remarkable for several reasons: First, it is the first elementary proof for the existence of Ramanujan graphs which also shows, for the first time, that there are k-regular Ramanujan graphs (with many vertices)  when k is not q+1, and q is a prime power. Second, the construction uses a novel “greedy”-method (with further promised fruits) based on identifying classes of polynomials with interlacing real roots, that does not lead (so far) to an algorithm (neither deterministic nor randomized). Third, the construction relies on Nati Linial’s idea of random graph liftings and verify (a special case of) a beautiful conjecture of Yonatan Bilu and Linial.  Continue reading

F ≤ 4E

1. E ≤ 3V

Let G be a simple planar graph with V vertices and E edges. It follows from Euler’s theorem that

3V

In fact, we have (when V is at least 3,) that E 3V – 6.

To see this,  denote by F the number of regions or faces determined by G (in other words, the number of connected components in the complement of the embedded graph). Euler’s theorem asserts that

E – V + F = 2

V – E + F = 2

and now note that every face must have at least three edges and every edge is contained in two faces and therefore 2E \ge 3F, so 6=3V – 3E + 3F ≤ 3V – 3E +2E.

2. F  4E

Now let K be a two-dimensional simplicial complex and suppose that K can be embedded in R^4. Denote by E the number of edges of K and by F the number of 2-faces of K.

Here is a really great conjecture:

Conjecture:

4E

A weaker version which is also widely open and very interesting is:

For some absolute constant C,

C E

Remarks: The conjecture extends to higher dimensions. If K is an r-dimensional simplicial complex that can be embedded into R^{2r} then the conjecture is that

f_r(K) \le C_rf_{r-1}(K),

Where C_r is a constant depending on r.  Here f_i(K) is the number of i-dimensional faces of K. A stronger statement is that C_r= r+2. The conjecture also extends to polyhedral complexes and more general form of complexes. In the conjecture ‘embed’ refers to a topological embedding.

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 f-vector (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.