16
$\begingroup$

What are known estimates for maximal $M$ for which their exists subsets $A_1,\dots,A_M$ in $\{1,\dots,n\}$ such that there do not exist different indexes $i,j,k$ for which $A_i\subset A_j\cup A_k$?

It is not hard to prove some exponential bounds $c_1^n<M<c_2^n$ for some $1<c_1<c_2<2$, but maybe sharp exponent is known?

$\endgroup$
  • 2
    $\begingroup$ You use $k$ twice for different things, maximal $N$ would be better. :) $\endgroup$ – Wolfgang Aug 14 '15 at 9:40
  • 1
    $\begingroup$ How do you come up with your lower bound $c_1^n$? I cannot seem to find anything better than linear, e.g. $A_i=\{i\}$. $\endgroup$ – Wolfgang Aug 14 '15 at 10:00
  • 2
    $\begingroup$ Choose, say, subsets $A_1,\dots,A_M$ of size $n/4$ at random. The probability of any event $A_i\subset A_j\cup A_k$ is exponentially small in $n$, thus for small $c_1$ close to 1 with positive probability no event happens. This may be improved by optimization in size and by using Lovász Local Lemma. $\endgroup$ – Fedor Petrov Aug 14 '15 at 10:18
  • $\begingroup$ Oh I see now, e.g. $f(9)\ge12$, attained by taking the 9 sets 123,234,... (cyclically) plus the 3 sets 147,258,369. Interesting! $\endgroup$ – Wolfgang Aug 14 '15 at 11:26
6
$\begingroup$

To best of my knowledge, the only bounds on this problem in the literature are in the the old paper of Erdős, Frankl, and Füredi. See Theorem 2 there. If you look at the MathSciNet review of the said paper you will find papers that referenced this paper. Perhaps, some might be of use to you.

There is also a follow-up paper by the same authors on families not containing sets $A,B_1,\dotsc,B_r$ such that $A\subset B_1\cup\dotsb\cup B_r$.

$\endgroup$

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.