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$.