4 ms·

Sunflower (Mathematics)

62 points by akkartik 3y ago

suoinguon 3y ago
[dead]
- gowld 3y ago
  This is a ChatGPT spam site.
bongripper 3y ago
Hate having had to learn all that shit in CS class as a student. Wish i had picked another major.
- yard2010 3y ago
  Lol I felt the same while being forced to study this but now I'm trying to learn it in my free time. Go figure
  - badosu 3y ago
    Math is fun when you have time to figure out on your own, and set challenges for yourself. It's not so fun when you have set deadlines to figure out some key concept it's not clicking yet and go through a standardized test and big exercise lists. Had the same experience as a math undergrad and after getting through college.
- bongripper 3y ago
  I didn't mean to sound so negative, it's still interesting, it was just a chore as a teenager/early twenties college student.
  - gowld 3y ago
    That has nothing to do with the OP, though.
- deleted 3y ago
  [deleted]
  - jusgu 3y ago
    [flagged]
finite_depth 3y ago
The existence of sunflowers in any sufficiently large set is an example of a fascinating field of combinatorics called Ramsey theory. The idea is that for a very wide range of structures, sufficiently large objects always necessarily contain substructures of arbitrary size because there's no way to avoid it as the amount of space inside the object grows. The classic example is the "Theorem on Friends and Strangers", which states that in any group of six or more people, there is always some subset of three people who are either pairwise friends or pairwise strangers (or, in graph theoretic terms, three vertices that are either all pairwise connected by an edge or pairwise not connected by an edge). This generalizes to larger subsets: in any group of 18 or more people, there's always some subset of four people who are pairwise friends or strangers, and in any group of 49 or more, there's always some subset of five (49 may not be optimal here; it's known to be between 43 and 49). The known bounds are quite weak: the number of people required to guarantee a mutual-friends-or-strangers subset of n people is known only to be omega(2^(n/2)) and little-o(2^2n), with no improvements on those bounds made despite nearly a century of work.
Aardwolf 3y ago
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}.
kazinator 3y ago
I just fixed the somewhat confusing wording in the introduction which talked about a constant intersection. I believe the right concept is that the intersection is common. If a set of sets have pairwise intersections that are different, those are still constants, if the sets being considered are constants! E.g. { 1, 2, 3, 4, 5 } is a constant set, so is the { 2 } which is an intersection of { 1, 2 } and { 2, 3 }, and so is { 4 }, which is an intersection of { 3, 4 } and { 1, 4 }. (I get that the idea is that the intersection constant from pair to pair: i.e. if we enumerate the pairs as an index i from 0 to n-1, then the intersection doesn't vary with i.) Under the formal definition, I replaced the explanatory ("in other words") text with a different idea, instead of reiterating what's already in the introduction. Every element in U is either common to all the subsets in W, or else is found in at most one W subset. No elements are shared by some sets in W, but not others.

62 points by akkartik 3y ago

suoinguon 3y ago

[dead]

gowld 3y ago
This is a ChatGPT spam site.

bongripper 3y ago

Hate having had to learn all that shit in CS class as a student. Wish i had picked another major.

yard2010 3y ago
Lol I felt the same while being forced to study this but now I'm trying to learn it in my free time. Go figure
- badosu 3y ago
  Math is fun when you have time to figure out on your own, and set challenges for yourself. It's not so fun when you have set deadlines to figure out some key concept it's not clicking yet and go through a standardized test and big exercise lists. Had the same experience as a math undergrad and after getting through college.
bongripper 3y ago
I didn't mean to sound so negative, it's still interesting, it was just a chore as a teenager/early twenties college student.
- gowld 3y ago
  That has nothing to do with the OP, though.
deleted 3y ago
[deleted]
- jusgu 3y ago
  [flagged]

finite_depth 3y ago

The existence of sunflowers in any sufficiently large set is an example of a fascinating field of combinatorics called Ramsey theory. The idea is that for a very wide range of structures, sufficiently large objects always necessarily contain substructures of arbitrary size because there's no way to avoid it as the amount of space inside the object grows. The classic example is the "Theorem on Friends and Strangers", which states that in any group of six or more people, there is always some subset of three people who are either pairwise friends or pairwise strangers (or, in graph theoretic terms, three vertices that are either all pairwise connected by an edge or pairwise not connected by an edge). This generalizes to larger subsets: in any group of 18 or more people, there's always some subset of four people who are pairwise friends or strangers, and in any group of 49 or more, there's always some subset of five (49 may not be optimal here; it's known to be between 43 and 49). The known bounds are quite weak: the number of people required to guarantee a mutual-friends-or-strangers subset of n people is known only to be omega(2^(n/2)) and little-o(2^2n), with no improvements on those bounds made despite nearly a century of work.

Aardwolf 3y ago

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

kazinator 3y ago

I just fixed the somewhat confusing wording in the introduction which talked about a constant intersection. I believe the right concept is that the intersection is common. If a set of sets have pairwise intersections that are different, those are still constants, if the sets being considered are constants! E.g. { 1, 2, 3, 4, 5 } is a constant set, so is the { 2 } which is an intersection of { 1, 2 } and { 2, 3 }, and so is { 4 }, which is an intersection of { 3, 4 } and { 1, 4 }. (I get that the idea is that the intersection constant from pair to pair: i.e. if we enumerate the pairs as an index i from 0 to n-1, then the intersection doesn't vary with i.) Under the formal definition, I replaced the explanatory ("in other words") text with a different idea, instead of reiterating what's already in the introduction. Every element in U is either common to all the subsets in W, or else is found in at most one W subset. No elements are shared by some sets in W, but not others.