21
$\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 http://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)$.

UPDATEs. Best currently known lower bound for $C_3$ is $\sqrt{10}\approx 3.16$, which can be found in Abbott-Hanson-Sauer: http://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.

$\endgroup$
  • 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 Apr 18 '14 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 Apr 18 '14 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 Apr 20 '14 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 Apr 20 '14 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 Apr 20 '14 at 23:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.