Forming Subsets

Question

This question is more of a graph problem. Suppose $A=\{1,2,..,n\}$, and we want to construct the sets $B(i)$,$1\leq i\leq n$, such that $i \not\in B(i)$ and the following constraints on the set $B(i)$ are satisfied:

1) If $j \in B(i)$ then $ i \notin B(j)$,

2) For all $i \in B(j)$, $B(j) \setminus \{i\} \not \subset B(i)$,

3) For all $i \notin B(k)$, $B(i) \not \subset {\{k\} \cup B(k)}$

Can we construct such subsets for all values of $n$? I can prove that you can construct such subsets for $n=4,5,6,..10$, but I can not generalize the proof for all values of $n$. I believe that such subsets cannot be constructed in general.

Answer 1

Consider a random tournament on $n$ vertices: for any two distinct vertices $i$, $j$ either $i\in B(j)$ or $j\in B(i)$ with probability $1/2$, all $\binom{n}2$ pairs $(i,j)$ are independent. Then the probability that for given vertices $i,k$ we have $B(i)\subset k\cup B(k)$ does not exceed $(3/4)^{n-2}$, since for any vertex $x\ne i,k$ the probability that $x\in B(i)\setminus B(k)$ equals $1/4$ and these events are independent. Using union bound, we see that the probability that some pair violates your condition does not exceed $n(n-1)(3/4)^{n-2}<1$ for large $n$.

Answer 2

Encouraged by the proof in the answer by Fedor Petrov, I started random search and found such subsets for each $n\leqslant200$ starting from $n=7$, which in addition satisfy the condition imposed by Fedor: for all $i\ne j$, either $i\in B(j)$ or $j\in B(i)$. Here is one for $n=7$: $$ \begin{aligned} B(1)&=\{2,3,5\},\\ B(2)&=\{3,4,6\},\\ B(3)&=\{4,5,7\},\\ B(4)&=\{5,6,1\},\\ B(5)&=\{6,7,2\},\\ B(6)&=\{7,1,3\},\\ B(7)&=\{1,2,4\}. \end{aligned} $$ As noticed in the comment by Gerhard "Nothing Escapes Him" Paseman, this one can be realized by a bijection between points and lines of the Fano plane.

Later

Here is, in fact, a (one of many) simple inductive construction of a tournament $B_n$ on vertices $\{1,...,n\}$ with needed properties for each $n\geqslant7$.

For $n=7$ just take $B_7(k)=B(k)$, $k=1,...,7$, with $B$ the one above.

Then for $n>7$ let $B_n(n)=B_7(7)=\{1,2,4\}$ for $n$ odd and $B_n(n)=B_7^{-1}(7)=\{3,5,6\}$ for $n$ even, and $$ B_n(k)= \begin{cases} B_{n-1}(k)\cup\{n\},&k\notin B_n(n),\\ B_{n-1}(k),&k\in B_n(n) \end{cases} $$ for $k=1,...,n-1$. That's it.

Still later

The proof seems to be not entirely trivial, so I decided to supply at least a sketch of it.

Let us denote for simplicity $i\in B(j)$ by $j\to i$. Note that for tournaments (i. e. when exactly one of $i\to j$ or $j\to i$ holds iff $i\ne j$), the requirements are equivalent to the existence, for all $i\to j$, of a $k$ with $i\to k\to j$.

Now by induction, if $B_{n-1}$ satisfies this, we have to check the above for $n\to i$ and for $i\to n$.

Now if $n\to i$ holds (i. e. $i\in B_n(n)$), then, noting that each $B_n(n)$ is in fact a 3-cycle (either $1\to2\to4\to1$ or $3\to5\to6\to3$), there always is a $j\in B_n(n)$ (i. e. $n\to j$) with $j\to i$.

And if $i\to n$ holds then $i\notin B_n(n)$, and, again by induction (see below), there is a $j\notin B_n(n)$ (hence $j\to n$) with $i\to j$.

To complete the induction, it remains to show that ($n\notin B_{n+1}(n+1)$ and) there is a $j\notin B_{n+1}(n+1)$ with $n\to j$. This is clear since $B_n(n)$ and $B_{n+1}(n+1)$ do not intersect, so we can take any $j\in B_n(n)$.