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 and . 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 is a family of sets 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 so that every family of -sets with more than members contains a sunflower of size .

We denote by the smallest integer that suffices for the assertion of the theorem to be true.

### The Erdos-Rado Sunflower Conjecture

**The Erdos-Rado sunflower conjecture: ** .

Here, is a constant depending on . It may be also the case that we can take for some absolute constant *C*. The conjecture is already most interesting for . 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 be the maximum size of a family of -subsets of* [n]=* containing no sunflower of size with head of size at most . (Note: it should me .)

**Basic Question**: Understand the function *f(k,r,m;n)*. Is it true that , where is a constant depending on *r*, perhaps even linear in *r*.

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

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

**C)** **The balanced case**

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

Let be the maximum size of a balanced family of -subsets of* [n]=* containing no sunflower of size with head of size at most . By randomly dividing the ground set into colors we obtain that .

**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

(*)

The alternative version would give

(**)

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

**E) Simplicial complexes and homology**

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

The definition of homology groups only depends on the combinatorial data. For simplicity we assume that all sets in (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 -dimensional chains as a vector space generated by i-faces of K. We also define a boundary map for every . The kernel of is the space of i-cycles denoted by ; the image of is the space of i-boundaries, denoted by . The crucial property is that applying boundary twice gives you zero, and this allows to define homology groups . The betti numbers are defined as . We will give the definition of the boundary operator further below.

**F) Acyclic families and intersecting families**

A family of -sets is acyclic if it contains no -cycle, or equivalently if . (For coefficients in , a -cycle is a family of -sets such that every set of size is included in an even number of -sets in .)

**Proposition**: An acyclic family of* k*-subsets of* [n]*, contains at most 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 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 *m *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?