|
%I #36 Jan 05 2024 12:29:20
%S 1,2,1,3,2,1,4,7,2,1,5,11,21,2,1,6,21
%N Square array of sunflower numbers Sun(m,n) = minimal number of distinct sets of cardinality <= m such that there is a sunflower with at least n sets among them, read by falling antidiagonals; m, n >= 1.
%C A sunflower S is a collection of sets such that all pairwise intersections of distinct A, B in S are equal. The intersection of all the sets is called the core or kernel of S.
%C Some authors (e.g., Wikipedia) use "more than" instead of "at least" in the definition, which corresponds to an index n decreased by 1. We use the same conventions Tao (but following OEIS standards we use m,n instead of k,r). Also, some authors (e.g., Abbott et al. and the Polymath wiki page) use f(k,r) = Sun(k,r) - 1 which is not the minimal number of required sets, but such that any collection of *more than* f(k,r) sets has the given property.
%C Bell et al. improve Rao's bound [as reproved by Tao] from Sun(m,n) <= O(n log(mn))^m for m, n >= 2 to the slightly cleaner bound Sun(m,n) <= O(n log m)^m for m, n >= 2. [Pers. comm. from L. Warnke.] - _M. F. Hasler_, May 02 2021
%H H. L. Abbott, D. Hanson, and N. Sauer, <a href="https://doi.org/10.1016/0097-3165(72)90103-3">Intersection Theorems for Systems of Sets</a>. J. Comb. Theory A 12 (1972) pp. 381-389. doi:10.1016/0097-3165(72)90103-3
%H T. Bell, C. Chueluecha and L. Warnke, <a href="http://doi.org/10.1016/j.disc.2021.112367">Note on Sunflowers</a>, Discrete Mathematics 344 (2021), 112340; DOI: 10.1016/j.disc.2021.112367; preprint arXiv:2009.09327.
%H P. Erdös and R. Rado, <a href="https://doi.org/10.1112/jlms/s1-35.1.85">Intersection Theorems for Systems of Sets</a>, Journal of the London Mathematical Society, s1-35 (1960) pp. 85-90. doi:10.1112/jlms/s1-35.1.85
%H Polymath wiki, <a href="https://web.archive.org/web/20220705073934/https://asone.ai/polymath/index.php?title=The_Erdos-Rado_sunflower_lemma">The Erdos-Rado sunflower lemma</a>, as of Feb 5, 2016.
%H Anup Rao, <a href="https://arxiv.org/abs/1909.04774">Coding for Sunflowers</a>, arXiv:1909.04774 [math.CO], Sept. 2019.
%H Terence Tao, <a href="https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy">The sunflower lemma via Shannon entropy</a>, personal blog "What's new", Jul 20 2020.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sunflower_(mathematics)">Sunflower (mathematics)</a>.
%F Sun(m,n) = n for n <= 2 and all m;
%F Sun(1,n) = n for all n: see Examples for explanation.
%F Sun(2,n) = n(n-1)+1 if n is odd, (n-1)^2-n/2 if n is even. (Abbott-Hanson-Sauer)
%F (n-1)^m <= Sun(m,n) <= (n-1)^m*m! + 1. (Erdös & Rado)
%F Sun(m,n) <= O(n log(mn))^m for m, n >= 2. (Rao)
%F Sun(m,n) <= O(n log m)^m for m, n >= 2. (Bell-Chueluecha-Warnke)
%F Sunflower conjecture: Sun(m,n) <= (n*O(1))^m.
%e The table starts:
%e m \n=1 2 3 4 5 6 7 ...
%e ---+-------------------------------
%e 1 | 1 2 3 4 5 6 7 ...
%e 2 | 1 2 7 11 21 28 43 ...
%e 3 | 1 2 21 ...
%e 4 | 1 2 ...
%e 5 | 1 2 ...
%e ...
%e Row m=1 has Sun(1,n) = n for all n, because any collection of n sets having at most 1 element (which may or may not include the empty set) makes up an n-petal sunflower S with an empty kernel.
%e Columns n=1 and n=2 have Sun(m,n) = n for any m, because any single set A makes up a 1-petal sunflower S = {A}, and any two distinct sets A, B make up a 2-petal sunflower S = {A, B} with kernel {A intersect B}, necessarily not equal to both A and B since they are distinct; then so the petals with at least one of them nonempty.
%Y Cf. A236397, A266696.
%K nonn,tabl,hard,more,nice
%O 1,2
%A _M. F. Hasler_, Jul 27 2020
| 