# Maximal number of subsets in $\{1,\dots,n\}$ such that neither is contained in a union of two others

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?

• You use $k$ twice for different things, maximal $N$ would be better. :) Aug 14 '15 at 9:40
• 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\}$. Aug 14 '15 at 10:00
• 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. Aug 14 '15 at 10:18
• 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! Aug 14 '15 at 11:26

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