4 ms·
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 i
by 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.