Stefan Steinerberger: The Ulam Sequence

This post is authored by Stefan Steinerberger.

The Ulam sequence

1,2,3,4,6,8,11,13, 16, 18, \dots

is defined by starting with 1,2 and then repeatedly adding the smallest integer that is (1) larger than the last element and (2) can be written as the sum of two distinct earlier terms in a unique way. It was introduced by Stanislaw Ulam in a 1962 paper (`On some mathematical problems connected with patterns of growth of figures’) where he vaguely describes this as a one-dimensional object related to the growth of patterns. He also remarks (in a later 1964 paper) that `simple questions that come to mind about the properties of a sequence of integers thus obtained are notoriously hard to answer.’ The main question seems to have been whether the sequence has asymptotic density 0 (numerical experiments suggests it to be roughly 0.07) but no rigorous results of any kind have been proven so far.

A much stranger phenomenon seems to be hiding underneath (and one is tempted to speculate whether Ulam knew about it). A standard approach in additive cominatorics is to associate to the first N elements of a sequence a_1, a_2, \dots, a_N a
function

 f_N(\theta) = \exp{(a_1 i \theta)} + \exp{(a_2 i \theta)} + \dots + \exp{(a_N i \theta)}

and work with properties of f_N. If we do this with the elements of the Ulam sequence and plot the real part of the function, we get a most curious picture with a peak around
 \theta \sim 2.571447\dots

pic1

Such spikes are generally not too mysterious: if we take the squares 1,4,9,16, ... we can observe a comparable peak at \theta = 2\pi/4 for the simple reason that squares are \equiv 0, 1 (mod 4). However, here things seem to be very different: numerically, the Ulam sequence does seem to be equidistributed in every residue class. Due to 2\pi-periodicity, the function f_N only sees the set of numbers

\left\{ \theta a_n~\mbox{mod}~ 2\pi: 1 \leq n \leq N\right\}

and it makes sense to look at the distribution of that sequence on the torus for that special value \theta \sim 2.571447\dots. A plot of the first 10 million terms reveals a very strange distribution function.

pic2

The distribution function seems to be compactly supported (among the first 10 million terms only the four elements 2, 3, 47, 69 give rise to elements on the torus that lie outside [\pi/2, 3\pi/2].) The same phenomenon seems to happen for some other initial conditions (for example, 2,3 instead of 1,2) as well and the arising distribution functions seem to vary greatly.

 

Question 1: What is causing this?

Question 2: Are there other `natural’ sequences of integers with that property?

 

See also Stefan’s paper  A Hidden Signal in the Ulam sequence .

Update: See also Daniel Ross’  subsequent study of Ulam’s sequence, presented in Daniel’s sort of public ongoing “research log”.  (“It includes a summary at the top of the most interesting observations to date, which usually lags a couple weeks behind the most current stuff.”) pic3

Posted in Guest blogger, Open problems | Tagged , | 8 Comments

TYI 26: Attaining the Maximum

(Thanks, Dani!) Given a random sequence a_1,a_2,\dots , a_n, ***a_i \in \{-1,1\}***, n>2, let S_k=a_1+a_2+\cdots +a_k. and assume that S_n=0.  What is the probability that the maximum value of S_k is attained only for a single value of k?

Test your intuition: is this probability bounded away from 0? tends to 0 like 1/\sqrt n? Quicker? Slower? Is there a nice formula?

Posted in Combinatorics, Probability, Test your intuition | Tagged | 21 Comments

A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24

maryna1

Maryna Viazovska

The news

Maryna Viazovska has solved the densest packing problem in dimension eight! Subsequently, Maryna Viazovska with Henry Cohn, Steve Miller, Abhinav Kumar, and Danilo Radchenko solved the densest packing problem in 24 dimensions!

Here are the links to the papers:

Maryna Viazovska, The sphere packing problem in dimension 8

Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, Maryna Viazovska,
The sphere packing problem in dimension 24

(I thank Steve Miller and Peter Sarnak for telling me about it.)

Additional sources:  An article by Frank Morgan in The Huffington Post; A blog post by John Baez on the n-Category Cafe; An article by Erica Klarreich on Quanta Magazine; A blog post in Mathbya girl;

Some Background

Kepler, Gauss, Hales, Cohn and Kumar. A central mathematical problem is to find the densest sphere packing in R^d. The case d=3 is known as the Kepler conjecture. Gauss solved it for lattice packings, and Thomas Hales proved it for general packing using a massive use of computations. Cohn and Kumar settled the lattice case for dimensions 8 and 24.

Conway and Sloane. The “bible” regarding sphere packing is the classic book by two major player of the theory John Conway and Neil Sloane.

Hales and Fejes Toth.  Announced in 1998 and published a few years later, Hales’ proof  relies on some early work of Laszlo Fejes Toth. Since a full verification would require developing much of  the whole project from scratch, Hales himself led a team of researchers to find a formal proof which was published in 2015.

Lie and  Leech.   Lower bounds for higher dimensions. For some dimensions, special lattices of Lie type give surprisingly dense lattice packings. The Leech lattice gives a remarkably dense packing in dimension 24.

Minkowski,…, Ball, Vance and Venkatesh,  For asymptotically large dimensions a probabilistic method by Minkowski gives the best known lower bound up to small (but exciting) improvements. It gives a packing of density $2 \cdot 2^{-n}$.  Here is a slide from a lecture by Henry Cohn on the state of the art for the asymptotic question. (And here is the link to the slides of the full lecture.)

cohn-slide

Delsartes, Kabatiansky and Levenshtein. Upper bounds via linear programming. Delsartes’ linear programming method (that can be seen as a Fourier/spectral attack with special features,) had led to important results towards general upper bounds by Kabatiansky and Levenshtein.

Cohn and Elkies developed related spectral methods applying directly to sphere packing, which allow to improve the upper bounds in dimensions 4–31 and give strikingly good results in dimensions 8 and 24.  Cohn and Kumar used these linear programming methods to settle the densest lattice problem in dimensions 8 and 24 and to give extremely good numerical upper bounds for the non-lattice case.

This is the starting point for Viazovska’s breakthrough.

Related problems/issues  to keep in mind: The densest packing problem in other dimensions and when the dimension tends to infinity; Kissing numbers and spherical codes; Upper bounds for error correcting codes; packing in other symmetric spaces; packing covering and tiling in combinatorics and geometry.

Viazovska’s breakthrough

The little I can tell you is that for a solution one needs to identify certain functions to plug in to the spectral machine. And Maryna’s starting point was some familiar extraordinary elliptic functions and modular forms.  More details on the comment section are most welcome.  (Update:) John Baez wrote on the n-Category Cafe some elementary comments on the proofs: E8 is the best.

The 24-dimensional case

A key ingredient for the result in dimension 24 is the earlier numerical rationality conjectures by Cohn and Miller.  Those now appear in the preprint: Henry Cohn, Stephen D. Miller, Some properties of optimal functions for sphere packing in dimensions 8 and 24 .

Congratulations to Maryna, Abhinav,  Danilo,  Henry, and Steve!

I remember a decade ago that Steve Miller explained to me some developments, ideas, and dreams  regarding two problems. One was the sphere packing problem in dimensions 8 and 24 that he now took part in solving, and the other was the irrationality questions regarding zeta functions at odd integers (and maybe also the Euler constant.)  Time to move to the second problem, Steve:)

(And a trivia question: name a player in both these stories. As usual if you answer in the comment section please give a zero-knowledge answer demonstrating that you know the solution without revealing it.)

Posted in Combinatorics, Geometry, Updates | Tagged , , , , , , | 15 Comments

Polymath10-post 4: Back to the drawing board?

It is time for a new polymath10 post on the Erdos-Rado Sunflower Conjecture. (Here are the links for post1, post2, post3.) Let me summarize the discussion from Post 3 and we can discuss together what directions to peruse. It is a pleasure to mention that in parallel Tim Gowers is running polymath11 aimed for resolving Frankl’s union closed conjecture. Both questions were offered along with the Erdos discrepancy problem and the Erdos-Hajnal conjecture in this 2009 post by Tim. In fact, some people participate both in polymath10 and polymath11. The acronym for polymath 11 is FUNC and I suppose we can choose between SUN or ERSC or some other options for polymath10.

Because of polymath10, I did not discuss over here other things. Let me mention two super major developments that I am sure you all know about. One is Laci Babai’s  quasi-polynomial algorithm for Graph isomorphism. (This is a good time to mention that my wife’s mother’s maiden name is Babai.) You can read about it here (and the next three posts) and here. Another is the solution by Jean Bourgain, Ciprian Demeter, Larry Guth of Vinogradov’s main conjecture. You can read about it here and here.

 

Polymath10:

We denoted by f(k,r) the largest cardinality of a family of k-sets without a sunflower of size r, and  f(k,r,m,n) the largest cardinality in a family of k-subsets of [n] with the property P(r,m), namely without a sunflower of size r with head of size at most m. Adding the subscript b for f_b(k,r),f_b(k,r,m,n) refer to balanced families rather than to arbitrary family. The “Erdos-Ko-Rado regime” is when r=2 and m is arbitrary or when m=1 and r is arbitrary. (In this regime the property P(r,m) is preserved under shifting.)

Results by Ferdinand Ihringer

Ferdinand gave interesting upper bounds and lower bounds for f(k,r,m,n) in terms of f(k,r).

f(m, r) \leq f(k, r, m, n) / \binom{n-m}{k-m} \leq 10 f(k, r)^3.

For the upper bound see this writeup by Ferdinand. For more details see this comment and the following ones. It will be interesting to find sharp lower and upper bounds.

Proposal by Domotor Palvolgyi

Domotor raised   in this comment and the following ones some ideas for using algebraic methods for the sunflower conjecture. This have led to an interesting discussion (following these comments) between Domotor and Ferdinand on connection between Sunflowers and Ramsey numbers (mainly R_3(k)).

So that this post will not interrupt this interesting discussion let me quote the beginning of Domotor’s comment posted minutes ago:

“So let us denote the size of the largest k-uniform family without r (different) sets whose pairwise intersection has the same size by g(k,r). As we have seen in the earlier discussion, trivially g(k,r)\le f(k,r) and g(k,r)\le R_r(k) (where in the last Ramsey notation we forbid K_r in a k-coloring of the complete graph). Mysteriously, for all three functions we have similar lower and upper bounds. In this comment I propose to try proving f(k,r) \le g(ck,r) for some c.”

Proposal by Shachar Lovett.

Shachar Lovett proposed in this comment how to use the topological Tverberg theorem for attacking a certain important special case of the conjecture.

Reminder: Reduction to the balanced case, Phillip Gibbs’ construction, and more drastic reductions.

We started with the observation that every family F of k-sets contains a balanced subfamily of size \frac {k!}{k^k}|F|. (BTW for graphs there is a sharper result by Noga Alon and it would be interesting to extend it to hypergraphs!) This gives that

f(k,r) \le e^kf_b(k,r).

Phillip Gibbs showed in this comment that if the sunflower conjecture is true then

f_ (k,r) \le (1+o(1))^kf_b(k,r).

It will be interesting to describe precisely what (1+o(1)) stands for, and improve it as much as possible. All left to be done for a counterexample to the sunflower conjecture is to complement Phillip construction by another one showing an exponential gap between the balanced and general case. This is certainly a tempting direction.

More drastic reductions then the very basic one are also possible, for example: for families of k-subsets without a sunflower of size 3 it is enough to consider families with elements colored by 100k colors such that every set is colored by consecutive colors and two sets sharing k-1 elements are not using the same color-intervals. (This implies “high girth” of some sort.) We can ask if this type of reductions is useful for proving the conjecture, if one can show (like Phillip) that assuming the conjecture, the gap between the bounds for this version is not too large compared to the general version, and hope that this can be part of a construction going in the negative direction.

The Homological/Algebraic Approach

In quite a few comments to post 3, I tried to further develop the homological ideas   (and to mention some low hanging fruits and related questions). We did reach a major obstacle sending us back to the drawing board. I see some possible way around the difficulty and I will now describe it. For this purpose I will review the homological ideas in somewhat more general and very elementary context. (We only briefly mention the connection with cycles/homology but it is not needed).

Compound matrices, weak isomorphism and dominance.

Let X=(x_ij)_{1 \le i \le n, 1 \le j \le n} be a generic matrix. The k-th compound matrix C_k(X) is the matrix of k by k minors. Namely, C_k(X)=x_{ST}, S,T \in {{[n]} \choose {k}} where x_{ST}=det(x_{ij})_{i \in S,j\in T}.

Given two k-unform hypergraphs F,G we say that F and G are weakly isomorphic if the m\times m minor C_{F,G}(X) of C_k(X) whose rows and columns correspond to sets in F and G respectively is non-singular. (It is fairly easy to see that if F and G are isomorphic then they are weakly isomorphic. This relies on the condition that X is generic.) We will say that F dominates G if  |F|\ge |G| and C_{F,G}(X) is full rank. Thus, F and G are weakly isomorphic if each dominates the other.

Let D[b,c] be the set of k-subsets S of [n] such that |S \cap [b]|\ge c.  The connection with our notions of acyclicity is as follows: F is acyclic (i.e. Z_{k-1}(K)=0) iff F is dominated by D[1,1]. In greater generality,   K_{k-1}[b,c]=0 iff F is dominated by D[b,c]. (In particular,  Z_{k-1} [r,1](K)=0 iff F is dominated by D[r,1], and Z_{k-1}[m,m](K)=0 iff F is dominated by $D[m,m]$.) Remark: Here and later in the post Z_*[b,c] with H_*[b,c] since we deal only with cycles for the top dimension, so there are no “boundaries” to mod out.

Algebraic shifting

A family F of k-subsets of [n] is shifted if whenever S \in F and R is obtained by replacing an element by a smaller element then R \in F.  It can be shown that two shifted families of the same size are weakly isomorphic only if they are equal! We can use our compound matrix to describe an operation (in fact, several operations) called shifting which associated to a family F a shifted family \Delta_T(F).  Suppose that |F|=m. \Delta (F) is the lexicographically smallest family of sets which is weakly isomorphic to F. In more details: we first consider a total ordering T on k-subsets of [n]. Then we greedily  build a hypergraph which is dominated by F.  When we reach m sets we obtain a  hypergraph \Delta_T(F) weakly isomorphic to F.

Now, if the total ordering is the lexicographic order on {{[n]} \choose {k}} then we denote \Delta(F)=\Delta_T(F)) and call \Delta(F) the “algebraic shifting” of F. In this case, it can be shown that the resulting family is shifted. Also of special importance is the case that T=RL is the reverse lexicographic order.

For sets of integers of size k, the lexicographic order refers to the lexicographic order when we ordered the elements of every set from increasingly, and the reverse lexicographic order is the lexicographic order when we order the elements decreasingly.

From 12<13<14<15<…<21<22<…<31<32<… we get

\{1,2\} <_L \{1,3\} <_L \{1,4\} \dots <_L \{ 2,3\} <_L \{2,4\} <_L \dots

and from  21<31<32<41<42<43<51<52<…  we get

\{1,2\} <_{RL} \{1,3\}<_{RL}\{2,3\}<_{RL}\{1,4\}\dots

We mention again some connection with acyclicity and homology: F  is acyclic if all sets in \Delta (F) contains ‘1’. F is [r,1]-acyclic iff all sets in in \Delta (F) intersect [r]. F is [m,m]-acyclic iff all sets in \Delta(F) contains [r]. For general b,c, [b,c]-acyclicity is not expressed by those two versions of algebraic shifting, however, F is [s,k]-cyclic if \Delta_{RL}(F) \subset {{[s]}\choose{k}}.

Algebraic shifting in  the Erdos-Ko-Rado regime.

The following properties are preserved under algebraic shifting:

(1) Every two members of F has at least m elements in common.

(2) There are no r pairwise disjoint sets in F.

For balanced families we know even more:

(3) If F is balanced and every two members of F has at least m elements in common then all sets in \Delta(F) contains [m].

and

(4) If F is balanced and there are no r pairwise disjoint sets in F, then every set in \Delta(F) intersects [r-1].

Reverse shifting in the Erdos-Ko-Rado regime.

As it turns out we have much stronger statements:

The following properties are preserved under reverse-lexicographic algebraic shifting:

(5) Every two members of F has at least m elements in common.

(6) There are no r pairwise disjoint sets in F.

(I dont know if (3) and (4) extends as well. It  certainly worth the effort to check it.)

 

Modified plan for attack:

Our ultimate conjecture remains the same:

Main Conjecture:  If F has no sunflower of size r then it is [xk,k]-acyclic. (I.e., Z_{k-1}[(xk,k](K)=0.)

For balanced family we conjectured that x=(r-1) and for the non-balance we had a larger value x=r.

Our homological approach mainly for the balanced case was to use the local homological condition from  (2) (or(4)) (with some additional homological condition yet to be proved – this was Conjecture A) to conclude (This was Conjecture B) that F is [xk,k]-acyclic. However,  Conjecture B turned out to be false.  Our new idea is to replace the local conditions on homology obtained from (2), (4) by those given by (6) which are apparently quite stronger.

We also tried to explore how to prove the main conjecture via  an even stronger statement for “combinatorial cycles”. This works for the balanced case in the Erdos-Ko-Rado-regime (leading to some interesting consequences). But we did not manage to extend it beyond this regime. Domotor  shoot down some half-baked attempts towards such a goal.

What we propose now is to use the following theorem instead of Conjecture A and to greatly modify Conjecture B accordingly. (For general families; being balanced is not used.)

Theorem: Let F is a family of k-sets without a sunflower of size r. Then

(*) For every family of i-sets F' which is the link of a set of size k-i (including the case F'=F) , Every set in \Delta _{RL}(F') intersect [(r-1)i].

Conjecture B (greatly modified): For a family F of k-sets satisfying (*) we have

(**) \Delta_{RL}(F) \subset {{[rk]}\choose{k}}.

This is the new plan! Below are a couple of comments.

A new homological translation:

We can, I think,  translate the condition on reverse lexicographic shifting also to some conditions on homology, given in this comment,  but the connection is still a little dubious and need some further checking and explanation. (Specifically, it relies on a comment I make in my paper on algebraic shifting that if F is a family of k-subsets of [n] and  G is its complement, then the shifting of F is related to the reverse lexicographic shifting of G as follows: takes the complement of \Delta (F) and apply the involution sending element i to n-i.)

If K is the simplicial complex spanned by our family F and L is the simplicial complex spanned by the complement of F  we want to replace conditions of the form

(*) Z_{k-1}[s,1] (K)=0

by the stronger condition

(**) Z_{k-1}[n-s-k,1] (L)\ne 0

For example, for a graph G with n vertices and n-1 edges \Delta (G) gives all edges containing ‘1’ (which is equivalent to (*) for s=1) if and only if G is a tree. But requiring it for \Delta_{RL}(G)  implies (I think) that G  be a star and is equivalent (I think) to Z_1[n-3,1](\bar G)\ne 0, where \bar G is the complement of G.

Planned experimentation.

We plan to run computer experimentation to test some of these ideas on small cases.

A few words on symmetric shifting and related notions of homology.

Let me mention that there is a variant of compound matrix, weak equivalence and of algebraic shifting (and hence also of the various homology groups we considered,) when we use symmetric products instead of exterior products.  The theories based on those variants are very similar, and the advantage of the notions based on symmetric powers is that they are closer to studied notions of commutative algebra. (But I think they will be harder to compute as determinants are replaced by permanents.)

 

Posted in Combinatorics, Mathematics over the Internet, Polymath10 | 11 Comments

News (mainly polymath related)

Update (Jan 21)

j) Polymath11 (?) Tim Gowers’s proposed a polymath project on Frankl’s conjecture. If it will get off the ground we will have (with polymath10) two projects running in parallel which is very nice. (In the comments Jon Awbrey gave a links for a first in a series posts also on Frankl’s conjecture, with the catchy title, Frankl my dear.)

 

a) NogaFest started a few days ago. It is a wondeful meeting! My lecture entitled “polymath” refers to the older meaning of the word, so appropriate to describe Noga. (I was not aware that the word has a meaning until recently). I talked, among other things, about polymath10. I prepared the talk a week ahead and  presented our Conjectures A and B (from polymath10 last post) hoping that perhaps I could add some positive information toward them. Well, just after my presentation was ready, I realized that Conjecture B is false. Here are the slides.

Two quotes from the lecture. First about the birthday boy: the idea of the polymath was expressed by Leon Battista Alberti (1404–1472), in the statement, most suitable to Noga a man (who) can do all things if he will”.  Second, about polymath projects (by Gowers): “a large collaboration in which no single person has to work all that hard.”

b) Here is the link to a mathoverflow question asking for polymath proposals. There are some very  interesting proposals. I am quite curious to see some proposals (perhaps mainly to see what researchers regard as central major projects,) in applied mathematics, and various areas of geometry, algebra, analysis and logic.

c) A very nice polymath proposal by Dinesh Thakur was posted  by Terry Tao on the polymath blog. The task was to explain some numerically observed identities involving the irreducible polynomials P in the polynomial ring {\bf F}_2[t] over the finite field of characteristic two. David Speyer managed to prove Thakur’s observed identities! Here is the draft of the paper.

d) This reminds me that some years ago David Speyer solved a question that interested me for decades and was presented here on the blog and later on MathOverflow about systems of skew lines in three dimensional vector spaces over division rings (and especially the Quaternions).

e) Related to polymath3, let me mention that Michael Todd proved a small but very elegant improvement of the upper bounds by Kleitman and me from 1992. (The new bound is (n-d)^{\log d}. The first improvement, I think, in two decades!

f) I have a very nice thing to tell you about polymath4! Shafi Goldwasser abstract for Nogafest talked about a new notion of randomized algorithms: A randomized algorithm to achieve a certain task (for example to find a perfect matching in a graph,) which is guaranteed to reach the same answer with high probability! Such an algorithm is called pseudo-deterministic. It is both an amazing concept, and it is quite amazing that it was not introduced before. The polymath4 question was to find deterministically a prime with n digits and A new challenge (that Shafi asks about) is to find a pseudo-deterministic efficient algorithm. Namely, a randomized algorithm which will find an n-digit prime, but with high probability the same one! (I would guess that it is still hopeless.)

g) And Terry Tao gave a beautiful lecture on Erdos discrepancy problem (the topic of polymath5). I understood a little better the argument (which is  similar to Roth density increase argument for 3 term AP,) that allows Tao to use the logarithmically-averaged Chowla inequalities.

h) The old conjecture that centrally symmetric convex sets  have nonnegative correlation w.r.t. the Gaussian distribution  was proved! Let me refer you to the paper Royen’s proof of the Gaussian correlation inequality for a simple exposition of a proof by Thomas Royen, and more information on the solutions and solvers.

i) The Nogafest participants are invited to a Jazz night at Gilly’s

2016_JAZZ gilly's

The third Polymath10 post is active. I hope to post a new polymath10 post in about 1-2 weeks. I hope also to return to various amazing things I am hearing on Nogafest and other places (and also on my ownfest some months ago).

 

 

Posted in Combinatorics, Conferences, Mathematics over the Internet, Polymath10, Polymath3, Updates | Tagged , , , , , , , | 11 Comments

Polymath 10 Post 3: How are we doing?

The main purpose of this post is to start a new research thread for Polymath 10  dealing with the Erdos-Rado Sunflower problem.  (Here are links to post 2 and post 1.) Here is a  very quick review of where we are.

Let f(k,r) [f_b(k,r)] be the maximum size of a family of k-sets [balanced family] with no sunflower of size r. Let C(r) = \lim sup f(k,r)^{1/k} and  C_b(r) = \lim sup f_b(k,r)^{1/k}.

Philip Gibbs:  The balanced case vs. the general case.

Phillip gave a beautiful construction showing that if C(r) is finite than C_b(r)=C(r). This is very interesting and I found it surprising. (Earlier we only knew that C(r) \le e \cdot C_b(r).) Of course, if you can find another construction which starts with balanced families (even only those constructed by Philip) and end with exponentially larger general families (you can even enlarge k a little,) this will provide a counterexample to the Erdos-Rado conjecture.

The homological approach:

In the previous post and some comments (like this comment and the following ones; and this comment)  I continued to meditate about my homological approach. For r=3 we want to show that for balanced families, a (2m,m)-cycle will contain a sunflower with head of size smaller than m. (This will now give C(3) \le 4.)  Juggeling between the homological notion of (b,c)-cycles and a combinatorial one can be useful.

Proposals by Tim:

Tim observed that if all pairwise intersections between sets in a sunflower free family have the same size then this leads to exponential upper bounds. This can be a starting point for an argument where “same size” is replaced by a weaker condition, or to ideas about how to construct a counterexample.

Random sunflower-free families

We also want to understand the expected number of sets in the sunflower-free process when we consider k-subsets fron [n]. (We would also like to understand the expected size of the union of sets in the resulting family.) This is interesting both for the general case and the balanced case. Simulations by Philip (e.g. here) and by Gonzalo (e.g. here) were presented. (I am still confused about the outcomes of the simulations, maybe we shoud run more simulations.)

New examples

In the later comments to the previous thread (starting here) that I did not digest yet, Philip offered some ideas on new constructions of various types.

Some more comments and questions

Avi Wigderson asked: Is it enough to prove the Erdos-Rado conjecture for n=k^2? n=k \log k? etc? Dömötör asked the following Kneser-type coloring question:
How many colors to we need to color all k-tuples of an n element set avoiding monochromatic 3-sunflowers?

The special case mentioned by Shachar:

Shachar mentioned in comments to post I (starting here) an exciting special case (related to matrix multiplication.)

Looking at the classic papers:

It can be a good time to look at the classic papers by Abott, Hanson, and Sauer and , Spencer and Kostochka (for the general case; for sunflower of size three). Here is again the link for Kostochka’s survey.  There are many other papers (even recent) about sunflowers and many aspect of the problem and related problems that we did not talk about.

Here are the six pages of Joel’s paper.

quote-the-very-term-combinatorial-methods-has-an-oxymoronic-character-joel-spencer-76-50-16

temp1temp2temp3temp4 temp5temp6

Posted in Combinatorics, Mathematics over the Internet, Open problems, Polymath10 | Tagged , | 103 Comments

Polymath10, Post 2: Homological Approach

We launched polymath10 a week ago and it is time for the second post. In this post I will remind the readers what  the Erdos-Rado Conjecture and the Erdos-Rado theorem are,  briefly mention some points made in the previous post and in the comments, make some remarks of administrative nature, and describe in detail a homological plan for attack, some of whose ingredients were mentioned in the first post.

Of course, there are various other avenues that can be explored:  In a series of comments (e.g. this thread and that thread and this) Tim Gowers proposed a line of attack related to understanding quasirandom behavior of families of sets in terms of their pairwise intersections. (Update: Tim developed his ideas in further comments. A theme which is common to his approach as well as to the homological approach is to see if we can “improve” certain properties of the family after moving to an exponentially smaller subfamily. Second update: this post was written after 70 or so comments for post 1. There are many further interesting comments. ) Karim Adiprasito described a different topological combinatorics approach. Another clear direction is  to try to extend the ideas of Spencer and Kostochka which led to the best known bounds today.  Raising more ideas for attacking the conjecture is most welcome. For example, in Erdos Ko Rado theory, besides direct combinatorial arguments (mainly those based on “shifting,”) spectral methods are also quite important. Of course, the sunflower conjecture may be false as well and ideas on how to construct large families without sunflowers are also most welcome.

Terry Tao kindly set a Wiki page for the project and proposed to conduct computer experimentation for small values of r and k. Of course, computer experimentation will be most welcome! Some of the suggestions described below can also be tested experimentally for small values.

Let me also mention some surprising connections between the sunflower conjecture and various issues arising in matrix multiplication. As pointed by Shachar Lovett (in this comment and the following one), a counterexample to a certain structural special case of the sunflower conjecture will imply an almost quadratic algorithm for matrix multiplication!

Dömötör and I hyperoptimistically conjectured that the Erdos-Rado example is optimal for Balanced families. But Hao gave a very simple counterexample.

The status of our project at this stage is described very nicely by Tim Gowers who wrote:

At the time of writing, Gil’s post has attracted 60 comments, but it is still at what one might call a warming-up stage, so if you are interested in the problem and understand what I have written above, it should still be easy to catch up with the discussion. I strongly recommend contributing — even small remarks can be very helpful for other people, sparking off ideas that they might not have had otherwise. And there’s nothing quite like thinking about a problem, writing regular bulletins of the little ideas you’ve had, and getting feedback on them from other Polymath participants. This problem has the same kind of notoriously hard feel about it that the Erdős discrepancy problem had — it would be wonderful if a Polymath collaboration could contribute to its finally getting solved.


Update to an earlier post. Karim Adiprasito, June Huh, and Eric Katz have now posted their paper “Hodge theory for combinatorial geometries” which contains, among other things, a proof of the Heron-Rota-Welsh conjecture on matroids.


Here is a reminder of the sunflower theorem and conjecture:

The Erdos-Rado sunflower Theorem

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 one of the sets belongs to all of them.  We call the common element to all the sets the head of the sunflower (or the kernel of the sunflower), and the elements that belong to just one among the sets, the petals.

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.

We denote by f(k,r) the smallest integer that suffices for the assertion of the theorem to be true.

The Erdos-Rado Sunflower Conjecture

The Erdos-Rado sunflower conjecture:  f(k,r) \le C_r^k.

Here, C_r is a constant depending on r. It may be also the case that we can take C_r=Cr for some absolute constant C. The conjecture is already most interesting for r=3.  I recommend to reading Kostochka’s survey paper and also, as we go, it will be useful to learn Spencer’s argument and Kostochka’s argument which made remarkable improvements over earlier upper bounds.

The main purpose of this post is to provide

A Homological attack on the sunflower Conjecture

Part 1:  Combinatorial Extensions and Variations

A) The question as an Erdos-Ko-Rado type question

Let f(k,r,m;n) be the maximum size of a family \cal F of k-subsets of [n]=\{1,2,\dots ,n\}  containing no sunflower of size r with head of size at most m-1.  (Note: it should me m-1.)

Basic Question: Understand the function f(k,r,m;n). Is it true that f(k,r,m;n)\le C_r^{k}n^{k-m}, where C_r is a constant depending on r, perhaps even linear in r.

A family of k-sets satisfies property P(k,r,m) if it contains no sunflower of size r with head of size at most m-1.

B) Stars and links:  Given a family F of sets and a set S,  the star of S is the subfamily of those sets in F containing S, and the link of S is obtained from the star of S by deleting the elements of S from every set in the star. Another way to say that \cal F has property P(k,r,m) is that the link of every set of size at most  less than m contains no r pairwise disjoint sets.

C) The balanced case

A family of k-sets is balanced (or k-colored, or multipartite) if it is possible to divide the ground set into k parts so that every set in the family contains one element from every part.

Let g(k,r,m;n) be the maximum size of a balanced family \cal F of k-subsets of [n]=\{1,2,\dots ,n\}  containing no sunflower of size r with head of size at most m. By randomly dividing the ground set into colors we obtain that f(k,r,m;n) \le \frac{k^k}{k!}g(k,r,m;n).

D) What we aim for. Below we describe two variations of a homological attack on the sunflower conjecture. If successful (as they are) they will lead to the following bounds.

The first variation based on conjectured homological properties of balanced families would yield

(*) f(k,r,m;n)\le e^k {{(r-1)m}\choose{m}}\cdot{{n-m} \choose {k-m}}

The alternative version would give

(**) f(k,r,m;n)\le {{m+(r-1)k}\choose{m}}\cdot {{n-m}\choose {k-m}}

Part 2: Collections of sets as geometric objects, homology and iterated homology.

E) Simplicial complexes and homology

Staring with a family {\cal F} we will consider the collection of sets obtained by adding all subsets of sets in {\cal F}. This is a simplicial complex, K, and we can regard it as a geometric object if we replace every set of size i by a simplex of dimension i-1. (We call sets in K of cardinality (i+1) by the name i-faces.

The definition of homology groups only depends on the combinatorial data. For simplicity we assume that all sets in {\cal F} (and hence in the associated simplicial complex) are subsets of {1,2,…,n}. We choose a field A (we can agree that the field will be the field of real numbers). Next we define for i>0 the vector space of i-dimensional chains C_i(K) as a vector space generated by i-faces of K. We also define a boundary map \partial_i:C_i(K)\to C_{i-1}(K) for every i. The kernel of \partial_i is the space of i-cycles denoted by Z_i(K); the image of \partial_{i+1} is the space of i-boundaries, denoted by B_i(K). The crucial property is that applying boundary twice gives you zero, and this allows to define homology groups H_i(K)=Z_i(K)/B_i(K). The betti numbers are defined as b_i(K)=dim H_i(K).  We will give the definition of the boundary operator further below.

F) Acyclic families and intersecting families

A family {\cal F} of k-sets is acyclic  if it contains no k-cycle, or equivalently if H_k({\cal F})=0.  (For coefficients in Z/2Z, a k-cycle G is a family of k-sets such that  every set of size (k-1) is included in an even number of k-sets in G.)

Proposition: An acyclic family of k-subsets of [n], contains at most {{n-1} \choose {k-1}} sets.

In the first post we asked:  Are there some connections between the property “intersecting” and the property “acyclic?”

Unfortunately, but not surprisingly intersecting families are not always acyclic, and acyclic families are not always intersecting. (The condition 2k \le n from EKR theorem also disappeared.) As we mentioned in the previous post intersecting balanced families are acyclic! And as we will see for balanced families Erdos-Ko-Rado properties translate nicely into homological property.

G) Pushing the analogy further

We made an analogy between “intersecting” and “acyclic”. Building on this analogy

1) What could be the “homological” property analogous to “every two sets have at least elements in common”?

2) What could be the “homological” property analogous to “not having r pairwise disjoints sets”?

I will propose answers below the fold. What is your answer?

Continue reading

Posted in Combinatorics, Polymath10 | Tagged , , , | 125 Comments

Polymath10: The Erdos Rado Delta System Conjecture

The purpose of this post is to start the polymath10 project. It is one of the nine projects (project 3d) proposed by Tim Gowers in his post “possible future polymath projects”. The plan is to attack Erdos-Rado delta system conjecture also known as the sunflower conjecture. We will start the research thread here. Mimicking a feature of polymath1 I will propose a detailed approach in the next post. Here, I will remind you of the conjecture and some basic known results,  mention a few observation and ingredients of my point of view, and leave the floor to you comments.

The Erdos-Rado Delta-system Theorem and Conjecture

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 one of the sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that

Erdos-Rado Delta-syatem 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.

(We denote by f(k,r) the smallest integer that suffices for the assertion of the theorem to be true.) The simple proof giving f(k,r)\le k! (r-1)^k can be found  here.

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. It may be also the case that we can take C_r=Cr for some absolute constant C. The conjecture is already most interesting for r=3. And getting progress for r=3 will already be great.

At least for r=2 the delta system conjecture is true. Every two sets form a Delta-system of size two. So f(k,2)=1. Can we find more difficult proofs and for weaker statements? The case r=2 will play a role in the context of more general questions.

The best known upper bounds

An excellent review paper is Extremal problem on Δ-systems by Alexandr Kostochka. After an early paper by L. Abbott, D. Hanson, and N. Sauer imroving both the upper and lower bounds, Joel Spencer proved an upper bound of f(k,r) \le C(1+\epsilon)^kk! for every fixed r. Spencer also proved an upper bound e^{k^{3/4}}k! for r=3. (The exponent was improved further to 1/2 by Furedi and Kahn.) A remarkable result by Sasha Kostochka from 1996 is the best upper bound known today.

kostochka

sasha

Sasha Kostochka

A summary of my proposed approach:

I. A more general problem

Given a family F of sets and a set S,  the star of S is the subfamily of those sets in F containing S, and the link of S is obtained from the star of S by deleting the elements of S from every set in the star. (We use the terms link and star because we do want to consider eventually hypergraphs as geometric/topological objects.)

We can restate the delta system problem as follows: f(k,r) is the maximum size of a family of k-sets such that the link of every set A does not contain r pairwise disjoint sets.

What can we say about families of k-sets from {1,2,…,n} such that that the link of every set A of size at most m-1  does not contain r pairwise disjoint sets? In particular, what is f(k,r,m;n) the maximum number of sets in such a family. We can ask

Question 1: Understand the function f(k,r,m;n).

Question 2: Is it true that f(k,r,m;n)\le C_r^{k}n^{k-m}, where C_r is a constant depending on r, perhaps even linear in r.

My proposal is to approach the Delta-system problem via these questions. We note that Question 1 includes the Erdos-Ko-Rado theorem:

(r=2, m=1) Erdös-Ko-Rado Theorem: An intersecting of k-subsets of N, when 2k \le n contains at most {{n-1} \choose {k-1}} sets.

Here,  a family of sets is “intersecting” if every two sets in the family has non empty intersection. The situation for r=2 and general m was raised by Erdos-Ko-Rado (who proposed a conjecture for a certain special case), Frankl proposed a general conjecture that was settled by Alswede-Khachatrian. This was a remarkable breakthrough. The case of general r and m=1 is again a famous question of Erdos.  The conjecture is that when n \ge rk, f(k,r,0,n)=\max ({{rk-1} \choose {k}}, {{n} \choose{k}}~-~{{n-r} \choose {k}}). This is a classic result by Erdos and Gallai (1959) for graphs (k=2), and very recently it was proved for r=3 for large values of n, in the paper On Erdos’ extremal problem on matchings in hypergraphs  by Tomasz Luczak, and Katarzyna Mieczkowska, and for all values of n by Peter Frankl.

We want much weaker results (suggested by Problem 2) than those given (or conjectured) by Erdos-Ko-Rado theory, but strong enough to apply to the Delta system conjecture.

II. moving to the multipartite case

A family of k-sets is balanced (or k-colored) if it is possible to color the elements with k colors so that every set in the family is colorful.

Reduction (folklore): It is enough to prove Erdos-Rado Delta-system conjecture for the balanced case.

Proof: Divide the elements into d color classes at random and take only colorful sets. The expected size of the surviving colorful sets is k!/k^k|F|.

III: Enters homology

A family F of k-sets is acyclic (with Z2 coefficient) if it contains no k-cycle. A k-cycle G is a family of k-sets such that  every set of size (k-1) is included in an even number of k-sets in G.

Theorem 1: An acyclic family of k-subsets of [n], contains at most {{n-1} \choose {k-1}} sets.

I suppose many people ask themselves:

Question 3: Are there some connections between the property “intersecting” and the property “acyclic?”

Unfortunately, but not surprisingly intersecting families are not always acyclic. And acyclic families are not always intersecting.(The condition 2k \le n from EKR theorem also disappeared in the result about acyclic families.)

Lets ignore for a minute that being acyclic and being intersecting are not related and ask.

Question 4: Is there some “acyclicity” condition related to (or analogous to) the property of not having 3 pairwise disjoint sets? r pairwise disjoint sets?

We know a few things about it.

Question 5: What can we say about families which are acyclic and so are all links for every set A of size at most m-1?

Here under some additional conditions there are quite a lot we can say in a direction of bounds asked for in Question 2.

(We note that one place where  a connection between homology and Erdos-Ko-Rado theory was explored successfully is in the paper Homological approaches to two problems on finite sets by  Rita Csákány and Jeff Kahn.)

IV) Coloring to the rescue!

Relating acyclicity and being intersecting is not easy in spite of the similar upper bound. We can ask now if for  balanced families,  there are some connections between the property “intersecting” and the property “acyclic?”

Question  6:    Let F be a balanced intersecting family of k-sets, is K acyclic?

The answer is yes. Eran Nevo pointed out a simple inductive argument which also extends in various directions.  If you have a balanced k-dimensional cycle (mod Z/Z2) then by induction the link of a vertex v (which is also a cycle) has two disjoint sets R and R‘  and taking one of those sets with v and the other set with yet another vertex w  yield a disjoint pair. (Each set of size k-1 in a cycle must be included in more than one sets of size k; in fact this is the only fact we are using.)

On technical matters: The project will run over this blog and Karim Adiprasito will join me in organizing it. (Perhaps to make the mathematical formulas appearing better we will move to another appearance.)

Posted in Combinatorics, Polymath10 | Tagged , , , | 137 Comments

Convex Polytopes: Seperation, Expansion, Chordality, and Approximations of Smooth Bodies

app2

I am happy to report on two beautiful results on convex polytopes. One disproves an old conjecture of mine and one proves an old conjecture of mine.

Loiskekoski and Ziegler: Simple polytopes without small separators.

Does Lipton-Tarjan’s theorem extends to high dimensions? Can polytopes be expanders?

Lipton and Tarjan proved that a planar graph (hence the graph of a 3-polytope) with n vertices can be separated to connected parts each with no more than 2n/3 vertices by deleting C\sqrt n vertices. I proposed a similar property (with a different exponent depending on the dimension) for graphs of simple polytopes in higher dimensions. This turned out to be false.

Simple polytopes without small separators:

Lauri Loiskekoski, Günter M. Ziegler

Abstract:  We show that by cutting off the vertices and then the edges of neighborly cubical polytopes, one obtains simple 4-dimensional polytopes with n vertices such that all separators of the graph have size at least \Omega(n/log^{3/2}n) This disproves a conjecture by Kalai from 1991/2004.

A major remaining open question is if we can have examples of graphs of simple 4-polytopes where every separator has at least cn vertices or perhaps even examples of such graphs that are expanders. (I conjecture that the answer is negative).

Expansion is closely related to diameter and there are various interesting higher dimensional analogs for the expansion property, for diameter question, and for the non-revisiting property which is crucial in the study of diameter of polytopal graphs.

Adiprasito, Nevo and Samper: Higher chordality and approximating smooth bodies by polytopes.

Consider a sequence of polytopes P_n that converge to a smooth convex body K. It is easy that the number of vertices of these polytopes must tend to infinity and there are interesting theorems relating the quality of the approximation and the the number of vertices.

For a d-dimensional simplicial polytope P there are is remarkable set of parameters introduced by McMullen (g_1(P),g_2(P),\dots g_m(P)) where m=[d/2]. g_1(P) is the number of vertices minus (d+1).  g_2(P) is the dimension of the space of stresses of a framework based on P. The nonnegativity of these numbers is the generalized lower bound theorem which is part of Stanley’s 1980 “g-theorem” (necessity part), which is one of the most important results on convex polytopes in the last decades. Here on the blog we devoted several posts (I,II,III,IV) to the g-theorem and the related g-conjecture for simplicial spheres. (Probably the g-conjecture for spheres is the single problem I devoted the most effort to in my career.)

I conjectured that for a sequence of polytopes P_n that converge to a smooth convex body K, g_i(K) tends to infinity for ≤ [d/2]. This was now proved.

app1

Higher Chordality III: A Geometric Lower Bound Theorem

Karim A. Adiprasito, Eran Nevo, José Alejandro Samper

Abstract: We resolve a conjecture of Kalai relating approximation theory of convex bodies by simplicial polytopes to the face numbers and primitive Betti numbers of these polytopes and their toric varieties. The proof uses higher notions of chordality. Further, for C^2-convex bodies, asymptotically tight lower bounds on the g-numbers of the approximating polytopes are given, in terms of their Hausdorff distance from the convex body.

The paper continues a project which led already to:

Higher chordality I. From graphs to complexes by Karim A. Adiprasito, Eran Nevo, Jose A. Samper and

 

Further extensions for general polytopes, and similar results regarding the nonlinear part of the g-theorem would be of great interest.

More news in brief

A polymath10 project devoted to the Erdos Rado Delta System Conjecture will start over this blog in about a week. (This is one of the project proposals by Tim Gowers in this post.)  Quanta magazine has an article on important progress by Maria Chudnovsky, Irene Lo,  Frédéric Maffray, Nicolas Trotignon and Kristina Vušković towards an efficient coloring argorithm for perfect graphs! (BTW, while we have several notions of chordality in high dimensions I am curious about appropriate notions of perfectness.)  In this MathOverflow answer, I report (and describe the background) on the 2013 paper by Zdeněk Dvořák, Jean-Sébastien Sereni, Jan Volec   “Subcubic triangle-free graphs have fractional chromatic number at most 14/5“.  This recent mathoverflow question asks for proposals for polymath projects.

 

$latex \Omega(n/log^{3/2}n)$.

Posted in Combinatorics, Convex polytopes | Tagged , , , , | 1 Comment

Igor Pak’s collection of combinatorics videos

The purpose of this short but valuable post is to bring to your attention

Igor Pak’s Collection of Combinatorics Videos

igor

Posted in Combinatorics | Tagged | Leave a comment