Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$

Question

Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$.

I have verified the statement for $n \leq 4$ with a Mathematica code. I have tried to prove the statement by considering the digraph $\Gamma(R)$ associated to $R$. I tried to use this fact: If $(x,y) \in \bigcap \limits_{\ell=1}^n R^\ell$ then there is a directed walk in $\Gamma(R)$ from $x$ to $y$ of every integer length $\ell \leq n$. This implies that $\Gamma(R)$ contains a cycle. I would like to show that this also implies that there is a directed walk in $\Gamma(R)$ from $x$ to $y$ of length $n+1$.

Answer 1

Let $k_n$ be the least integer $k$ such that, for any digraph $D$ of order $n$ and any vertices $x,y\in D$, if there are $x$-$y$ walks of length $1,\dots,k$, then there are $x$-$y$ walks of all positive integer lengths.

Theorem. $k_1=1$ and, for $n\ge2$, $$k_n=n-1+\max\{g(m)-m:0\le m\le n-2\}$$ where g(m) is Landau's function, the maximum order of an element in the symmetric group $\mathbf S_m$.

(So $k_n=n$ for $n\le8$, i.e., YCor's example with $n=9$ vertices is as small as possible.)

Trivially $k_1=1$; we consider $n\ge2$. I have to show that $$k_n=f(n):=n-1+\max\{g(m)-m:0\le m\le n-2\}.$$ Note that $f(n)\ge n$ since $g(0)=1$.

To show that $k_n\le f(n)$ it will suffice to prove the following:

Lemma 1. Suppose $x,y$ are vertices in a digraph of order $n\ge2$, and suppose $k\ge f(n)$. If there are $x$-$y$ walks of length $1,\dots,k$, then there is an $x$-$y$ walk of length $k+1$.

Proof. Assume for a contradiction that there are $x$-$y$ walks of length $1,\dots,k$ but none of length $k+1$.

Note that no cycle contains $x$ or $y$. For if $C$ were a cycle of length $m$ containing $x$ or $y$, then by adding $C$ to an $x$-$y$ walk of length $k+1-m$ we would get an $x$-$y$ walk of length $k+1$.

Let $C_1,\dots,C_t$ be a maximal family of (vertex-)disjoint cycles with respective lengths $m_1,\dots,m_t$. Let $m=m_1+\cdots+m_t\le n-2$ and let $L=\operatorname{LCM}(m_1,\dots,m_t)\le g(m)$. Now $$k\ge f(n)\ge n-1+g(m)-m\ge n-1+L-m,$$ whence $$k\ge k+1-L\ge n-m\ge2.$$ Let $W$ be an $x$-$y$ walk of length $k+1-L$. Then $W$ is disjoint from the cycles $C_1,\dots,C_t$, as otherwise there would be an $x$-$y$ walk of length $k+1$. So $W$ has at most $n-m$ vertices, and length $k+1-L\ge n-m$, so $W$ contains a cycle, which is disjoint from $C_,\dots,C_t$, contradicting the assumed maximality of that family of disjoint cycles.

We have shown that $k_n\le f(n)$. We will show $k_n\ge f(n)$ by generalizing YCor's construction.

Lemma 2. $k_{n+1}\ge k_n+1$.

Proof. Take a digraph of order $n$ with vertices $x,y$ such that there are $x$-$y$ walks of length $1,\dots,k_n-1$ but none of length $k_n$. Add a vertex $y'$ and an arc from $y$ to $y'$. In the resulting digraph of order $n+1$ there are $x$-$y'$ walks of length $1,\dots,k_n$ but none of length $k_n+1$.

Lemma 3. $k_n\ge g(n-2)+1$ for $n\ge2$.

Proof. Write $g(n-2)=\operatorname{LCM}(m_1,\dots,m_t)$ where $m_1+\cdots+m_t=n-2$. Consider a digraph consisting of disjoint cycles $C_1,\dots,C_t$ of respective lengths $m_1,\dots,m_t$ and two additional vertices $x$ and $y$. Draw an arc from $x$ to $y$; draw arcs from $x$ to one vertex in each cycle; and draw arcs to $y$ from all but one vertex in each cycle, chosen so that there is an $x$-$y$ walk through $C_i$ of length $k$ iff $k\not\equiv1\pmod{m_i}$. Thus there is an $x$-$y$ walk of length $k$ iff either $k=1$ or else $k\not\equiv1\pmod{g(n-2)}$.

We finish the proof of $k_n\ge f(n)$ by proving the following:

Lemma 4. If $0\le m\le n-2$ then $k_n\ge n-1+g(m)-m$.

Proof. By Lemmas 2 and 3, since $n\ge m+2$, $$k_n\ge n-(m+2)+k_{m+2}\ge n-m-2+g(m)+1$$ $$=n-1+g(m)-m.$$

Answer 2

This is false as shown by the following digraph.
From $x$ there is an edge to $v_p$, from $v_p$ there is a cycle of length $p$ to itself, and from $v_p$ there are $p-1$ different paths to $y$, of lengths $1,2,\ldots,p-1$.
Then using these $\Theta(p^2)$ vertices we can get from $x$ to $y$ through $v_p$ along a walk of length $\ell$ for any $\ell\not\equiv 1 \pmod p$.
If you repeat the above construction for every prime $p\le N$, and also add the edge $xy$, then the shortest missing length is $1+\prod_{p\le N \text{ prime }} p$, which is much bigger than $\sum_{p\le N \text{ prime }} \Theta(p^2)$.
It would be a nice problem to determine exactly up to what length you need walks to get walks of any length.

Update. Apparently, Aleksei has solved essentially the same question five years ago, with an asymptotically optimal bound.

Answer 3

domotorp's lovely solution is by far the best one, but here is an explicit counterexample for $n = 10$, I wonder if it's computationally tractable to figure out the max $n$ for which your statement holds.

$S = \{0,1,2,3,4,5,6,7,8,9\}$

$R = \{(0, 1), (0,6), (0,9), (1,2), (1,9), (2,3), (2,9), (3,4), (3,9), (4,5), (4,9), (5,1), (6,7), (6,9), (7,6)\}$

(It's not a typo that $8$ is not used.) This $R$ should have $(0,9) \in R \cap \dotsb \cap R^{10}$ but not $R^{11}$.

Answer 4

Here's an example of size 9 inspired by domotorp's anwer, where I only consider the primes $2,5$, and where I replace the additional long arrows from the basis of the cycles with arrows from the vertices themselves, which avoids additional vertices, and where I change the congruences to precisely forbid $n+1=10$ instead of $11$.

In words: I have 9 vertices: the initial and terminal vertices $x,y$, a $2$-cycle $v_2=\{b_0,b_1\}$, a $5$-cycle $v_5=\{c_0,\dots,c_4\}$. Join: $x\to y$, $x\to b_O$, $x\to c_0$, $b_1\to y$, $c_i\to y$ for $i=0,1,2,4$ (i.e. not for $i=3$), and the cycles $b_0\to b_1\to b_0$, $c_0\to c_1\to c_2\to c_3\to c_4\to c_0$.

Then for $m\ge 0$ there is a path from $x$ to $y$ of length $m$ iff $m$ is nonzero modulo $10$.

Here's a picture of the digraph: