{
  "id": "1408.3671",
  "version": "v2",
  "published": "2014-08-15T22:42:21.000Z",
  "updated": "2014-08-19T13:54:07.000Z",
  "title": "Asymptotic Improvement of the Sunflower Bound",
  "authors": [
    "Junichiro Fukuyama"
  ],
  "comment": "13 pages, no figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A sunflower with a core $Y$ is a family ${\\cal B}$ of sets such that $U \\cap U' = Y$ for each two distinct elements $U$ and $U'$ in ${\\cal B}$. The well-known sunflower lemma states that a given family ${\\cal F}$ of sets, each of cardinality at most $s$, includes a sunflower of cardinality $k$ if $|{\\cal F}|> (k-1)^s s!$. Since Erdos and Rado proved it in 1960, it has not been known for more than half a century whether the sunflower bound $(k-1)^s s!$ can be improved asymptotically for any $k$ and $s$. It is conjectured that it can be reduced to $c_k^s$ for some real number $c_k>0$ depending only on $k$, which is called the sunflower conjecture. This paper shows that the general sunflower bound can be indeed reduced by an exponential factor: We prove that ${\\cal F}$ includes a sunflower of cardinality $k$ if \\[ |{\\cal F|} \\ge \\left( \\frac{8}{7} \\right)^2 \\left[ k \\cdot \\min \\left( \\frac{7}{8}, \\frac{c}{\\log \\min(k, s)} \\right) \\right]^s s!, \\] for a constant $c>0$. For instance, whenever $k \\ge s^\\epsilon$ for a given constant $\\epsilon \\in (0,1)$, the sunflower bound is reduced from $(k-1)^s s!$ to $(k-1)^s s! \\cdot O (1 / \\log s )^s$, achieving the reduction ratio of $O ( 1 / \\log s )^s$. Also any ${\\cal F}$ of cardinality at least $(8/7)^2 (7k/8)^s s!$ includes a sunflower of cardinality $k$. Our result demonstrates that the sunflower bound can be improved by a factor of less than a small constant to the power $s$, giving hope for further update.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-08-19T13:54:07.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "asymptotic improvement",
      "cardinality",
      "well-known sunflower lemma states",
      "general sunflower bound",
      "distinct elements"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1408.3671F"
    }
  }
}