Intersection Safe Families

Question

I'm looking at a past homework solution and there is a part of it I don't understand. Specifically I'm talking about number 2 in this problem set:

Let $m=\lfloor(8/7)^{n/3}\rfloor$. Show that there exist distinct sets $A_1,A_2,\dots,A_m\subseteq[n]$ such that for all distinct $i,j,k\in[m]$ we have $A_i\cap A_j\nsubseteq A_k$.

Given $A_1, A_2, A_3,..., A_m$ which are subsets of $ [n] $. Can someone explain in detail why the probability of $A_i \cap A_j \subseteq A_k$ is equal to $(\frac7 8)^{n}$.

Answer 1

Suppose that $A_i\cap A_j\subseteq A_k$. Then for each $r\in[n]$ one of the following must be true:

1. $r\in A_i$ and $r\in A_j$ and $r\in A_k$.
2. $r\in A_i$ and $r\notin A_j$, in which case it doesn’t matter whether $r\in A_k$.
3. $r\notin A_i$ and $r\in A_j$, in which case it doesn’t matter whether $r\in A_k$.
4. $r\notin A_i$ and $\notin A_j$, in which case it doesn’t matter whether $r\in A_k$.

Since each $r\in[m]$ is in any given $A_s$ with probability $\frac12$, the probability of (1) is $\frac12\cdot\frac12\cdot\frac12=\frac18$. The probability of (2) is $\frac12\cdot\frac12\cdot1=\frac14$, and exactly the same calculation gives the probability of (3) and the probability of (4). These four possibilities are mutually exclusive, so the probability that one of them is true is $\frac18+\frac14+\frac14+\frac14=\frac78$.

In other words, for each $r\in[n]$ the probability that $r$ behaves in one of the ways consistent with $A_i\cap A_j\subseteq A_k$ is $\frac78$. This is the case independently for each $r\in[n]$, so the probability that all of them behave properly is $\left(\frac78\right)^n$.

Answer 2

The sets $A_i$ were constructed by taking each element of $[n]$ with probability $\frac 12$. An element $p$ can render $A_i \cap A_j \subseteq A_k$ false if it is in $A_i$ and $A_j$ but not in $A_k$. This requires three choices to be right, so happens in $\frac 18$ of the cases. To have $A_i \cap A_j \subseteq A_k$ true, none of the elements can render it false, so the chance is $(\frac 78)^n$