A266696 -id:A266696 - cp's OEIS frontend

A332077 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.

1, 2, 1, 3, 2, 1, 4, 7, 2, 1, 5, 11, 21, 2, 1, 6, 21

Offset: 1

M. F. Hasler, Jul 27 2020

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.
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.
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

			The table starts:
   m \n=1   2   3   4   5   6   7  ...
  ---+-------------------------------
   1 |  1   2   3   4   5   6   7  ...
   2 |  1   2   7  11  21  28  43  ...
   3 |  1   2  21  ...
   4 |  1   2  ...
   5 |  1   2  ...
    ...
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.
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.

H. L. Abbott, D. Hanson, and N. Sauer, Intersection Theorems for Systems of Sets. J. Comb. Theory A 12 (1972) pp. 381-389. doi:10.1016/0097-3165(72)90103-3
T. Bell, C. Chueluecha and L. Warnke, Note on Sunflowers, Discrete Mathematics 344 (2021), 112340; DOI: 10.1016/j.disc.2021.112367; preprint arXiv:2009.09327.
P. Erdös and R. Rado, Intersection Theorems for Systems of Sets, Journal of the London Mathematical Society, s1-35 (1960) pp. 85-90. doi:10.1112/jlms/s1-35.1.85
Polymath wiki, The Erdos-Rado sunflower lemma, as of Feb 5, 2016.
Anup Rao, Coding for Sunflowers, arXiv:1909.04774 [math.CO], Sept. 2019.
Terence Tao, The sunflower lemma via Shannon entropy, personal blog "What's new", Jul 20 2020.
Wikipedia, Sunflower (mathematics).
Kyle Wood, Example for Sun(3,3)=21, a family of 20 sets with no 3-flowers.

Cf. A236397, A266696.

Sun(m,n) = n for n <= 2 and all m;
Sun(1,n) = n for all n: see Examples for explanation.
Sun(2,n) = n(n-1)+1 if n is odd, (n-1)^2-n/2 if n is even. (Abbott-Hanson-Sauer)
(n-1)^m <= Sun(m,n) <= (n-1)^m*m! + 1. (Erdös & Rado)
Sun(m,n) <= O(n log(mn))^m for m, n >= 2. (Rao)
Sun(m,n) <= O(n log m)^m for m, n >= 2. (Bell-Chueluecha-Warnke)
Sunflower conjecture: Sun(m,n) <= (n*O(1))^m.

A335322 Triangle read by rows: T(n, k) = binomial(n, floor((n+k+1)/2)) with k <= n.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 4, 4, 1, 1, 10, 5, 5, 1, 1, 15, 15, 6, 6, 1, 1, 35, 21, 21, 7, 7, 1, 1, 56, 56, 28, 28, 8, 8, 1, 1, 126, 84, 84, 36, 36, 9, 9, 1, 1, 210, 210, 120, 120, 45, 45, 10, 10, 1, 1, 462, 330, 330, 165, 165, 55, 55, 11, 11, 1, 1, 792, 792, 495, 495, 220, 220, 66, 66, 12, 12, 1, 1

Offset: 1

Stefano Spezia, May 31 2020

T(n, k) is a tight upper bound of the cardinality of an intersecting Sperner family or antichain of the set {1, 2,..., n}, where every collection of pairwise independent subsets is characterized by an intersection of cardinality at least k (see Theorem 1.3 in Wong and Tay).

Equals A061554 with the first row of the array (resp. the first column of the triangle) removed. - Georg Fischer, Jul 26 2023

			The triangle T(n, k) begins
n\k|  1   2   3   4   5   6   7   8
---+-------------------------------
1  |  1
2  |  1   1
3  |  3   1   1
4  |  4   4   1   1
5  | 10   5   5   1   1
6  | 15  15   6   6   1   1
7  | 35  21  21   7   7   1   1
8  | 56  56  28  28   8   8   1   1
...

Eric Charles Milner, A Combinatorial Theorem On Systems of Sets, Journal of the London Mathematical Society, 43, (1968), 204-206.
W. H. W. Wong and E. G. Tay, On Cross-intersecting Sperner Families, arXiv:2001.01910 [math.CO], 2020.
Index entries for sequences related to antichains.

Cf. A000372, A001405, A004526, A007318, A007695, A061554, A266696, A325982, A325983.

Cf. A037951 (k=3), A037952 (k=1), A037953 (k=5), A037954 (k=7), A037955 (k=2), A037956 (k=4), A037957 (k=6), A037958 (k=8), A045621 (row sums).

T[n_,k_]:=Binomial[n,Floor[(n+k+1)/2]]; Table[T[n,k],{n,12},{k,n}]//Flatten

T(n, k) = binomial(n, (n+k+1)\2);
vector(10, n, vector(n, k, T(n, k))) \\ Michel Marcus, Jun 01 2020

T(n, k) = A007318(n, A004526(n+k+1)) with k <= n.

cp's OEIS Frontend

A332077 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula