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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.