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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ You use $k$ twice for different things, maximal $N$ would be better. :) $\endgroup$
    – Wolfgang
    Commented Aug 14, 2015 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
    Commented Aug 14, 2015 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
    Commented Aug 14, 2015 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
    Commented Aug 14, 2015 at 11:26

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .