Polymath 10 Post 3: How are we doing?

Posted on December 8, 2015 by Gil Kalai

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

This entry was posted in Combinatorics, Mathematics over the Internet, Open problems, Polymath10 and tagged , . Bookmark the permalink.

104 Responses to Polymath 10 Post 3: How are we doing?

  1. gowers says:
    December 9, 2015 at 1:55 am

    Reading your post made me think of a reformulation, though it doesn’t feel new and may have been mentioned in one of your posts or one of the comments on them.

    Suppose we have a collection of k-sets A_i. Let us think of each A_i as a characteristic function mod 3. Then a sunflower corresponds to three sets A_i,A_j,A_k such that A_i+A_j+A_k takes values 0 and 1. So we have a collection of sets and the statement that it is 3-sunflower free is an arithmetic condition about the sumset mod 3. If all the sets belong to \mathbb{F}_3^n, then we want a collection X of elements of \{0,1\}^n where every element of X has support size k and X+X+X\cap\{0,1\}^n=\emptyset.

    So it’s just conceivable that some kind of additive combinatorial techniques could be brought to bear. Unfortunately, the condition that the supports have size k is not very nice.

    Reply
    • daeseoklee says:
      December 9, 2015 at 1:45 pm

      That was what I observed too. I also thought that it can be reformulated as an analytic question. Similarly make characteristic vectors for each set, then the sunflower problem becomes finding three different vectors such that s (u,v,w)=u•v+v•w+w•u-3u•v•w=0, (here u•v•w represents sum of coordinate wise products.) This can be generalized to a collection of vectors with coordinates in interval [0,1], bounded size (number of element condition),and some distance condition(distinguishing condition), then the problem is finding vectors such that s (u,v,w)<1

      Reply
    • gowers says:
      December 9, 2015 at 10:01 pm

      There are two natural weakenings of the question. One is to drop the condition that the sets have size k. So now one would be asking how large a subset of \{0,1\}^n (regarded as a subset of \mathbb{F}_3^n) is it possible to have with no solution to x+y+z\in\{0,1\}^n. This is strongly reminiscent of the cap-set problem, but there are two differences: we restrict x,y and z to \{0,1\}^n, and instead of forbidding x+y+z to equal 0 we forbid it to belong to \{0,1\}^n.

      Another thing we could do is drop the first of these conditions, and merely ask how big a subset X of \mathbb{F}^n one can find such that X+X+X\cap\{0,1\}^n=\emptyset.

      Obviously these variants won’t directly solve the sunflower question, but they seem close enough to it to be worth thinking about.

      Reply
      • daeseoklee says:
        December 10, 2015 at 5:19 am

        the case dropping the size condition, I got a exponential lower bound (with respect to the background set) by a simple probabilistic argument. If I havent made mistake, for 3-sunflower case, we can get a constant times (1-2/(3 sqrt (3)))^(-n/3) lower bound. I guess the maximum is also exponential

      • daeseoklee says:
        December 10, 2015 at 5:26 am

        Ah, it was just obviously exponential. 2^n. I was a fool

      • daeseoklee says:
        December 10, 2015 at 12:48 pm

        Get random subsets X_1,..,X_k of [n] by involving each element with a probability 0<p<1.
        I'll directly calculate the probability of X_1,…,X_k forming a k-sunflower.
        First, given S⊂[n] (|S|=s), T⊂[n]\S (|T|=t) calculate probability P_{S,T} of S to be the core of sunflower, and T=∪(X_i\S). (Thus, X_i\S are disjoint).
        By an easy induction, it can be seen that there are k^t choice of multiple (X_i\S).(ordered partition of T into k sets). Given a multiple, let t_i=|X_i\S|. We have \sum t_i=t. Then
        P_{S,T}=k^{t}*\bigprod_{i=1}^{k}p^{s+t_i}(1-p)^{n-s-t_i}=p^{ks}(1-p)^{k(n-s)}*k^{t}*(p/(1-p))^{t}
        Then Since the events of P_{S,T} are disjoint, (desired probability)=
        \sum{s=0}^{n}\binom{n}{s}\sum{t=0}{n-s}\binom{n-s}{t}p^{ks}(1-p)^{k(n-s)}*k^{t}*(p/(1-p))^{t}
        =\sum{s=0}^{n}\binom{n}{s}p^{ks}(1-p)^{k(n-s)}*(1+{kp}over{1-p})^{n-s}
        = p^{kn}(1+p^{-k}(1-p)^{k}+p^{-k}(1-p)^{k}{kp}over{1-p})^{n}=(p^{k}+(1-p)^{k}+kp(1-p)^{k-1})^{n}
        We want to minimize the value p^{k}+(1-p)^{k}+kp(1-p)^{k-1} Differentiating, it follows that p={l}over{l+1} where l=(k-1)^{{1}over{k-2}} gives minimum. at this case, the probability becomes ({l^{k}+kl+1}over{(l+1)^k})^n. Let we have m random subsets of [n]. We have (m choose k) of above event we calculated. And the probability that considerable amount of the sets are equall is so small. Using lovasz local lemma, we can get a lower bound around a constant of ({(l+1)^{k}}over{l^{k}+kl+1})^{{n}over{k-1}}

    • Gil Kalai says:
      December 9, 2015 at 10:43 pm

      Let me mention that there are some connections between the sunflower conjecture and the cup set conjecture, and also that there is an important variant of the sunflower conjecture (The weak sunflower conjecture by Erdos and Szemeredi)that does not refer to k. See this post Cap Sets, Sunflowers, and Matrix multiplication, describing briefly  the paper On sunflowers  and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens, which rely on an earlier paper Group-theoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans .

      The paper describes a subtle implication diagram of conjectures which make it very challenging to guess the truth.

      sun-cup-omega

      Reply
      • Uwe Stroinski says:
        December 11, 2015 at 6:22 pm

        When I was mentioning the above work of Cohn et al shacharlovett commented on it. As a a non-expert in this field, I am puzzled about the status of this paper. Is it peer reviewed and published?

  2. Pingback: attack on/ of the sunflowers! | Turing Machine

  3. daeseoklee says:
    December 9, 2015 at 2:36 pm

    Another approach. Think about this much much easier problem.
    Let’s call {X_1,…,X_i} (i≥3) a circular sunflower if C=X_1∩X_2=X_2∩X_3=…=X_{i-1}∩X_i=X_i∩X_1,
    and C the core of it.
    Let |X_i|=k (i=1,..,n) and ∪X_i=[m] a family without any circular sunflower.
    For A⊂[m], |A|≤k, Let G_A be the graph whose vertex set is the set
    of X_i containing A, and two vertices are connected iff their intersection is exactly A.
    Let |V(G_A)|=n_A, |E(G_A)|=e_A.
    By the cicular sunflower-free condition, all these graphs become forests,
    so we get e_A≤n_A. From two double counting arguments, we get
    n(n-1)/2=\sum e_A≤\sum n_A=n*2^k, n≤1+2^{k+1}.

    But obviously, for sunflowers, this cannot be applied, since even complete
    bipartite can be possible for G_A, there’re no limits on number of edges.
    But we do have some restrictions.
    The graphs G_A, can be seen as ‘disjointness’ of some sets.
    For disjointness graphs, there is a theorem by Bollobas(Gowers’ supervisor, right?).
    The theorem says,

    |A_i|=a, |B_i|=b (i=1,…,n), A_i∩B_i are all disjoint, (A_i, B_j) intersects for all i≠j
    implies n<(a+b-2 choose a-1).

    I expect this is not the only restriction for disjointness graphs.
    And I think it will be worth seeking for those.
    But the fact is that only these relations for individual graphs are not enough.
    (Worst case, all could be complete bipartite, give no useful inequality)
    But hopefully, there seems to be some useful relation 'between' the G_A s.
    For example, if A⊂B, V(G_B) becomes an edge indpendent subset of V(G_A).
    Summing up these and possibly more relations, I hope we can do something

    Reply
  4. Gil Kalai says:
    December 14, 2015 at 1:10 am

    Going back to the homological approach. I think one challenge would be to understand well the situation for (2,2)-cycles. The claim is that for balanced families a (2,2) cycle contains two sets whose intersection is either empty or has exactly one element in common. Actually I claimed https://gilkalai.wordpress.com/2015/11/11/polymath10-post-2-homological-approach/#comment-22682 that an inductive argument applies (and even to the (b,b)-case). I dont see the argument now but it is late and I will come to it tomorrow. So the plan (mainly for myself, I suppose) would be

    1) (2,2) by induction; then (b,b) by induction (for combinatorial cycles)
    2) Alternative understanding (2,2) algebraically in terms of homologies of links.
    3) combinatorial (4,2) cycles contain a sunflower of size 3 with head of size at most 1.

    Reply
    • Gil Kalai says:
      December 15, 2015 at 2:30 pm

      Indeed the (b,b) case is easy by induction. For combinatorial cycles: (b,b) cycle of b-sets is simply a collection of more than one set of size b. (b,b)-cycles of k-sets for k \ge b is a collection so that every link of a vertex is a (b,b)-cycle. We need to show that a balanced collection of k sets which is a (b b) cycle has two sets with intersection smaller than b. This is obvious for b=k because there a (b,b) cycle has more than one set. We apply it by induction to a link of a vertex. We find in the links two sets with intersection smaller than b. There is nothing to do unless the intersection in the link has b-1 elements. Adding the linked vertex this gives us two sets A and B whose intersection T is of size b. Now C=A\B has k-b elements and its link being a (b,b)-cycle must contain another set T’. The elements of T and T’ are colored with the same colors so T’ is disjoint from B\A. If A’ = A \B union T’ then A’ is in the family and its intersection with B has less than b elements.

      As I said an additional task even for the (2,2) case is to give another derivation which gives a (2,2) conclusion based on “(1,1) properties” for the family and links.

      Reply
    • Gil Kalai says:
      December 16, 2015 at 12:04 am

      I suppose our next task is to show that a family of k-sets which is a combinatorial (4,2)-cycle must contain a sunflower of size 3 with head of size 0 and 1.

      For k=2 a combinatorial (4,2) cycle is a collection with more than 6 pairs. For larger k we need to assume that the link of every set of size (k-2) has more than 6 pairs. (In other words, every set of size (k-2) is included in no k-set or in more than 6 k-sets from the family.)

      Any volunteers to try to show it?

      Reply
  5. domotorp says:
    December 14, 2015 at 1:50 am

    I wanted to propose a computer program to be written that searches for symmetric constructions for small values. What I mean by symmetric is that for r=3 and small k, all the best known families are such that they are on just a few elements and the sets of the family can be obtained from each other through applying a small permutation group to the elements. So for example, for k=4, one could try to search for an intersecting sunflower-free family on 10 elements by enumerating all permutation groups of size at most 30 or so, and check whether they yield a solution. Unfortunately, I really have no clue how many such groups there are and I don’t have enough confidence in my coding skills to attempt to write such a program, but maybe someone else is more talented.

    Reply
    • Philip Gibbs says:
      December 14, 2015 at 6:58 pm

      I’d like to do more computer searches but am otherwise occupied right now.

      One idea was to continue the random approach but as well as adding random sets until no more can be added you can then randomly delete some and try to replace with more.

      Another idea more similar to the symmetry one is to do a search for linkwise complete families, i.e. where each link (defined earlier as subfamilies sharing a subset with that subset removed) is maximal/complete. Most of the biggest families take this form and it may be possible to build them up efficiently by joining together families with smaller k.

      Reply
  6. vegafrank says:
    December 19, 2015 at 12:21 am

    THE P VERSUS NP PROBLEM

    We define an interesting problem called $MAS$. We show $MAS$ is actually a succinct version of the well known $\textit{NP–complete}$ problem $\textit{SUBSET–PRODUCT}$. When we accept or reject the succinct instances of $MAS$, then we are accepting or rejecting the equivalent and large instances of $\textit{SUBSET–PRODUCT}$. Moreover, we show $MAS \in \textit{NP–complete}$.

    In our proof we start assuming that $P = NP$. But, if $P = NP$, then $MAS$ and $\textit{SUBSET–PRODUCT}$ would be in $\textit{P–complete}$, because all currently known $\textit{NP–complete}$ are $\textit{NP–complete}$ under logarithmic-space reduction including our new problem $MAS$. A succinct version of a problem that is complete for $P$ can be shown not to lie in $P$, because it will be complete for $EXP$. Indeed, in Papadimitriou’s book is proved the following statement: “$NEXP$ and $EXP$ are nothing else but $P$ and $NP$ on exponentially more succinct input”. Since $MAS$ is a succinct version of $\textit{SUBSET–PRODUCT}$ and $\textit{SUBSET–PRODUCT}$ would be in $\textit{P–complete}$, then we obtain that $MAS$ should be also in $\textit{EXP–complete}$.

    Since the classes $P$ and $EXP$ are closed under reductions, and $MAS$ is complete for both $P$ and $EXP$, then we could state that $P = EXP$. However, as result of Hierarchy Theorem the class $P$ cannot be equal to $EXP$. To sum up, we obtain a contradiction under the assumption that $P = NP$, and thus, we can claim that $P \neq NP$ as a direct consequence of the Reductio ad absurdum rule.

    You could see more on (version 3)…

    https://drive.google.com/file/d/0B3yzKiZO_NmWZ1M1MkNuYVBreXc/view?usp=sharing

    Best Regards,
    Frank.

    Reply
  7. Gil Kalai says:
    December 22, 2015 at 3:11 pm

    Let me make a few more comments on the combinatorial version of the homological (balanced) approach. The first unknown case is this statement:

    For k=2 a combinatorial (4,2) cycle is a collection with more than 6 pairs. For larger k we need to assume that the link of every set of size (k-2) has more than 6 pairs. (In other words, every set of size (k-2) is included in no k-set or in more than 6 k-sets from the family.) We want to prove that a combinatorial (4,2)-cycle has a sunflower with 3 petals and head of size 0 or 1.

    Suppose we want to prove it by induction. If k>2, the link of a vertex of a (4,2)-cycle is a (4,2) cycle. So by induction the links have a sunflower with head of size 0 or 1.

    If the head is empty we are done. Otherwise we have a sunflower {A,B,C} with head of size 2. Let a and b be the vertices in the head. Let A’ B’ and C’ be the petals minus the head. The link of A’ B’ and C’ are three bipartite graphs (with the same parts).

    They have the properties that

    1) They share an edge {a,b}

    2) Each contains in addition 6 more edges.

    We want to find a sunflower of three edges – one from each graph. Is this always possible?

    Dömötör shot down a similar statement but not quite (yet) this one.

    The sequence of weaker and weaker working conjectures from last time could have been useful also for such an inductive statement (although I had a different intention for them) but Dömötör shot them down too.

    Reply
  8. Gil Kalai says:
    December 22, 2015 at 10:18 pm

    So far, we mainly talked about the following sub-strategy for the homological idea (just for the balanced case): Recall that we want to conclude from not having a certain sunflower that certain (top) homology vanishes. In other words we want to show that every “cycle” contains a required sunflower. What we did next was to replace the homological cycle by combinatorial cycle. The claim that every combinatorial cycle must have a sunflower is a stronger statement, but hopefully it will admit a combinatorial argument.

    The most optimistic view of the arguments we had was that it will allow by induction to move from the case of families of k-sets where we forbid a sunflower with head of size smaller than m to the case where k=m. This would be very nice (and we are stacked even for r=3 and m=1) but, without more ingredients, it will only reduce the more general problem (with m) to the original sunflower question (without m).

    I want to devote two remarks to explain better the homological notion of cycles and homology, Why there are already useful to draw conclusions (in some very simple cases that we considered) and what we can hope for them when we forbid sunflowers.

    Reply
  9. Gil Kalai says:
    December 22, 2015 at 11:01 pm

    So here is the first comment.

    Let’s consider balanced families F of k-subsets from [n] and the following four statements

    (1) F does not contain r pairwise disjoint sets (or in a more complicated way: no sunflower of size r with head of size smaller than 1.)

    (2) F does not contain a combinatorial (r-1,1) cycle

    (3) F does not contain a homological (r-1,1) cycle

    (4) |F| \le {{n} \choose {k}}-{{n-r+1} \choose {k}}.

    We recall the definitions

    A combinatorial (b,1)-cycle of k-sets is a collection of k-sets such that every (k-1)-set which is included in one k-set from the family is included in at least b+1.

    To define a homological (b,1) cycles we need to consider b generic boundary operators from (k-1)-chains [namely linear combinations of k-sets] to (k-2)-chains.

    A homological (b,1)-cycle is a collection of k-sets so that you can assign to them nonnegative weights so that the resulting linear combination vanishes when we apply each one of these b boundary operators.

    We have the following implications:

    For every family of k-sets (here we do not need the family to be balanced) (2) implies (3) and (3) implies (4). The implication (2) implies (3) is easy linear algebra. (3) implies (4) is also not a difficult linear algebra argument. What is a little surprising is that the proof of the implication (2) implies (4) requires essentially moving through (3). (Essentially, the only known arguments are based on linear algebra and some sort of generic vectors, although the homology nature of it can be hided.)

    For balanced families (1) implies (2) (and therefore also (3) and (4)) The implication from (1) to (2) was explained here: https://gilkalai.wordpress.com/2015/11/11/polymath10-post-2-homological-approach/#comment-22581

    Reply
    • Gil Kalai says:
      December 22, 2015 at 11:34 pm

      Before moving to the second comment let me mention that when r=2, Condition (2) asserts that the simplicial complex defined by the family, collapses to its codimension one skeleton. (The simplicial complex is (k-1)-dimensional so it collapses to the (k-2) skeleton.) Condition (3) asserts that the top ((k-1)-dimensional) homology of the simplicial complex vanishes.

      Going back to general values of r, we comment that for general families, (4) is a sharp consequence from (2) and (3). For balanced families stronger inequalities are possible but I dont know what is the sharp upper bound. (This is an interesting extremal question.)

      Reply
  10. Gil Kalai says:
    December 22, 2015 at 11:41 pm

    Let me move now to the second comment. Before a detailed comment here is a piece of motivation. We can think about a different path to go (again, for balanced families):

    From
    (i) Conditions on no sunflowers TO
    (ii) global and local homological conditions TO
    (iii) conclusion about no (b,c) homological cycles TO
    (iv) Consequences on the size of the family.

    The first place to try it would be for cases where we already know even stronger conclusion on (iii) regarding combinatorial cycles.

    Reply
    • Gil Kalai says:
      December 24, 2015 at 11:58 pm

      Now, lets consider the property of a balanced family F of k-sets of not having a sunflower of size r=2 with head of size smaller than m. And let’s take m=2. We already know that F does not contain a combinatorial and hence a homological (2,2) cycle (and (m,m) cycle in the more general case.) But we want to give a direct homological argument. We have two reasons for that:
      First the inductive argument we have for that case does not extend to the case r=3, m=2. So we are stacked. It seems that in any case we need to assume the case k=m as a basis to an induction argument. Let use F to denote also the simplicial complex spanned by sets in the family.

      Here is how the argument goes.
      We know that an intersecting (balanced) family is acyclic,
      To show that F does not contain a (2,2) cycle it is enough by the theorem mentioned in post 2 to show that

      1) The top ((k-1)-dimensional) homology for F vanishes
      2) The top ((k-2)-dimensional) homology of every link of a vertex of F vanishes.
      3) The (k-2)-dimensional homology for F vanishes

      Property 1) follows from the fact that F contains no pair of disjoint sets. Property 2) follows from the fact that the link of every vertex contains no pair of disjoint faces. We need to prove property 3). Namely we want to show that if F has a (k-2) cycle which is not a (k-2) boundary then it has a pair of disjoint sets.There may be various ways to go about it.

      First one remark. Note that although family of (k-2) sets which are included in sets of our original family does not contain a pair of disjoint sets this does not imply that there are no (k-2) cycles supported by F altogether because by going to sets of size (k-2) we are no longer balanced. (This may give some advantage to the alternative homological approach without the balance condition.)

      OK, so we want to show that if our family support a (k-2) cycle which is not a (k-2) boundary then it contains two sets with intersection at most 1. We can try to prove it by induction. We start with such a (k-2)-cycle supported on a minimum number of vertices. The link of every vertex v involved in this boundary does not support a (k-3) cycle which is not a (k-3) boundary – otherwise we can eliminate this vertex from the (k-2)-cycle we started with. So by induction we have two sets A and B in the link with intersection size smaller than 2. We can assume the intersection has one vertex w. In the (k-2)-cycle A\w must be included in another set C whose additional element cannot be w or v (because of the coloring). So this looks ok.

      Reply
  11. domotorp says:
    December 23, 2015 at 5:53 pm

    I would like to make a long comment on possible computer assisted ways to find good constructions for small values. We seem to have several computer programs and I was wondering if it made any sense to unify them, maybe we could have a common file on SageMath Online. Then it’s easier to improve the algorithm. Of course we would need an expert programmer to start…

    Possible improvements include to better understand the structure of maximal examples; Philip Gibbs made some conjectures about the links of vertices (https://gilkalai.wordpress.com/2015/11/11/polymath10-post-2-homological-approach/#comment-23058) and Ferdinand Ihringer about some special configurations that must appear (https://gilkalai.wordpress.com/2015/11/03/polymath10-the-erdos-rado-delta-system-conjecture/#comment-23070).

    I proposed to look for examples that are generated by some transitive permutation group (https://gilkalai.wordpress.com/2015/12/08/polymath-10-post-3-how-are-we-doing/#comment-23032); indeed, there are not that many of these (see https://oeis.org/A002106 and https://oeis.org/A000637/a000637_1.pdf), so a computer program could easily check all.

    A further possible simplification could be to try constructions for intersecting families. If we denote the size of the largest k-uniform intersecting family without an r-sunflower by f^{int}(k,r), then we have (r-1)\cdot f^{int}(k,r)\le f(k,r). In fact, if I understood well, it is even possible (though unlikely) that equality holds for all values of k and r. This is the case for all best constructions for r=3, but not for r=4, k=3 (see our wiki and Abbott-Exoo). Certainly intersecting families are easier to search for by a computer.

    Reply
  12. Gil Kalai says:
    December 27, 2015 at 10:29 am

    Looking at the next step in the homological/balanced plan what we want to prove is:

    If F is a (4,2)-cycle then F contains a 3-sunflower with head of size 0 or 1. Or, in other words, if F does not contain a 3-sunflower with head of size 0 or 1 then it is (4,2) acyclic.

    Let’s recall the definitions. We consider generic weighted boundary operators \partial_1, \partial_2,\dots. A (k-1)-dimensional chain is a linear combination with real coefficients of sets of size k. A (2,1)-cycle is a chain that vanishes when we apply \partial_1 and \partial_2. A (4,2) cycle is a chain that vanishes when we apply one after the other any two from the four boundary operators \partial_1,\partial_2,\partial_3,\partial_4.

    Lets define the space of cycles Z_k[b,c](K) as k-dimensional chains that vanishes when we apply successively each c boundary operators out of b generic boundary operators \partial_1, \partial_2,\dots.

    We also want to define homology H_k[b,c](K). In the top dimension the homology is the space of cycles, but in lower dimensions we need to mod up by some “boundaries”. for c=b=1 we are left with the usual homology.

    The theorem mentioned the comment above (and referred to in Post 2) asserts that if K is (k-1)-dimensional, and

    (1) H_{k-1}(K)=0
    (2) H_{k-2}(K)=0
    (3) H_{k-2}(lk(v,K))=0 for every vertex v

    Then Z_{k-1}[2,2](K)=0.

    We need to prove and apply a theorem of the following kind:

    If K is (k-1)-dimensional, and

    (1) H_{k-1}[2,1](K)=0
    (2) H_{k-2}[2,1](K)=0
    (3) H_{k-2}[2,1](lk(v,K))=0 for every vertex v

    Then Z_{k-1}[4,2](K)=0.

    We note that to apply such a theorem for a balanced family with no sunflower of size 3 with head of size 0 and 1 we already have parts (1) and (3) (from what we know about balanced families with no three pairwise disjoint sets). But we will have to worry about (2).

    Reply
    • Gil Kalai says:
      December 27, 2015 at 2:14 pm

      Let me give the definition of H_j[2,1](K). H_j[2,1](K)=Z_j[2,1](K)/B_j[2,1](K) where Z_j[2,1](K)=\{x \in C_j(K):\partial_1(x)=\partial_2(x)=0\}, and B_j[2,1](K)=\partial_2(\{x \in C_{j+1}(K): \partial_1(x)=0.\}).

      Reply
      • Gil Kalai says:
        December 29, 2015 at 8:16 am

        Actually the definition of the space of boundaries should be:

        B_j[2,1](K)=\{\partial_1(x)+\partial_2(y):x,y\in C_{j+1}(K),\partial_1\partial_2(x)=\partial_1\partial_2(y)=0\}.

      • Gil Kalai says:
        January 21, 2016 at 7:48 pm

        We can use both definitions. (I am not sure yet which is better.) When we use the first Conjecture A is harder and Conjecture B is easier. However, the example showing that Conjecture B is false applies to this version as well.

    • Gil Kalai says:
      December 27, 2015 at 7:37 pm

      Let me also outline what is needed for the balanced/homological approach to work for the full sunflower conjecture for r=3. We need two conjectures:

      Conjecture A: Let F be a balanced family of k-sets without a sunflower of size 3. Let K denotes the simplicial complex spanned by the family. Then for every set R and every j, H_j[2,1](lk(R,K))=0.

      Conjecture B: Let K be a (k-1)-dimensional simplicial complex such that for every set R and every j, H_j[2,1](lk(R,K))=0. Then H_{k-1}[2k,k] (K)=Z_{k-1}[2k,k](K)=0.

      Reply
      • Gil Kalai says:
        January 6, 2016 at 10:15 am

        Just to sum up the situation. Right now I don’t have an avenue for proving Conjecture A whenever j < \dim(lk(R,K)). (We know, from the previous post, that it holds when $j=\dim(lk(R,K))$. As far as I know conjecture A can hold even in the unbalanced case. As for conjecture B. I forgot that you do need to assume that K is balanced. The graph with two connected components each is a triangle does not satisfies H_{4,2}(G)=0. (It may be true for arbitrary complexes if we weakened somewhat the conclusion, for for a slight variation of the definition of weighted homology.)

  13. Gil Kalai says:
    December 29, 2015 at 11:40 pm

    I have some hopes that Conjecture A can be reduced to the case of graphs (OK even before that I probably need to be able to extend the (2,2) case in this comment to general (b,b) case), and I also expect it to be correct for graphs. So if this works this will be very nice.

    Reply
  14. Gil Kalai says:
    December 30, 2015 at 1:22 pm

    Consider the property of a balanced family F of k-sets such that

    (*) the intersection of every two sets in the family is at least of size m.

    (In other words the family does not contain a sunflower of size r=2 with head of size smaller than m.) Let K be the simplicial complex spanned by F. We want to show that

    (**) H_{k-1-j}(K)=0.

    When j=0,1,\dots m-1. For m=1 this was Nevo’s basic observation mentioned in post 1.

    Three remarks:
    1) (**) implies (but this is a difficult result) that

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

    which implies that |F| \le {{n-m}\choose {k-m}}.

    2) Given (*), we have a different proof of (***) via a simple argument for a stronger statement:

    (****) F does not contain a combinatorial (m,m)-cycle.

    3) In post 2 we thought about local homological conditions more general than (**) sufficient to derive (***), but apparently this is not needed for our purposes.

    We described the argument for (**) from (*) for m=2 in this comment. I’d like to devote the next comment for proving (**) from (*) for every m.

    Reply
  15. Gil Kalai says:
    December 30, 2015 at 4:37 pm

    Given a family F of k-sets and denoting by K the simplicial complex spanned by F, let me try to show that

    (*) the intersection of every two sets in the family is at least of size m.

    implies

    (**) H_{k-1-j}(K')=0.

    When j=0,1,\dots m-1, and when K’ is K itself or the link of some face in K. (We can regard K itself as the link of the empty face.)
    Note that we made (**) a little more general, but the older (**) applies to links implies the new, more general, (**). (We always talk about reduced homology, so H_0(K')=0 if K' is connected.)

    We know it for m=1, and once we know it for smaller values of m and k what is left to be proved for that H_{k-m}(K)=0.

    As a first step suppose that there is a set of size k-m which is included in a single set R in F. Delete R from F and repeat. This operation does not effect any of the homology groups
    of dimension (k-m) and above in K and in every link K’ of a face of K.

    Given a (k-m)-dimensional cycle x which is not a boundary we want to find two sets S, T in the family with intersection of size smaller than m. We can assume that the number of vertices on which x is supported is minimum. Let v be a vertex on which x is supported. x induces a (k-m-1)-dimensional cycle x’ on lk(v). if x’ is a boundary of y’ in lk(v) then by taking the cone over y’, x minus the boundary of this cone will be a new (k-m)-dimensional cycle which is not a boundary not involving the vertex v. By an induction hypothesis we can find two sets S’, T’ in lk(v) whose intersection has less than m elements. If the size of the intersection is smaller than m-1 we can add v to both S’ and T’ and we are done. We are left with the case that the size of the intersection of S’ and T’ is m-1. But know we can look at A=S’\T’ and B=T’\S’. Both these sets have in their link the set of size m Y=\{v\} \cup S'\cap T' But because of our preliminary step A has in the link yet another set Z of the same size m and because of the coloring this new set cannot have vertices from B. A \cup Z and B \cup X are two sets
    in the family with intersection smaller than m.

    We also have to start the induction somewhere. But we note that when K is not connected, i.e., when the 0th (reduced) homology does not vanish then we must have two disjoint sets in the family.

    What we want to do next is to consider the case r=3. Perhaps first the case r=3, m=2.

    Reply
    • Gil Kalai says:
      December 31, 2015 at 10:12 pm

      Well, there is a subtle issue with the deletion procedure at the beginning of the proof. What we actually proved is: Given a family F of k-sets which is a (m,m) -cycle and denoting by K the simplicial complex spanned by F, if

      (*) the intersection of every two sets in the family is at least of size m.

      implies

      (**) H_{k-1-j}(K')=0.

      I dont know if we can eliminate the condition of F being a (m,m) cycle.
      So it is possible that we will need to modify conjecture A above to:

      Conjecture A (modified): Let F be a balanced family of k-sets which is a (2k,k)-cycle without a sunflower of size 3. Let K denotes the simplicial complex spanned by the family. Then for every set R and every j, H_j[2,1](lk(R,K))=0.

      This will be enough with the same Conjecture B to give us what we want.

      Conjecture B: Let K be a (k-1)-dimensional simplicial complex such that for every set R and every j, H_j[2,1](lk(R,K))=0. Then H_{k-1}[2k,k] (K)=Z_{k-1}[2k,k](K)=0.

      Reply
      • Gil Kalai says:
        January 3, 2016 at 10:33 am

        For j=0 we have that H_0[2,1](K)=0 as long as K has at most two connected components. So in this case this is implied by not having three pairwise disjoint sets. (And thus from not having a sunflower of size three.)

      • Gil Kalai says:
        January 4, 2016 at 7:13 am

        In view of the comment above, we can ask if, more generally, for a family F of k-sets, and the simplicial complex K spanned by F, when F does not have two sets with intersection of size smaller than m Then H_i(K)=0 for i<m. Similarly, when F does not have a sunflower of size 3 with head of size smaller than m, perhaps H_i[2,1](K)=0 for i<m.

        Added later: Unfortunately this does not continue to hold for j=1.

  16. Eran Nevo says:
    January 2, 2016 at 10:28 am

    Indeed (*) does not imply (**), here is an example:
    let c be the boundary complex of the (k-1)-simplex T.
    For any vertex v of T consider the k-set formed by T\v and a new vertex v’.
    This gives a balanced family F of k-sets (v and v’ are colored with the same color, |F|=k) where any A,B in F intersect in k-2 elements, and c is a nontrivial (k-2)-cycle. So for k>2 this is a counterexample.

    [Gil’s proof seems to give that if balanced F has no 3-sunflower of head size < k-1 then (**) holds, but that's too weak. The point is that a vertex minimal cycle c may be of the form c=v*lk(v)+b where all vertices in the chain b are in the link of v, so lk(v) may be trivial. But if this happens for all v in c then c is just a simplex boundary; like in the example above.]

    Conjectures (B) and (modified A) imply that the condition in (modified A) is never satisfied, so it may be useful to think about (modified A) also as:
    Let F be a balanced family of k-sets without a sunflower of size 3. Let K denote the simplicial complex spanned by the family. Assume that for some set R and some j, H_j[2,1](lk(R,K)) is NOT zero.
    Then F has a (2k,k)-cycle.

    Reply
    • Gil Kalai says:
      January 2, 2016 at 8:13 pm

      Dear Eran, Yes, this is correct. The original Conjecture A is not correct (and the argument for r=2 requires an additional condition) and, as you mentioned, the modified conjecture A is a sort of counterfactual, afoer the modification Conjectures A and B do not divide the problem to two pieces but rather can be seen as a strategy for dividing the proof into two parts. It is possible that some stronger form of Conjecture B (we mentioned some ideas in post 2 when we discussed Theorems 1/2) will allow a version of Conjecture A which is not “counterfactual.”

      In any case, the status of Conjecture B is also quite interesting. It is a bold extension of the theorems for r=2 meant specifically towards the sunflower conjecture. It is quite elegant but for now I don’t have any evidence for believing that it is true.

      Reply
    • Gil Kalai says:
      January 3, 2016 at 12:02 am

      In somewhat greater generality Conjecture B asserts the following (I mainly care about s=1,2. r=s+1.)

      Conjecture B: Let K be a (k-1)-dimensional simplicial complex such that for every set R, |R|<m and every j, H_j[s,1](lk(R,K))=0. Then H_{k-1}[sm,m] (K)=Z_{k-1}[sm,m](K)=0.

      Here, H_j[s,1](K)=Z_j[s,1](K)/B_j[s,1](K) where Z_j[s,1](K)=\{x \in C_j(K):\partial_1(x)=\cdot =\partial_s(x)=0\}, B_j[s,1](K)=\{\partial_1(x_1)+\cdots +\partial_s(x_s):x_i \in C_{j+1}(K),~\partial_1\cdots \partial_s(x_i)=0, i=1,2,\dots,s\}.

      For s=1 this is true and follows from results in commutative algebra. It would be great if the there is some reduction from s=2 to s=1, namely you can move from a complex where the H_i[2,1] groups vanish to another complex where the ordinary homology H_i(K) vanish.
      For s=1 and m=2 I think there is a simple derivation and it would be very interesting to understand the case s=2 and m=2.

      Reply
    • Gil Kalai says:
      January 3, 2016 at 12:09 am

      So the simplest cases for the conjecture are:

      Case 1 (known; but i’d be happy to see a simple as possible proof): If K is (k-1) dimensional and H_{k-1}(K)=0, H_{k-2}(K)=0 and for every vertex v, H_{k-2}lk(v,K)=0 then H_{k-1}[2,2](K)=0.

      Case 1 (unknown;): If K is (k-1) dimensional and H_{k-1}[2,1](K)=0, H_{k-2}[2,1](K)=0 and for every vertex v, H_{k-2}[2,1]lk(v,K)=0 then H_{k-1}[4,2](K)=0.

      (Added later: we need to assume for the unknown case that K is balanced.)

      Reply
  17. shacharlovett says:
    January 5, 2016 at 10:45 pm

    I am interested in whether a topological approach can be useful for the special case relevant to matrix multiplication. In particular, I wonder whether the topological Tverberg theorem can be useful.

    (by the way, I am not sure if it was mentioned previously or not, but a great book on applications of tological methods in combinatorics is “Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry” by Jiri Matousek).

    Let x_0,...,x_k \in \{1,\ldots,n\}, where ideally we want k=O(\log n). The goal is to find 3 disjoint subsets with the same sum. Define a k dimensional simplex with vertices v_0,...,v_k. My question is: can we define a continuous map f:R^k \to R^d such that
    (1) d=O(\log n) (but d << k).
    (2) f(v_i)=x_i.
    (3) Intersections between disjoint faces correspond to equal sumsets (this is the tricky part)

    If so, the topological Tverberg theorem would automatically give us the required result. Maybe an easier case to consider first is a more geometrical problem, where the domain \{1,\ldots,n\} is replaced with \{0,1\}^{\log n}.

    Reply
    • Gil Kalai says:
      January 6, 2016 at 8:54 pm

      This is a very nice idea, but can you make it work when the parameters will just give a new derivation of the known bounds?

      We can try to use, either for the original problem or the variation, Tverberg’s original theorem (rather than the Topological version). The conclusion is usually not pairwise disjoint sets with equal sumsets but pairwise disjoint sets and positive weights with equal weighted sumsets. Maybe there is a way to move from weighted sumsets to weight-1 sumsets.

      A third thought about it is this. suppose you want to prove that for any m vectors x_1,\dots,x_m in (Z_3)^n there are three pairwise disjoint nonempty subsets A B and C with the same sum. Hoping for m = Cn. This is stronger than requiring a single nonempty subset X whose sum is 0. (Because we can take X as the union as A B and C.) To guarantee such an X we need only 2n+1 vectors and this can be proved easily by the polynomial method. (The first step is to ask the question as finding a non trivial solution to the equation \sum a_i^2 x_i =0..) So one idea might be to combine the polynomial method with the algebraic idea from Sarakaria’s proof of Tverberg theorem. You want to find a solution to the equation \sum_{i-1}^m a_i^2 \omega_{p(i)}a_i=0, where p(i) is in {0,1,2}, and \omega is a third root of unity. (And to guarantee that the partition according to p(i) is not trivial.)

      Reply
      • shacharlovett says:
        January 7, 2016 at 9:10 am

        regarding the third thought: since any 2n+1 points in (Z_3)^n contain a subset summing to zero, any 3(2n+1) points contain 3 disjoint sets, each summing to zero.

      • Gil Kalai says:
        January 7, 2016 at 10:51 am

        Hmm, it is hard to argue with that. I wonder by how much 6n+3 can be reduced. Perhaps even to 2n+1?

      • Gil Kalai says:
        January 8, 2016 at 10:42 am

        Yap :). One related thing I am curious about is for graphs. The 2n+1 results gives that every 4-regular graph plus an edge contains a 3-regular subgraph and also every 5-regular grapg contains a 3-regular subgraph. Taskinov prove that every 4-regular simple graph contains a 3-regular subgraph. I dont know if in these results “3-regular subgraph” can be replaced by “3-regular 3-edge colorable subgraph”.

  18. jtxidrandomno122x says:
    January 6, 2016 at 1:58 pm

    info yang sangat menarik, sepertinya harus dicoba , Aerilyn

    Reply
  19. Gil Kalai says:
    January 8, 2016 at 11:46 am

    Just to repeat/summarize how things stand regarding the homological approach. For the sunflower conjecture for r=3 we need the following two conjectures:

    Conjecture A: Let F be a balanced family of k-sets without a sunflower of size 3. Let K denotes the simplicial complex spanned by the family. Then for every set R and every j,

    (*) H_j[2,1](lk(R,K))=0.

    Conjecture B: Let K be a (k-1)-dimensional balanced simplicial complex such that for every set R and every j, H_j[2,1](lk(R,K))=0. Then

    (**) H_{k-1}[2k,k] (K)=Z_{k-1}[2k,k](K)=0.

    Remarks:

    1. As far as I know, Conjecture A may hold also without the condition that F is balanced.
    2. When F is balanced we can prove that (*) holds when j=\dim lk(R,K). Our attempts to have some inductive arguments for cases where j<\dim lk(R,K) did not succeed.
    3. For our purposes, it is enough to prove the assertion of Conjecture A when the family is a [2k,k] cycle (i.e. it violates the conclusion of Conjecture B).
    4. We can refine further the statements of Conjectures A,B. For conjecture A we can forbid sunflowers with head of size at most m, and  ask that (*) holds only  j>k-m. (For this refinement being balanced is crucial, but not sufficient.) For conjecture B we require (*) for j>k-m and want to conclude that Z_{k-1}[2m,m](K)=0.
    5. Of course, replacing [2k,k] by some [Ck,k] where C is a constant would suffice for our purposes
    6. We do not even know that (*) implies that |F| is bounded.
    7. H_j[2,1](K)=Z_j[2,1](K)/B_j[2,1](K) where Z_j[2,1](K)=\{x \in C_j(K):\partial_1(x)=\partial_2(x)=0\}, and B_j[2,1](K)=\{\partial_1(x)+\partial_2(y):x,y\in C_{j+1}(K),\partial_1\partial_2(x)=\partial_1\partial_2(y)=0\}.
    8. Z_{k-1}[2k,k](K) are those (k-1)-dimensional chains of K which vanishes when we apply successively any k out of 2k (generic) boundary operators.
    9. There are some versions of these conjectures in the language of face-rings for K where methods from commutative algebra could  apply.
    Reply
    • Gil Kalai says:
      January 8, 2016 at 12:14 pm

      We can mention what we get from some results we know for the following questions.

      1) What is the maximum size of an intersecting balanced family F of k-subsets of [n]?

      2) What is the maximum size of a balanced family F of k-subsets of [n] such that every two sets in the family have intersection of size at least m?

      3) What is the maximum size of a balanced family F of k-subsets of [n] without r pairwise disjoint sets?

      4) What is the maximum size of an acyclic balanced family F of k-subsets of [n]? (Namely, a family with H_{k-1}(K)=0 when K is the simplicial complex spanned by F.)

      5) What is the maximum size of a balanced family F of k-subsets of [n] such that H_{k-1}[m,m](K)=0?

      6) What is the maximum size of a balanced family F of k-subsets of [n] such that H_{k-1}[r-1,1](K)=0?

      Our results allow to give upper bounds for questions 1,2,3 based on upper bounds for questions 4,5,6 respectively. Using the known (sharp) upper bounds for questions 4,5,6 for general families (not necessary balanced) we get the upper bounds {n-1}\choose {k-1}, {n-m} \choose {k-m} and {{n} \choose {k}}-{{n-r}\choose{k}}, respectively. It will be very interesting to find sharp upper bounds for questions 4,5, and 6, as well as sharp upper bound for 1,2,3. (The bounds for the last three questions apply for the first three but they would not be sharp, in general.)

      Reply
  20. Ferdinand Ihringer says:
    January 8, 2016 at 3:06 pm

    I attempted to generalize the easy EKR one-line proofs for n \gg k to f(k, r, m, n). Here is a (hopefully correct!) short argument for f(k, r, m, n) \leq 10 f(k, r)^3 \binom{n-m}{k-m} if n \geq m(k-m) \binom{2k-m}{m+1} + m. So if the Erdos-Rado Conjecture is true, then also Gil Kalai’s Question 2 from his first post on Polymath 10 is true.

    Click to access erdosrado_kalaissecondquestion.pdf

    (224 KB, 3 pages)

    I tried to keep the argument simple. I guess that one can easily improve the f(k, r)^3 to f(k, r)^2 or the 10 to something close to 1. Similarly, some more effort should improve the condition on n.

    Reply
    • Gil Kalai says:
      January 9, 2016 at 6:28 pm

      Dear Ferdinand, This is very nice! I will try to read the details soon.

      Reply
    • Ferdinand Ihringer says:
      January 12, 2016 at 6:51 pm

      I would like to add the observation that we f(m, r) \binom{n - m f(m, r)}{k-m} \leq f(k, r, m, n). I do not know if this was mentioned before, but I did not look for it very carefully.

      To see this, take a set Y' with property P(m, r, m) and size f(m, r). Let Y be the set of of k-sets, which meet the union U of Y' in exactly one element of Y'. Obviously, Y' has size f(m, r) \binom{n - m f(m, r)}{k-m}. If A_1, A_2, \ldots, A_x \in Y is a sunflower with head size less than m, then A_1 \cap U, A_2 \cap U, \ldots, A_x \cap U is a sunflower with head size less than m. So as Y' does not contain a sunflower with head size less than m, Y does not.

      If n large compared to k we have approximately (unless I made some mistake)

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

      So as long as we can answer Question 2 of the first post for any m and n large compared to k, then everything should be fine. So showing Question 2 for something silly such as n > k^{k^k} and m < \log \log k is enough to answer Question 2 completely for n \gg k.

      Reply
      • Ferdinand Ihringer says:
        January 17, 2016 at 11:58 pm

        I was thinking a bit about refining my bounds. I would assume that for n \gg k there are constants c_1, c_2 such that

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

        Basically, this would imply that the conjecture should be f(k, r, m, n) \leq C_r^m \binom{n-m}{k-m} and that the problems are roughly the same. Which would be nice to to know.

        How to prove it? I think that for the suggested upper bound it might be enough to pay more attention in my proof, but maybe someone else wants to think about it as well: In my proof you get all these intersections of size m (the z \cap z'). I would like to know if the family of these m-sets satisfies property P(m, r, m). Maybe not, but I would guess that if not, then something strange happens, which will give a good bound as well.

  21. Gil Kalai says:
    January 9, 2016 at 7:24 pm

    Let me relate to a few comments by Karim Adiprasito from the first post (mainly: comment 1, comment2). Karim asked about the case that the simplicial complex K spanned by the family F has the Cohen-Macaulay property (or is closed to be Cohen-Macaulay).

    A pure d-dimensional simplicial complex K is Cohen-Macaulay if for every link of a face K’ (including the empty face where K’=K)

    (1)  H_i(K')=0 for i < \dim K'

    I.e., K’ looks homologically like a “bouquet of spheres” of the top dimension.

    Question: What is the maximum number of sets in a balanced family F of k-sets without a sunflower of size 3 (or, more generally, r) such that the simplicial complex K spanned by F has the Cohen-Macaulay property.

    We note that (for r=3, and the balanced case) the assertion of Conjecture A is satisfied. For a pure simplicial complex K of dimension d

    (2)  H_i(K)=0 implies H_i[2,1](K) = 0.
    (Later change: the implication arrow fixed.)
    This is because always (4) Z_i[2,1](K) \subset Z_i(K) and  (5) B_i(K) \subset B_i[2,1] (K). (4) is immediate and for (5) note that if a \in B_i(K) then a=\partial _1 (b) and \partial_2\partial_1 (b)= \partial_2 (a) which vanishes by definition if  a \in Z_i[2,1](K).

    Two remarks

    1. The homologies H_i[a,b](K) are a variation of “iterated homology groups” that I studied and also Art Duval and Lauren Rose. They are also related to algebraic shifting based on the exterior algebra. The Cohen-Macauly property is classically also  described in terms of the face ring of K and is related to algebraic shifting based on the symmetric algebra.  There are “symmetric algebra” analogs to these homology groups which could be more convenient to study (especially for the Cohen-Macaulay case.) Those are based as Karim mentioned on several linear differential forms in the face ring. (Here is the link to my paper on algebraic shifting (and itterated homology groups), and to Duval and Rose’s paper.)
    2. Let me also mentioned that the one and only Shmuel who visited HUJI for the fall term asked about homology with respect to a (single) weighted boundary operator over a ring of coefficients e.g. over \mathbb Z. The case that all weights equal to sum p might already be of interest. (Over a field, when the weights are non-zero,  the homology does not depend on the weights. With zeros you get an interesting mixture of combinatorics and algebra.)
    Reply
  22. Gil Kalai says:
    January 11, 2016 at 2:16 pm

    Conjecture B is incorrect and the local homological conditions (*) do not suffice to imply that K is bounded (so certainly not condition (**)). To see this consider a balanced triangulation of a (k-1) dimensional sphere. For all links K’ and every i \dim H_i(K') = 1 if i=\dim K' and H_i(K)=0 if i < \dim K' which implies (I think) that for every i and K' H_i[2,1](K')=0.

    Reply
  23. domotorp says:
    January 16, 2016 at 6:41 pm

    I was thinking of some kind of linear algebra approach to the problem using the following observation. Denote the base set by X and let x_i be the indicator for x\in X being in F_i, the i-th member of our family. Observe that F_i,F_j,F_h form a 3-sunflower if and only if \forall x\in X x_ix_j+x_jx_h+x_hx_i\equiv 0 (mod 3). Thus having a sunflower-free family is almost the same as \sum_x x_ix_j+x_jx_h+x_hx_i\not\equiv 0 for each triple i,j,h.

    We can use this, for example, to construct a graph G whose vertices are the sets, and there is an edge between F_i and F_j if \sum_x x_ix_j \equiv 0. Using G, we can show that there is a unique extreme sunflower-free family for k=2 (which is anyhow not that hard to prove).
    If we have six sets, then we have a triangle in G or its complement. But for k\le 3, an edge means that the two sets are disjoint, so a triangle would mean 3 disjoint sets. An empty triangle in a sunflower-free family for k=2 can only mean 3 sets that look like \{x,y\}, \{y,z\}, \{z,x\}. No other set can be adjacent to x,y or z, so our 3 sets are connected in G to everyone else. That means that in the rest of the graph there are no edges (or we would have a triangle), so again we have an empty triangle.

    I wonder if this \sum_x x_ix_j mod 3 function is useful to prove deeper results, either using the above defined graph, or the polynomial method, or some incidence matrix approach. By incidence matrix, I mean a matrix M whose rows are indexed by the sets, the columns by the elements, and thus in M^TM the values \sum_x x_ix_j appear (thus the diagonal will be all k).

    Reply
    • Ferdinand Ihringer says:
      January 19, 2016 at 3:22 pm

      (1) I do not see anything that would make the eigenvalue spectrum of this incidence matrix interesting. Limiting the size of this matrix should be interesting, but then I come to (2).

      (2) Can you somehow make the “almost” more precise? In general it looks more restrictive than the original equality. At least when I tried to write down example for incidence matrices.

      Reply
      • domotorp says:
        January 19, 2016 at 5:11 pm

        A 3-sunflower F_i,F_j,F_h implies that \sum_x x_ix_j+x_jx_h+x_hx_i\equiv 0 but not the other way around, as shown by \{x,y\}, \{y,z\}, \{z,x\}. However, at least we know something about the intersections among the 3 sets in question that might allow us to go on. I didn’t have a deeper insight behind the almost.

      • Ferdinand Ihringer says:
        January 23, 2016 at 3:35 pm

        I still have to thank for that reply. Maybe generating large symmetric matrices M = (m_{ij}) with entries from in \{ 0, \ldots, k \} with the properties

        (1) m_{ij} + m_{jh} + m_{hi} \not\equiv 0 (\mod 3),
        (2) m_{ij} = k iff i = j,

        would be helpful? If the incidence matrices of the largest examples have any interesting properties (ranks, eigenvalues, something else?), then looking at small examples should be, as in the regular case, helpful.

    • Gil Kalai says:
      January 21, 2016 at 7:41 pm

      Dear Domotor, very interesting suggestion. I will be happy to see it developed further and think about it myself.

      Reply
    • domotorp says:
      January 23, 2016 at 8:41 pm

      After thinking more and more, I think that introducing that mod 3 was a bad idea. A much better condition is that F_i,F_j,F_h form a sunflower iff for all x we have x_ix_j=x_jx_h=x_hx_i. This implies \sum_x x_ix_j= \sum_x x_jx_h=\sum_x x_hx_i. So if you look at it from a graph point of view, we color the edges with the intersection sizes. So if the incidence matrix is I, then for M=I^TI this would mean that m_ij=m_jh=m_hi. Anyhow, this formulation becomes equivalent to looking for 3 sets that have pairwise the same intersection. What do we know about this?

      Reply
      • Ferdinand Ihringer says:
        January 24, 2016 at 8:58 pm

        So we want to color K_{\alpha} with k colors such that we have no monochromatic K_3 subgraph (replace K_3 with K_r for the general case)? So Ramsey numbers minus 1 are the largest examples?

        So for r= 3, we have for k = 2, 3, 4, 5, 6, 7 the numbers are 5, 16, 50, 161, 537, 1681. Interestingly, the best construction for k = 5 for these colorings is (with 161) better than the best known construction for our sets (160) according to the Wiki page for this project. Maybe we can use that 161-vertices example to improve the known lower bound by 1? (Yes, very ambitious!)

        In general we seem to have 3.199^r \leq R_r \leq r! (e - 1/e + 3)/2 \approx 2.67 r!. This looks very similar to the bounds on the sunflower conjecture. Also the general lower bound looks better.

        See here, page 36, for the numbers:

        http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1

        I am sure that some reader of this blog will know more about this than me. Maybe this overview paper is outdated.

      • Ferdinand Ihringer says:
        January 24, 2016 at 11:10 pm

        The bound in my previous post should read 3.199^k \leq R_k(3) \leq k! (e - 1/e + 3)/2 \approx 2.67 k!. Furthermore, “R_k(r)-1 is the size of the largest example” would be correct statement, while “So Ramsey numbers minus 1” is not.

      • domotorp says:
        January 25, 2016 at 12:14 am

        Thx for the bounds. It seems mysterious that these two parameters go so close to each other and have such similar bounds, though none of them dominates the other (at least we don’t know). Converting the 161 vertex graph sounds a little too ambitious for me. I tried and the 5 vertex graph is trivial to convert to 5 sunflower-free 2-sets, but a simple case analysis shows that the 17 vertex graph cannot give a family of 17 sunflower-free 3-sets. So I wonder if we can prove any relation between these two parameters.

      • Ferdinand Ihringer says:
        January 25, 2016 at 2:22 am

        You mean the 16 vertex graph? Ok, converting colorings to sunflowers will not work in general in an obvious way if even the 3-set case fails.

        The easiest upper bound, R_k(3) \leq 3 k!, comes from an easy inductive argument (as for f(k, 3)), which explains the k!. The polynomial lower bound is obtained by putting together smaller examples, which is again as in the sunflower conjecture case. So the upper and lower bound proofs feel the same for both problems.

        Converting between R_k(3) and f(k, 3) seems to be nontrivial. Going from R_k(3) to f(k, 3) the problem seems to be that you cannot avoid triples that have colorings such as k-1, k-1, 0. Is this still a problem if we want to go from R_k(3) to f(2k, 3)? Or some other f(ck, 3)? For some sufficiently large k' we will get enough freedom to say f(k', 3) \geq R_k(3), I suppose.

      • domotorp says:
        January 25, 2016 at 12:44 pm

        Yeah, sorry, I meant 16. Well, if k'\ge k\cdot R_3(k), that’s certainly enough, but we would need k'\le ck to prove something interesting, and I see little hope for a direct reduction. The other direction looks more promising to me, i.e., converting a 3-sunflower-free family of n k-sets to a K_{k'}-free edge 3-colored graph on n vertices.

      • Ferdinand Ihringer says:
        January 25, 2016 at 4:06 pm

        We can have many, many triples x, y, z with |x \cap y| = |x \cap z| = |y \cap z| \approx k/2, which are a problem for the coloring. Deleting some sets seems to be a bad option as then our size will go down by factors such as 1/\binom{k}{k/2} very often unless we figure out some good way of doing. Adding colors will not be interesting, because we will need too many.

        Maybe we would like to find a problem that either dominates both problems or that is dominated by both problems?

      • domotorp says:
        January 25, 2016 at 5:58 pm

        Well, being dominated by both is easy – require a family of k-sets without 3 sets whose pairwise intersections’ sizes equal. I think it might be a good start to prove an exponential upper bound for this problem.

  24. Pingback: News (mainly polymath related) | Combinatorics and more

  25. Pingback: Frankl’s union-closed conjecture — a possible Polymath project? | Gowers's Weblog

  26. Gil Kalai says:
    January 21, 2016 at 9:41 pm

    While Conjecture B failed, I have some further ideas regarding the homological approach which in a usual (little obsessive) working-on-a-project activity, I would probably pursue. I am not sure what the policy should be in a polymath projects. Opinions are welcome, (This is sort of a Meta question.) I tend to pursue it anyway, and write about it next post.

    Reply
  27. Gil Kalai says:
    January 22, 2016 at 9:29 am

    Ok, let me say briefly what the additional idea is. Let F be a family of subsets from a ground set [n]. Let G be the complement family, namely those k-subsets of [n] not in F. Let L be the simplicial complex spanned by F and L be the simplicial complex spanned by G.

    Now, our staring point was the analogy between “intersecting” and “acyclic” (namely having vanishing Z_{k-1}(K)) that we extended and tried to further extend in various directions. Let me point out a stronger homological property which might be relevant to being “intersecting.” This is the property, let’s call it “strongly acyclic” that Z_{k-1}[n-k-1,1](L)=0. (I’d like to explore if balanced intersecting families are strongly acyclic; or perhaps in the other extreme K is strongly acyclic if all its set have an element in common. )

    What we do know is that for intersecting families Z_{k-1}[k,1](K)=0 and for families with no three pairwise disjoint families Z{k-1}[2k,1](K)=0. This follows from the fact that algebraic shifting preserves the property : “does not have r pairwise disjoint set”. The counterexample to our conjecture B shows that vanishing of such homologies does not suffice.

    However, algebraic shifting provides a much stronger property: If F is intersecting then Z_{k-1}[n-2k,1](L) \ne 0 and if F does not have 3 pairwise disjoint families then Z_{k-1}[n-3k,1](L) \ne 0. This is because also algebraic shifting with respect to the reverse lexicographic order preserves the property : “does not have r pairwise disjoint set”.

    My current proposal is to deduce from the property that Z_{k-1}[n-3k,1](L) \ne 0, and the analogous properties for links the required global homological property for K.

    Reply
  28. domotorp says:
    January 31, 2016 at 5:38 pm

    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.

    For this, it is enough to show that if we have a sunflower-free k-uniform family, then we can convert it into a “pairwise same intersection size-free” ck-uniform family. So our goal is to ruin intersections that are accidentally the same, like is done in the Isolation lemma (https://en.wikipedia.org/wiki/Isolation_lemma). However, in our case, we only care about local coincidences, so our problem might be more similar to the 1-2-3 conjecture (http://www.math.illinois.edu/~dwest/regs/123conj.html). The exact formulation is as follows.

    Suppose that we have a 3-sunflower-free k-uniform family. Can we assign weights 1,\ldots,c to its vertices such that no 3 sets have pairwise the same weighted intersection size?

    ps. Note that we needn’t require that the new family is uniform, we can achieve that by adding at most k more weighted vertices to each set.

    An optimistic approach would be to show that to any family we can assign weights that kills all triples with pairwise the same intersection size, unless they form a sunflower. Unfortunately, this isn’t true; already for k=2 the family whose sets are the edges of K_{2c+1} is a counterexample.

    Reply
    • Gil Kalai says:
      February 1, 2016 at 4:28 am

      This, and the reference to the isolation lemma, looks like a great idea.

      Reply
    • domotorp says:
      February 2, 2016 at 1:23 am

      I’ve just realized that we had no lower bound for g – a simple example showing g(k,3)\ge 2^k is the root-to-leaf paths of a complete binary tree. But I don’t know whether g(a,3)g(b,3)\le g(ab,3) holds or not. I also wonder if the homological approach can prove anything about g…

      Reply
      • Anurag Bishnoi says:
        February 2, 2016 at 2:38 am

        Since g(2, 3) = 5 (pentagon), can we at least prove that g(4, 3) \geq 25?

      • Ferdinand Ihringer says:
        February 2, 2016 at 3:17 am

        As Anurag Bishnoi pointed out, the largest example for g(2, 3) is a pentagon. So in this case 25 = g(2, 3)^2 \leq g(4, 3). As the construction for f implies f(a, r, r, n)f(b, r, r, n') \leq f(a+b, r, r, n+n'), it is natural to limit the first attempt to 4-sets of \{1, \ldots, 10\}. I did an incomplete search with my stupid generic program and it only came up with an example of size 11.

        Now a complete argument for 10 = g(1, 3)g(2, 3) \leq g(3, 3) should be more feasible. The following is, I think, a nice example for g(3, 3), which just merges two pentagons. It uses the elements of \{ 0, \ldots, 9 \}. I write 012 for \{ 0, 1, 2\}.

        012
        234
        456
        678
        890
        134
        356
        578
        790
        912

        Maybe this construction (if it is correct, please double check) could be generalized to get at least some recursive bound. My incomplete computer search suggests that 10 is the maximum here.

      • domotorp says:
        February 2, 2016 at 10:55 am

        Yes, I meant g(a)g(b)\le g(a+b) (where I dropped the ,3 to keep things simple), thx. To get some recursion, I can prove g(k+1)\ge 2g(k). For this, take two disjoint copies of the family for g(k) and add two more elements, one contained in all members of one family, the other in all members of the other family. This also gives g(3)\ge 10.

        I find it quite funny that we came back to almost the same problem what gowers proposed at the beginning (https://gilkalai.wordpress.com/2015/11/03/polymath10-the-erdos-rado-delta-system-conjecture/#comment-22240), except that there everyone thought that there should be a trick to keep a large fraction of the family such that any two have the same intersection size, while here we realized that to get even 3 such sets is hard…

      • Gil Kalai says:
        February 2, 2016 at 9:34 pm

        This is very interesting! I suppose looking back and Tim’s comments from this new perspective can be useful. As for the homological and homological/combinatorial ideas, we want to find in cycles of various sorts sunflowers. I dont see how this getting easier when you relax it to sets with pairwise intersection having the same size but e can try to explore it. Also the Erdos-Ko-Rado related questions are of interest. For example we can ask what will guarantee having three sets with 1) empty intersection; 2) all pairwise intersections have the same size. Is the answer {{n} \choose {k}}-{{n-2} \choose {k}}? Is a (2,1)-cycle guarantees such a structure (in the non balanced case)? Also the connection to R_3(k) and R_r(k) are very interesting. (Those are known to be closely related with Shannon capacity but I dont recall seeing the connection with the sunflower question; should have another look in the papers I linked by Alon Shpilka Umens Cohn and others…

      • domotorp says:
        February 2, 2016 at 11:59 pm

        I’ve also just thought of Shannon entropy, more specifically, of the following question. What is the largest number of vectors such that the set of their pairwise angles has size k (so any two vectors have one of the angles \alpha_1,\ldots,\alpha_k), but no three vectors have pairwise the same angle?

        About the EKR-type question – I think that it is better to simply select an intersecting system of size {n-1\choose k-1}, as {n-2\choose k}>{n-1\choose k-1}={n\choose k}-{n-1\choose k-1}. Or did I misunderstand your question?

      • Gil Kalai says:
        February 3, 2016 at 12:45 am

        Selecting all sets which contains ‘1’ or ‘2’ still avoid a triple satisfying (1) and (2) and the (off hand) question is this best possible.

        As for Shannon capacity it is known that the question if R_k(3)^{1/k} is bounded from above is equivalent to the question if the Shannon capacity of graphs with independent number 2 is bounded from above. (And you can replace 3 and 2 by r and r-1.)

      • domotorp says:
        February 3, 2016 at 1:13 am

        EKR: Oh, I see, I made a silly calculation mistake.

        The Shannon capacity connection sounds very interesting.

        I want to mention that there is a simple, direct proof for g(k)\le (k+1)!.
        For this, introduce g(k;S) to be the size of the biggest k-uniform family without 3 sets with pairwise same intersection (should we abbreviate this as 3-\Psi?), such that the intersection size of any two sets is in S. Thus, for example, g(k,\{i\}\le 2 if S is a singleton and g(k,\{i,j\})\le 5 is also easy to prove. In general, we have g(k;S)\le 1+\sum_{s\in S} g(k;S\setminus\{s\})\le 1+|S||S|!\le (|S|+1)!, as we can consider the intersection sizes of the whole family with one fixed set, and put them in groups with respect to their intersection sizes.

      • Gil Kalai says:
        February 3, 2016 at 5:26 am

        Actually, it is my mistake since the example of sets containing ‘1’ or ‘2’ does have a triple of sets so that there is no element common to all and every pair has the same intersecting size.

  29. Pingback: Polymath10-post 4: Back to the drawing board? | Combinatorics and more

  30. Ferdinand Ihringer says:
    February 3, 2016 at 2:12 pm

    This might be a very stupid question, but all the sets have ‘1’ and ‘2’ in common, don’t they? If we ignore ‘1’ and ‘2’, then I understand the statement.

    If all sets in Y have pairwise the same intersection size, then |Y| \leq n. An easy proof is somewhere in the Babai-Frankl-book. We want to do the opposite thing, but I wanted to mention this classical result anyway.

    Maybe thinking about families Z of k-sets such that for all x, y \in Z we find many z \in Z with |x \cap y| = |x \cap z| = |y \cap z| might be helpful. Each non-trivial example for Z should give some bound on g(k). Trivial examples are the empty set and the set of all k-sets. If k divides n, then taking a partition of k-sets shows an upper bound of \binom{n-1}{k-1}. This gives, by the way, an easy proof for the most basic EKR theorem for the case k | n. I tried this some time for our original function f(k, r, m, n) (with the condition x \cap y = x \cap z = y \cap z) and there this approach did not seem helpful, but in this new setting … Who knows? Maybe the same problem occur, which I had for the original problem, but at least the conditions on Z are now weaker.

    Reply
  31. Gil Kalai says:
    February 4, 2016 at 2:22 am

    I should mention that r sets with equal pairwise intersecting size are called weak delta system. See e.g. http://www.math.ucsd.edu/~erdosproblems/erdos/newproblems/WeakDeltaSystems.html . Somehow a topological method looks less applicable. I am not sure what happen when you exclude three sets with empty intersection and equal pairwise intersection. If you exclude three sets with empty intersection and non empty pairwise intersection then this is a known extension of EKR going back to Chvatal.

    Reply

  32. Pingback: Polymath10 conclusion | Combinatorics and more

Leave a reply to domotorp Cancel reply