26
$\begingroup$

A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z $ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdos and Rado says that there is a constant $C_t$ such that in any $k$-uniform family of size at least $C_t^k$ there is a $t$-sunflower. This is still wide open even for $t=3$, for more see https://en.wikipedia.org/wiki/Sunflower_(mathematics).

My question is, what is the best lower bound for $C_3$? So what is the largest known example of a $k$-uniform family that does not have a $3$-sunflower?

We can also study this as some function $f$ of $k$. I am even interested in small values, like up to $20$, if anyone can compute it. It is easy to see that $f$ is logsuperadditive. In case this is not a word, I mean $f(a+b)\ge f(a)f(b)$.

Denoting by $f'$ the version where the set family is required to be intersecting, $f'(ab)\ge f'(a)(f'(b))^a$; see Eric's answer for the proof. This recursion seems to give for $t=3$ the best currently known lower bound: $C_3\ge \sqrt{10}\approx 3.16$, which first appeared in Abbott-Hanson-Sauer: https://www.sciencedirect.com/science/article/pii/0097316572901033.

We also know $f(1)=2, f(2)=6, f(3)=20$, from some old papers, $f(4)$ might be still open.

Improve this question
$\endgroup$
17
  • 3
    $\begingroup$ One easy lower bound comes from taking one side from each of $a$ disjoint pentagons. This gives $5^a$ sets of size $2a$ with no sunflower of size $3$, so $C_3 \ge \sqrt{5}$. I recall that someone showed me a better construction a couple of decades ago involving the Petersen graph but I don't recall the details. $\endgroup$
    – Douglas Zare
    Commented Apr 18, 2014 at 10:04
  • 5
    $\begingroup$ @domotorp Don't laugh at me ... I finally understand (a bit) what you are asking :) Take a triangle with vertices $1,2,3$, and another triangle with vertices $4,5,6$. This gives you six edges total, with no sunflower of size $3$. So $C_3 \ge \sqrt{6} \approx 2.449 > \sqrt{5} \approx 2.236$. That is, my $2$-uniform family of size $6$ with no sunflower of size $3$ is $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, $\{4,5\}$, $\{4,6\}$, $\{5,6\}$. Thank you for your patience in explaining your question (did I get it right?) $\endgroup$
    – Mirko
    Commented Apr 18, 2014 at 18:05
  • 2
    $\begingroup$ Can you make the beginning clearer by saying something like "A well-known conjecture of Erdos and Rado says that there is a constant $C_t$ such that in any k-uniform family of size at least $C^k_ t$..." ? $\endgroup$
    – Wolfgang
    Commented Apr 20, 2014 at 16:53
  • 5
    $\begingroup$ For $k=3$, consider the quotient of the icosahedron by the antipodal map, the dual of the Petersen graph in the projective plane. Equivalently, in $\mathbb Z/5 \cup \lbrace \infty \rbrace$, take $\lbrace \lbrace i, i+1, \infty\rbrace \rbrace \cup \lbrace \lbrace i, i+1, i+3 \rbrace \rbrace$. This is $3$-free: there is no sunflower of size $3$. Every triple intersects every other. Two disjoint copies gives a $3$-free set of size $20$, which gives a lower bound $C_3 \ge \sqrt[3]{20} = 2.714$. I think this is the construction someone (maybe Robin Chapman?) showed me. $\endgroup$
    – Douglas Zare
    Commented Apr 20, 2014 at 23:33
  • 2
    $\begingroup$ If $F$ is a $k$-uniform family with $f(k)=|F|$ then there must be two disjoint sets $A,B\in F$ (else we could make $F$ bigger by adding a new $k$-set disjoint from all members of $F$). Then every $C\in F$ meets $A$ or $B$. Wolog $\cup F=(1,...,m)$ for some $m$, and $A=(1,...,k)$, $B=(k+1,...,2k)$. For every $i≤k$ at most $f(k−1)$ many members of $F$ contain $i$, and one of these is $A$. Hence $f(k)≤2(1+k(f(k−1)−1))$ (could possibly be improved), $f(2)≤2(1+2(f(1)−1))=2(1+2(2−1))=6$, so $f(2)=6$, and $f(3)≤2(1+3(6−1))=32$. Thus $20≤f(3)≤32$. Could we "build" $F$ starting from $A,B$ as above? $\endgroup$
    – Mirko
    Commented Apr 20, 2014 at 23:56

2 Answers 2

Reset to default
6
$\begingroup$

As mentioned in the update to the post, the best lower bound is $C_3\geq \sqrt{10}$ due to Abbott, Hanson, and Sauer. I wanted to briefly explain why it is a consequence of recursively using the construction in Douglas Zare's comment:

Douglas Zare: For $k=3$, consider the quotient of the icosahedron by the antipodal map, the dual of the Petersen graph in the projective plane. Equivalently, in $\mathbb{Z}/5\cup\{\infty\}$, take $\{\{i,i+1,\infty\}\}\cup\{\{i,i+1,i+3\}\}$. This is 3-free: there is no sunflower of size 3. Every triple intersects every other. Two disjoint copies gives a 3-free set of size 20, which gives a lower bound $C_3\geq \sqrt[3]{20}=2.714\dots $ I think this is the construction someone (maybe Robin Chapman?) showed me.

To summarize, this icosahedral construction yields a family of $10$ subsets of a universe of size $6$, of which no triple is a sunflower, and such that every pair intersects. This intersection property is critical, as it allows us to recursively utilize this construction inside of other sunflower-free families.

Suppose that I have some sunflower-free family $\mathcal{F}$ where each set has size $k$. Expand each element of the universe to a set of size $6$, and for each member of the family, replace each of it's elements with a member of the icosahedral family. Since each member of $\mathcal{F}$ contains $k$ elements, there are $10^k$ ways to do this, and so we obtain a family of size $10^k |\mathcal{F}|$ each containing $3k$ elements. This new family will be sunflower-free due to the intersection property described earlier. If I have three elements of $\mathcal{F}$, if they are all equal, none of $10^k$ choose $3$ triples obtained in this manner can contain a sunflower since the icosahedral family is sunflower-free. If they are not all equal, then there exists an element that is in precisely two of them. In that case, the intersective property of the icosahedral family guarantees that none of the resulting triples contain a sunflower.

Recursively applying this with the icosahedral set itself, for any $k$ we obtain a family of size $$10^{1+3+3^2+\cdots+3^{k-1}} = 10^{\frac{3^k-1}{2}}$$ where each member contains $3^k$ elements, and hence we obtain the lower bound $C_3\geq \sqrt{10}$.

I personally believe that this construction is optimal, and that $C_3 = \sqrt{10}$.

Improve this answer
$\endgroup$
-2
$\begingroup$

This is the same construction as the above comment. But with an attempt at more detail at each step for anyone who may need.

Let F be an arbitrary 3 sunflower free set. Expand each element of its universe to 6 elements and construct out of those 6 elements, the icosahedral family on those 6 elements. For each set in F, replace each element with any member of the icosahedral family corresponding to that element. There are 10 ways of doing this for each element and $10^k$ ways of doing this for each set. Perform this construction for each of the sets in F. Then taking the union of these constructed sets from across each the sets of F, we have a $|F|*10^k$ size set of sets which have $3k$ elements each which is 3 sunflower free.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Isn't this exactly the same as the construction Eric Naslund gives in his answer? $\endgroup$
    – Steven Stadnicki
    Commented Nov 6, 2022 at 23:35
  • 1
    $\begingroup$ Yes. Same construction. Bit more detail in explanation. Since I found it helpful. I assume someone else may as well. $\endgroup$
    – Z_22
    Commented Nov 7, 2022 at 2:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .