# Additional condition to the Bollobas theorem (Sperner's therorem) in extremal set theory

The Bollobas'1965 theorem is the following:

If $A_1,...,A_n$ and $B_1,...,B_n$ are two sequences of subsets of $X=\{1,...,r\}$ such that $A_i\cap B_j = \emptyset$ if and only if $i=j$, then $$\sum_{i=1}^n\binom{|A_i|+|B_i|}{|A_i|}^{-1}\leq 1.$$

First of all, I am interested in the case where $A_i$ and $B_i$ are complementary.

It means we obtain $$\sum_{i=1}^n\binom{r}{|A_i|}^{-1}\leq 1.$$ from which we have the Sperner's theorem since $\binom{r}{\lfloor \frac{r}{2} \rfloor}^{-1}\leq \binom{r}{k}^{-1}$ for all $k$: $$n\leq \binom{r}{\lfloor \frac{r}{2} \rfloor}.$$ For a given $n$, it is therefore easy to find the smallest value $r$ for which the previous inequality is verified.

However, I am interested in a special case where there are additional conditions on the $A_i$'s and $B_i$'s:

$$|(A_i\cap B_j) \cup (A_{i+1}\cap B_{j+1})|\geq 2, \text{ for all } i\neq j.$$

How could I adapt the previous results with this additional condition? That is, for a given $n$, how could I find the smallest integer $r$ such that all the conditions are verified?

I suppose that for a given $n$, the smallest integer $r$ for which there are such sets $A_i$ and $B_i$ will be bigger than without the additional conditions.

A way to prove the original problem is by counting the number of permutations separating a pair $(A,B)$ (see this link for example). However, I do not see how to adapt this approach.

• I'm not sure what you're asking here. Clearly the old proof still goes through if you have the additional assumption (since you don't need to actually use the assumption), and I think the standard example $A_i = \{1, \ldots, n\} \setminus \{i\}$, $B_i = \{i\}$ satisfies your extra assumption and shows that the upper bound is still best possible. – Gregory J. Puleo Feb 9 '16 at 16:32