12
$\begingroup$

Let the set $\mathcal{F}$ consist of subsets of $[n]$. Suppose that for any incomparable $A$ and $B$ in $\mathcal{F}$, we have $A \cap B \notin \mathcal{F}$. What is the largest possible size of $\mathcal{F}$?

$\endgroup$
  • 3
    $\begingroup$ Have you tried finding it for small values of $n$, and then looking it up in the Online Encyclopedia of Integer Sequences? $\endgroup$ – Gerry Myerson Aug 26 '15 at 3:31
  • $\begingroup$ I went ahead a wrote some code. I can only get it to work for n up to 5. Starting with n = 0, the answer is 1,2,3,5,9,16. There are 38 sequences in OEIS that start that way. Unfortunately, I don't know where to start with those. $\endgroup$ – Josh Brown Kramer Aug 26 '15 at 17:34
  • 2
    $\begingroup$ I'll note that in every case checked so far, a maximum size family has consisted of the set of size n, the sets of size n-1, and the sets of size n - 3. Notice that this will always work, and you can keep going ... sets of size n - 3 have an interection of size at least n - 6. So you can add the set of size n - 7, then n - 15, n - 31 and so on. A better strategy might be to start with the middle sized sets and work up (although this doesn't yield the max in the n = 4 case). $\endgroup$ – Josh Brown Kramer Aug 26 '15 at 17:48
  • 1
    $\begingroup$ Josh, if you try to construct an optimal system for $n=8$ in this manner (taking some complete layers of the cube), you will come up with the system of the 8-set, all 6-sets, and all 3-sets (all other combinations lose to this one). BUT THEN you may also add ONE 7-set without troubles! So an optimal example becomes more complicated, no matter whether it is the resulting one or not. $\endgroup$ – Ilya Bogdanov Aug 28 '15 at 6:47
4
$\begingroup$

It was proved by Kleitman that $|\mathcal F|\le {n\choose n/2}+2^n/n$, see http://www.sciencedirect.com/science/article/pii/0097316576900376.

$\endgroup$
  • 1
    $\begingroup$ This obviously doesn't answer the question exactly, but looking at the research that cites this paper and the quality of the people who have thought about it, it seems unlikely that we're going to get a much better answer than this. I will note that there are some recent improvements to lower bounds on $\mathcal{F}$. For example, researchgate.net/publication/… $\endgroup$ – Josh Brown Kramer Sep 5 '15 at 14:15
3
$\begingroup$

If you restrict yourself to incomparable subsets, you can take, e.g., all $t+1$-subsets of for $n=2t+1$. All intersections are now of size at most $t$ and don't belong to the family. For even $n=2t$ you'd need to take all $t+1$-subsets as well, but this wouldn't be as large as a fraction of the total family, but asymptotically essentially the same in relative size, compared to $2^n.$

Thus, asymptotically, if $${\cal F}=\{A \subset [n]: |A|=\lfloor{n/2}\rfloor+1\},$$ this will give $$|{\cal F}|=\binom{n}{\lfloor n/2 \rfloor+1}= O(2^{n}/\sqrt{n}).$$ If this family is enlarged by adding any other set which is smaller, this would destroy the intersection avoidance property since all smaller sets already occur as intersections of incomparable sets.

Edit: As pointed out in the comments by Seva, it is in fact fine a set of size larger than $t+1$ and preserve the required property, e.g., add $[n]$. Can we add more than one such set? If we add two distinct $t+1+a$ and $t+1+b$ sets, where $a,b\geq 1,$ as long as the intersection of these two sets is of size $\leq t$ we're fine. So the only problem would occur if these two sets intersected on a $t+1$ set. So we're not completely free to add all larger sets to the ensemble which would result in a total of $O(2^n)$ sets.

Thus it seems we can greedily pack larger sets, ensuring any two pairs intersect in at most $t$ points. For example we can use a sunflower set whereby a $t-$set intersection is extended to distinct $t+2$ sets by adjoining 2 points to obtain each new set, so this would add $\lfloor (t+1)/2 \rfloor$ sets to the family.

In any case, clearly the largest family size obtainable this way would be $O(2^n).$

$\endgroup$
  • $\begingroup$ The concluding part of your argument is a little vague and in fact, it seems that you can add an arbitrarily chosen set of size larger than $t+1$ to the family of all $(t+1)$-sets while keeping the property in question. (Think, for instance, of the set $[n]$ itself.) $\endgroup$ – Seva Aug 26 '15 at 9:50
  • $\begingroup$ @kodlu, If I understand correctly, you really do mean $O(2^n)$, rather than $\Theta(2^n)$, since the specific sunflower construction you're suggesting seems to be $o(2^n)$. Am I right, or are you actually saying that clearly there is $c$ such that $|\mathcal{F}| > c2^n$? $\endgroup$ – Josh Brown Kramer Aug 27 '15 at 1:39
  • $\begingroup$ @JoshBrownKramer. Yes, you are correct. $\endgroup$ – kodlu Aug 27 '15 at 1:58
  • 1
    $\begingroup$ I don't think the $O(2^n)$ makes much sense here. $\endgroup$ – domotorp Sep 2 '15 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.