<s>[INST] Smallest length of {0,1} vectors to satisfy some orthogonality conditions Let $n$ be a positive integer.
The output of the problem is another positive integer $r$ which must be as small as possible.
I want to construct $2n$ binary vectors $x_i\in\{0,1\}^r$ and $y_i\in\{0,1\}^r$, with $i\in\{1,...,n\}$, which must respect the following conditions:


*

*$x_i^Ty_i=0$ with $i\in\{1,...,n\}$,

*$x_{i+1}^Ty_i=0$ with $i\in\{1,...,n-1\}$, and $x_1^Ty_n=0$ (it is cyclic).

*$x_{j}^Ty_i>0$ with $i\in\{1,...,n-1\}$, $j\in\{1,...,n\}\setminus \{i,i+1\}$.


All the vectors $x_i$ must be distinct and all the vectors $y_i$ must be distinct.

For a given number $n$ of vectors, what is the smallest dimension $r=f(n)$ for which it is possible to construct vectors $x_i,y_i$ respecting the
  conditions described above?

An obvious upper bound is $f(n)\leq n$.
Since the $x_i$ must be distinct, a lower bound is $f(n)\geq \lceil \log_2(n)\rceil$.
However, this lower bound seems rather weak.
Example for $n=7$, there is a solution with $r=6$ (but apparently, not with $r=5$):


*

*$x_1=\begin{pmatrix}0&0&1&0&1&1\end{pmatrix}^T$ $\hspace{1cm }$ $y_1=\begin{pmatrix}0&1&0&1&0&0\end{pmatrix}^T$.

*$x_2=\begin{pmatrix}1&0&0&0&1&1\end{pmatrix}^T$ $\hspace{1cm }$ $y_2=\begin{pmatrix}0&1&1&0&0&0\end{pmatrix}^T$.

*$x_3=\begin{pmatrix}1&0&0&1&0&1\end{pmatrix}^T$ $\hspace{1cm }$ $y_3=\begin{pmatrix}0&1&0&0&1&0\end{pmatrix}^T$.

*$x_4=\begin{pmatrix}0&0&1&1&0&1\end{pmatrix}^T$ $\hspace{1cm }$ $y_4=\begin{pmatrix}1&0&0&0&1&0\end{pmatrix}^T$.

*$x_5=\begin{pmatrix}0&1&1&1&0&0\end{pmatrix}^T$ $\hspace{1cm }$ $y_5=\begin{pmatrix}1&0&0&0&0&1\end{pmatrix}^T$.

*$x_6=\begin{pmatrix}0&1&0&1&1&0\end{pmatrix}^T$ $\hspace{1cm }$ $y_6=\begin{pmatrix}1&0&1&0&0&0\end{pmatrix}^T$.

*$x_7=\begin{pmatrix}0&1&0&0&1&1\end{pmatrix}^T$ $\hspace{1cm }$ $y_7=\begin{pmatrix}1&0&0&1&0&0\end{pmatrix}^T$.

 [/INST] The $\log_2 n$ lower bound is actually within a constant factor of optimal for large $n$.  
Now let $x_1, \dots, x_n$ be formed by randomly setting each coordinate of each $x_i$ to $1$ with probability $\frac{1}{3}$ (with the events $x_i(k)=1$ independent for all $1 \leq i \leq n$ and $1 \leq k \leq r$).  Let the vectors $y_1, \dots, y_n$ be defined by 
$$y_i(k)=\left\{\begin{array}{cc} 1 & \textrm{ if } x_i(k)=x_{i+1}(k)=0 \\
0 & \textrm{ otherwise } \end{array} \right.$$
The first two conditions are immediately satisfied by our definition of $y$.  What remains to check is that $x_j^T y_i>0$ for $j \notin \{i, i+1\}$.  
Note that for these $(i,j)$ the vectors $x_j$ and $y_i$ are independent.  So for any $k$, we have 
$$P(x_j(k)=y_i(k)=1)=\frac{1}{3} \left(\frac{2}{3}\right)^2 = \frac{4}{27}$$
Multiplying over all coordinates and taking the union bound over all pairs $(i,j)$, we have that the probability the third condition is violated is at most
$$n^2 \left(\frac{23}{27} \right)^r$$
So if $r=c \log n$ for $c>\log_{27/23} 2 \approx 4.323$ and $n$ is sufficiently large, then the probability some condition is violated tends to $0$, so there's a set of vectors which works.  
</s>