3 ms·

This could really use some examples. So the main gist is: "a collection of sets whose pairwise intersection is constant." So 100 sets that all have different

This could really use some examples. So the main gist is: "a collection of sets whose pairwise intersection is constant." So 100 sets that all have different elements would be a sunflower since their intersection is constant (empty)? And 100 sets that all contain some unique elements and some shared across all would be a sunflower, but as soon as some sets share an element that a third doesn't, then not? And two sets would _always_ be a sunflower? Or is the meaning of "constant pairwise intersection" something else?

bobbylarrybobby 3y ago
The formal definition section is good: Suppose W is a set system over U, that is, a collection of subsets of a set U. The collection W is a sunflower (or Δ-system) if there is a subset S of U such that for each distinct A and B in W, we have A ∩ B = S. In other words, a set system or collection of sets W is a sunflower if the pairwise intersection of each set in W is identical. Note that this intersection, S, may be empty; a collection of pairwise disjoint subsets is also a sunflower. Similarly, a collection of sets each containing the same elements is also trivially a sunflower.
chompychop 3y ago
The formal definition in the link makes this precise. Yes, 100 sets which are pairwise disjoint (which makes any pairwise intersection empty) would make a sunflower. Your second example is not a sunflower, because the definition requires that if you take the intersection of any two sets from those 100, the resulting set should be the same. So if you pairwise take those sets with unique elements, you get the empty set as intersection, but if you pairwise take two sets with shared elements, you get a set of the shared elements as intersection. The pairwise intersection should always be the same for it to be a sunflower. And yes, a collection of two sets would always be a sunflower.
- holden_nelson 3y ago
  I read the second example as: every set contains some elements that are totally unique to that set, and also some elements that are common to all of the sets, and nothing else. So I think it is a sunflower - any pairwise intersection just has the shared elements. e.g 100 sets of integers, of size 3. Each set contains a unique number from 1-100, and every set also contains 1000 and 10000. Any pairwise intersection is {1000, 10000}.
crdrost 3y ago
No you've got it, all of those are correct. Just means that for any A,B and C,D in the space A ∩ B = C ∩ D. And we generally don't care about the size of the intersection or anything like that, we just care about how many sets there are—100 in your case. Normal mathematicians don't usually do this but if you like combinatorics it can help to specialize to remove irrelevant details: imagine a set P, where each element of P is a set of k integers. An s-sunflower consists of s lists in P such that if any integer appears on 2 or more lists in the sunflower then it appears in all of them. The combinatorics question is then, for a given k and s how large does |P| have to be before you cannot help but have an s-sunflower in there. So if k = 1 then P is a set of distinct integers, if you want a sunflower of size s that is guaranteed when |P| = s. If k = 2 then P is a set of pairs of integers, if you want a sunflower of size s then thinking adversarially I can construct s-1 sets that all share the number 1 plus a bunch that don't. So (1, -1), (1, -2), ... (1, 1 – s). Then I can construct s – 1 sets that all share the number 2, maybe it helps if I overlap what I already have, (2, -1) ... (2, 1 – s). I can get as far as (s – 1)² in this construction before I have to add an element that creates a sunflower, if it’s say (s, -1) continuing the pattern then {(1, -1), (2, -1), ... (s, -1)} is a sunflower of size s with kernel {-1}, but if I try to get clever with (s, 0) then {(1, -1), (2, -2), ... (s – 1, 1 – s), (s, 0)} is a sunflower with kernel {}. But off the top of my head I'm not sure if this construction is optimally adversarial. Notice that for k = 2 I got ~ (s – 1)², similar constructions can set a lower bound that with k = 3 you can need at least (s – 1)³, the biggest question is whether this is upper-bounded by f(s)^k for some function f so that the asymptotic growth in k is purely exponential. Right now the best known upper bound is superexponential, something like [s log(k)]^k.
kazinator 3y ago
I edited the page to get rid of the "constant" based talking point.

bobbylarrybobby 3y ago

The formal definition section is good: Suppose W is a set system over U, that is, a collection of subsets of a set U. The collection W is a sunflower (or Δ-system) if there is a subset S of U such that for each distinct A and B in W, we have A ∩ B = S. In other words, a set system or collection of sets W is a sunflower if the pairwise intersection of each set in W is identical. Note that this intersection, S, may be empty; a collection of pairwise disjoint subsets is also a sunflower. Similarly, a collection of sets each containing the same elements is also trivially a sunflower.

chompychop 3y ago

The formal definition in the link makes this precise. Yes, 100 sets which are pairwise disjoint (which makes any pairwise intersection empty) would make a sunflower. Your second example is not a sunflower, because the definition requires that if you take the intersection of any two sets from those 100, the resulting set should be the same. So if you pairwise take those sets with unique elements, you get the empty set as intersection, but if you pairwise take two sets with shared elements, you get a set of the shared elements as intersection. The pairwise intersection should always be the same for it to be a sunflower. And yes, a collection of two sets would always be a sunflower.

holden_nelson 3y ago
I read the second example as: every set contains some elements that are totally unique to that set, and also some elements that are common to all of the sets, and nothing else. So I think it is a sunflower - any pairwise intersection just has the shared elements. e.g 100 sets of integers, of size 3. Each set contains a unique number from 1-100, and every set also contains 1000 and 10000. Any pairwise intersection is {1000, 10000}.

crdrost 3y ago

No you've got it, all of those are correct. Just means that for any A,B and C,D in the space A ∩ B = C ∩ D. And we generally don't care about the size of the intersection or anything like that, we just care about how many sets there are—100 in your case. Normal mathematicians don't usually do this but if you like combinatorics it can help to specialize to remove irrelevant details: imagine a set P, where each element of P is a set of k integers. An s-sunflower consists of s lists in P such that if any integer appears on 2 or more lists in the sunflower then it appears in all of them. The combinatorics question is then, for a given k and s how large does |P| have to be before you cannot help but have an s-sunflower in there. So if k = 1 then P is a set of distinct integers, if you want a sunflower of size s that is guaranteed when |P| = s. If k = 2 then P is a set of pairs of integers, if you want a sunflower of size s then thinking adversarially I can construct s-1 sets that all share the number 1 plus a bunch that don't. So (1, -1), (1, -2), ... (1, 1 – s). Then I can construct s – 1 sets that all share the number 2, maybe it helps if I overlap what I already have, (2, -1) ... (2, 1 – s). I can get as far as (s – 1)² in this construction before I have to add an element that creates a sunflower, if it’s say (s, -1) continuing the pattern then {(1, -1), (2, -1), ... (s, -1)} is a sunflower of size s with kernel {-1}, but if I try to get clever with (s, 0) then {(1, -1), (2, -2), ... (s – 1, 1 – s), (s, 0)} is a sunflower with kernel {}. But off the top of my head I'm not sure if this construction is optimally adversarial. Notice that for k = 2 I got ~ (s – 1)², similar constructions can set a lower bound that with k = 3 you can need at least (s – 1)³, the biggest question is whether this is upper-bounded by f(s)^k for some function f so that the asymptotic growth in k is purely exponential. Right now the best known upper bound is superexponential, something like [s log(k)]^k.

kazinator 3y ago

I edited the page to get rid of the "constant" based talking point.