6
$\begingroup$

For a graph $\Gamma$ and a digraph $\vec H$ we write $\Gamma\Rightarrow \vec H$ if any orientation of $\Gamma$ contains an isometric and isomorphic copy of the digraph $\vec H$. Since each graph admits an orientation without directed cycles, the relation $\Gamma\Rightarrow \vec H$ implies that the digraph $\vec H$ is acyclic (i.e., contains no directed cycles).

On the other hand, by Theorem 2.1 of this paper, for any acyclic finite digraph $\vec H$, there exists a finite graph $\Gamma$ with $\Gamma\Rightarrow\vec H$. The smallest possible number of vertices of a graph $\Gamma$ with $\Gamma\Rightarrow\vec H$ is denoted by $\mathsf{IR}(\vec H)$ and called the isometric Ramsey number of the digraph $\vec H$.

I am interested calculating (or evaluating) the numbers $\mathsf{IR}(\vec I_n)$ where $\vec I_n$ is the digraph with the set of vertices $V=\{1,\dots,n\}$ and the set of directed edges $E=\{(i,i+1):1\le i<n\}$.

Observe that the relation $\Gamma\Rightarrow \vec I_n$ holds if and only if any orientation $\vec \Gamma$ of edges of the graph $\Gamma$ contains two vertices at distance $n-1$ in $\Gamma$ that can be linked by a directed path of length $n-1$ in the digraph $\vec\Gamma$.

It can be shown that $\mathsf{IR}(\vec I_1)=1$, $\mathsf{IR}(\vec I_2)=2$ and $\mathsf{IR}(\vec I_3)=5$. The last equality follows from the fact that the cycle $C_5$ on 5 vertices has $C_5\Rightarrow \vec I_3$ (since each orientation of $C_5$ contains a directed path of length 2).

Concerning the number $\mathsf{IR}(\vec I_4)$, I can only prove the upper bound $\mathsf{IR}(\vec I_4)\le 30$. A graph $\Gamma$ on 30-vertices realizing the relation $\Gamma\Rightarrow\vec I_4$ is the rectangular product $C_5\times K_6$ (of the 5-cycle $C_5$ and the complete graph $K_6$ on 6 vertices).

Problem. Try to improve the upper bound $\mathsf{IR}(\vec I_4)\le 30$ or better find the exact value of $\mathsf{IR}(\vec I_4)$. A lower bound for $\mathsf{IR}(\vec I_4)$ (better than $12$) also would be very helpful.

Remark. By Corollary 3.6 in this paper we have the asymptotic upper bound $\mathsf{IR}(\vec I_n)=o(n^{2n})$ and very bad lower bound $\mathsf{IR}(\vec I_n)\ge\frac12n^2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.