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.

Thanks for your help!

  • 1
    $\begingroup$ 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. $\endgroup$ – Gregory J. Puleo Feb 9 '16 at 16:32
  • $\begingroup$ @GregoryJ.Puleo I edited my question. $\endgroup$ – Paul Bub. Feb 9 '16 at 16:54
  • $\begingroup$ I doubt that this allows to get better bound. $\endgroup$ – Fedor Petrov Feb 10 '16 at 16:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.