182016261315

# Asymptotics for minimal overlapping patterns for generalized Euler
permutations, standard tableaux of rectangular shapes, and column strict
arrays

Ran Pan1  Jeffrey B. Remmel2  Department of Mathematics, UCSD La Jolla, CA,
92093-0112<EMAIL_ADDRESS>
Department of Mathematics, UCSD La Jolla, CA, 92093-0112<EMAIL_ADDRESS>
(2015-10-29; 2016-02-26; 2016-3-24)

###### Abstract

A permutation $\tau$ in the symmetric group $S_{j}$ is minimally overlapping
if any two consecutive occurrences of $\tau$ in a permutation $\sigma$ can
share at most one element. Bóna showed that the proportion of minimal
overlapping patterns in $S_{j}$ is at least $3-e$. Given a permutation
$\sigma$, we let $\text{Des}(\sigma)$ denote the set of descents of $\sigma$.
We study the class of permutations $\sigma\in S_{kn}$ whose descent set is
contained in the set $\\{k,2k,\ldots(n-1)k\\}$. For example, up-down
permutations in $S_{2n}$ are the set of permutations whose descent equal
$\sigma$ such that $\text{Des}(\sigma)=\\{2,4,\ldots,2n-2\\}$. There are
natural analogues of the minimal overlapping permutations for such classes of
permutations and we study the proportion of minimal overlapping patterns for
each such class. We show that the proportion of minimal overlapping
permutations in such classes approaches $1$ as $k$ goes to infinity. We also
study the proportion of minimal overlapping patterns in standard Young
tableaux of shape $(n^{k})$.

###### keywords:

permutations, arrays, minimal overlapping patterns

##  1 Introduction

Let $S_{n}$ denote the set of permutations of $[n]=\\{1,\ldots,n\\}$. We let
$k[n]=\\{k,2k,\ldots,nk\\}$ if $k,n\geq 1$. If
$\sigma=\sigma_{1}\ldots\sigma_{n}$ is an element of $S_{n}$, we let
$\text{Des}(\sigma)=\\{i:\sigma_{i}>\sigma_{i+1}\\}$. For any $k,n\geq 1$,
$\mathcal{C}_{=k[n-1]}$ denote the set of all $\sigma$ in $S_{kn}$ such that
$\text{Des}(\sigma)=k[n-1]$ and $\mathcal{C}_{\subseteq k[n-1]}$ denote the
set of all $\sigma$ in $S_{kn}$ such that $\text{Des}(\sigma)\subseteq
k[n-1]$. For example, elements of $\mathcal{C}_{=2[n-1]}$ are permutations
$\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{2n}\in S_{2n}$ such that

$\sigma_{1}<\sigma_{2}>\sigma_{3}<\sigma_{4}>\cdots.$

These are called up-down permutations or even alternating permutations.

One way to think of elements in $\mathcal{C}_{\subseteq k[n-1]}$ is as column
strict arrays which were studied by Harmse and Remmel in [6] and [7]. A
column-strict array $P$ is a filling of a $k\times n$ rectangular array with
$1,2,\cdots,kn$ such that elements increase from bottom to top in each column.
Let $\mathcal{F}_{n,k}$ denote the set of all the column-strict arrays with
$n$ columns and $k$ rows. Given a $P\in\mathcal{F}_{n,k}$, we let $P[i,j]$
denote element in the $i$th column and $j$th row where the columns are labeled
from left to right and the rows are labeled from bottom to top. We let
$\sigma_{P}$ denote the permutation

$\sigma_{p}=P[1,1]P[1,2]\ldots P[1,k]P[2,1]P[2,2]\ldots P[2,k]\ldots
P[n,1]P[n,2]\ldots P[n,k].$

For example, if $P$ is the element of $\mathcal{F}_{4,3}$ pictured in Figure
1, then $\sigma_{P}=3~{}11~{}12~{}1~{}2~{}4~{}6~{}8~{}10~{}5~{}7~{}9$. This
given, it is easy to see that $\sigma_{P}\in\mathcal{C}_{=k[n-1]}$ if and only
if $P[i,k]>P[i+1,1]$ for all $1\leq i\leq n-1$. An array
$P\in\mathcal{F}_{n,k}$ is a standard tableau of shape $(n^{k})$ if $P$ is
strictly increasing in rows, reading from left to right. That is, $P$ is
strictly increasing in rows if for all $1\leq j\leq k$,

$P[1,j]<P[2,j]<\cdots<P[n,j].$

We let $\mathcal{ST}(n^{k})$ denote the set of all standard tableaux of shape
$(n^{k})$.

Figure 1: An element of $\mathcal{F}_{4,3}.$

Given any sequence of pairwise distinct positive integers,
$\alpha=\alpha_{1}\ldots\alpha_{n}$, we let $\text{red}(\alpha)$ denote the
permutation of $S_{n}$ that results from $\alpha$ by replacing the $i$th
smallest element of $\alpha$ by $i$ for $i=1,\ldots,n$. For example,
$\text{red}(3~{}6~{}8~{}2~{}9)=2~{}3~{}4~{}1~{}5$. Given a permutation
$\tau\in S_{j}$ and permutation $\sigma=\sigma_{1}\ldots\sigma_{n}\in S_{n}$,
we say that

  1. 1.

$\tau$ occurs in $\sigma$ if there are $1\leq i_{1}<i_{2}<\cdots<i_{j}\leq n$
such that $\text{red}(\sigma_{i_{1}}\ldots\sigma_{i_{j}})=\tau$,

  2. 2.

$\sigma$ avoids $\tau$ if there is no occurrence of $\tau$ in $\sigma$, and

  3. 3.

there is a $\tau$-match in $\sigma$ starting at position $i$ if
$\text{red}(\sigma_{i}\sigma_{i+1}\ldots\sigma_{i+j-1})=\tau$.

We let $\tau\text{-mch}(\sigma)$ denote the number of $\tau$-matches in
$\sigma$. We say that $\tau$ has the minimal overlapping property or $\tau$ is
minimally overlapping if the smallest $n$ such that there exists $\sigma\in
S_{n}$ such that $\tau\text{-mch}(\sigma)=2$ is $2j-1$. This means in any two
consecutive $\tau$-matches in a permutation $\sigma$ can share at most one
element which must necessarily be at the end of the first $\tau$-match and the
start of the second $\tau$-match. It follows that if $\tau\in S_{j}$ is
minimally overlapping, then the smallest $n$ such that there exist a
$\sigma\in S_{n}$ such that $\tau\text{-mch}(\sigma)=k$ is $k(j-1)+1$. We call
these particular elements of $S_{k(j-1)+1}$ maximum packings for $\tau$ and we
let $\mathcal{MP}_{\tau,k(j-1)+1}=\\{\sigma\in
S_{k(j-1)+1}:\tau\text{-mch}(\sigma)=k\\}$. We let
$\text{mp}_{\tau,k(j-1)+1}=|\mathcal{MP}_{\tau,k(j-1)+1}|$

Minimal overlapping permutations are nice in that we have a nice expression
for the generating function of $x^{\tau\text{-mch}(\sigma)}$ over
permutations. That is, Duane and Remmel [3] proved the following theorem.

######  Theorem 1.

If $\tau\in S_{j}$ has the minimal overlapping property, then

$\sum_{n\geq 0}\frac{t^{n}}{n!}\sum_{\sigma\in
S_{n}}x^{\tau\text{-mch}(\sigma)}p^{\mathrm{coinv}(\sigma)}q^{\mathrm{inv}(\sigma)}=\\\
\frac{1}{1-(t+\sum_{n\geq
1}\frac{t^{n(j-1)+1}}{[n(j-1)+1]_{p,q}!}(x-1)^{n}\text{mp}_{\tau,n(j-1)+1}(p,q))}.$
(1)

Here if $\sigma=\sigma_{1}\ldots\sigma_{n}\in S_{n}$, then
$\mathrm{inv}(\sigma)=|\\{(i,j):1\leq i<j\leq n\ \&\
\sigma_{i}>\sigma_{j}\\}|$ and $\mathrm{coinv}(\sigma)=|\\{(i,j):1\leq i<j\leq
n\ \&\ \sigma_{i}<\sigma_{j}\\}|$ and

$\text{mp}_{\tau,n(j-1)+1}(p,q)=\sum_{\sigma\in\mathcal{MP}_{\tau,n(j-1)+1}}p^{\mathrm{coinv}(\sigma)}q^{\mathrm{inv}(\sigma)}.$

Harmse and Remmel generalized these definitions and results to
$\mathcal{F}_{n,k}$. However, as we shall see their definitions make perfectly
good sense in the the setting of $\mathcal{C}_{=k[n-1]}$ or
$\mathcal{ST}(n^{k})$. That is, if $F$ is any filling of a $k\times
n$-rectangle with distinct positive integers such that elements in each column
increase, reading from bottom to top, then we let $\text{red}(F)$ denote the
element of $\mathcal{F}_{n,k}$ which results from $F$ by replacing the $i$th
smallest element of $F$ by $i$. For example, Figure 2 pictures a filling $F$
with its corresponding reduced filling, $\text{red}(F)$.

Figure 2: An example of $\text{red}(F)$.

If $F\in\mathcal{F}_{n,k}$ and $1\leq c_{1}<\cdots<c_{j}\leq n$, then we let
$F[c_{1},\ldots,c_{j}]$ be the filling of the $k\times j$ rectangle where the
elements in column $a$ of $F[c_{1},\ldots,c_{j}]$ equal the elements in column
$c_{a}$ in $F$ for $a=1,\ldots,j$. We can then extend the usual pattern
matching definitions from permutations to elements of $\mathcal{F}_{n,k}$,
$\mathcal{C}_{=k[n-1]}$, or $\mathcal{ST}(n^{k})$ as follows.

######  Definition 2.

Let $P$ be an element of $\mathcal{F}_{j,k}$ $(\mathcal{C}_{=k[j-1]}$,
$\mathcal{ST}(j^{k}))$ and $F\in\mathcal{F}_{n,k}$ $(\mathcal{C}_{=k[n-1]}$,
$\mathcal{ST}(n^{k}))$ where $j\leq n$. Then we say

  1. 1.

$P$ occurs in $F$ if there are $1\leq i_{1}<i_{2}<\cdots<i_{j}\leq n$ such
that $\text{red}(F[i_{1},\ldots,i_{j}])=P$,

  2. 2.

$F$ avoids $P$ if there is no occurrence of $P$ in $F$, and

  3. 3.

there is a $P$-match in $F$ starting at position $i$ if
$\text{red}(F[i,i+1,\ldots,i+j-1])=P$.

We let $P\text{-mch}(F)$ denote the number of $P$-matches in $F$. For example,
if we consider the fillings $P\in\mathcal{F}_{3,3}$ and
$F,G\in\mathcal{F}_{6,3}$ shown in Figure 3, then it is easy to see that there
are no $P$-matches in $F$ but there is an occurrence of $P$ in $F$ since
$\text{red}(F[1,2,5])=P$. Also, there are 2 $P$-matches in $G$ starting at
positions 1 and 2, respectively, so $P\text{-mch}(G)=2$.

Figure 3: Examples of $P$-matches and occurrences of $P$.

We say that an element $P$ in $\mathcal{F}_{j,k}$ ($\mathcal{C}_{=k[n-1]}$,
$\mathcal{ST}(n^{k})$) has the minimal overlapping property or is minimally
overlapping if the smallest $i$ such that there exists an
$F\in\mathcal{F}_{i,k}$ ($\mathcal{C}_{=k[i-1]}$, $\mathcal{ST}(i^{k})$) with
$P\text{-mch}(F)=2$ is $2j-1$. Thus if $P$ has the minimal overlapping
property, then two consecutive $P$-matches can only overlap in a single
column, namely the last column of the first match and first column of the
second match. We say that $P$ is overlapping if $P$ is not minimal
overlapping.

If $P\in\mathcal{F}_{j,k}$ ($\mathcal{C}_{=k[j-1]}$, $\mathcal{ST}(j^{k})$)
has the minimal overlapping property, then the smallest $i$ such that there
exists an $F\in\mathcal{F}_{i,k}$ ($\mathcal{C}_{=k[i-1]}$,
$\mathcal{ST}(i^{k})$) such that $P\text{-mch}(F)=n$ is $n(j-1)+1$. If
$P\in\mathcal{F}_{j,k}$, we let $\mathcal{MP}_{P,n(j-1)+1}$ denote the set of
all $F\in\mathcal{F}_{n(j-1)+1,k}$ such that $P\text{-mch}(F)=n$ and set
$\text{mp}_{P,n(j-1)+1}=|\mathcal{MP}_{P,n(j-1)+1}|$. If
$P\in\mathcal{C}_{=k[j-1]}$, we let $\mathcal{CMP}_{P,n(j-1)+1}$ denote the
set of all $F\in\mathcal{C}_{=k[n(j-1)+1]}$ such that $P\text{-mch}(F)=n$ and
set $c\text{mp}_{P,n(j-1)+1}=|\mathcal{CMP}_{P,n(j-1)+1}|$. If
$P\in\mathcal{ST}(j^{k})$, we let $\mathcal{STMP}_{P,n(j-1)+1}$ denote the set
of all $F\in\mathcal{ST}((n(j-1)+1)^{k})$ such that $P\text{-mch}(F)=n$ and
set $st\text{mp}_{P,n(j-1)+1}=|\mathcal{STMP}_{P,n(j-1)+1}|$. In each case we
shall call an $F\in\mathcal{MP}_{P,n(j-1)+1}$
($F\in\mathcal{CMP}_{P,n(j-1)+1}$, $F\in\mathcal{STMP}_{P,n(j-1)+1}$) a
maximum packing for $P$.

Given $P\in\mathcal{F}_{j,k}$, let

$A_{P}(x,t)=\sum_{n\geq
0}\frac{t^{n}}{(kn)!}\sum_{F\in\mathcal{F}_{n,k}}x^{P\text{-mch}(F)}.$

Clearly, when $x=0$,

$A_{P}(0,t)=\sum_{n\geq
0}\frac{t^{n}}{(kn)!}\left|\\{F\in\mathcal{F}_{n,k}:P\text{-mch}(F)=0\\}\right|.$

For $P,Q\in\mathcal{F}_{j,k}$, if $A_{P}(0,t)=A_{Q}(0,t)$, we say $P$ and $Q$
are c-Wilf equivalent. If $A_{P}(x,t)=A_{Q}(x,t)$, we say $P$ and $Q$ are
strongly c-Wilf equivalent. In [10], in the case where $k=1$, Nakamura
conjectured that if two permutations are c-Wilf equivalent then they are also
strongly c-Wilf equivalent. Harmse and Remmel gave a similar conjecture in [7]
when $k\geq 2$. That is, they made the following conjecture.

######  Conjecture 3.

$P,Q\in\mathcal{F}_{n,k}$ are c-Wilf equivalent if and only if $P$ and $Q$ are
strongly c-Wilf equivalent.

It has been shown that the conjecture holds for minimal overlapping patterns
and the first and the last column of a pattern determines which c-Wilf
equivalence class it belongs to (see [2], [3], [4], and [7]). The key to
proving such results is to prove an analogue to Theorem 1. This was done by
Harmse and Remmel [7] who proved the following theorem for minimal overlapping
patterns in $\mathcal{F}_{j,k}$.

######  Theorem 4.

Suppose that $k\geq 2$, $j\geq 2$, and $P\in\mathcal{F}_{j,k}$ has the minimal
overlapping property. Then

$A_{P}(t,x)=\frac{1}{1-(\frac{t}{k!}+\sum_{n\geq
1}\frac{t^{n(j-1)+1}}{(k(n(j-1)+1))!}(x-1)^{n}\text{mp}_{P,n(j-1)+1})}.$ (2)

One can prove analogous results for minimal overlapping patterns $P$ in
$\mathcal{C}_{=k[j-1]}$ and for minimal overlapping patterns $P$ in
$\mathcal{ST}(j^{k})$. However, such results can no longer be expressed just
in terms of maximum packings, but require a more sophisticated concept of
generalized maximum packing. This will be the subject of a forthcoming paper
[11].

The main focus of this paper is the following questions.

How many minimal overlapping patterns are there in $\mathcal{F}_{n,k}$?

How many minimal overlapping patterns are there in $\mathcal{ST}(n^{k})$?

How many minimal overlapping patterns are there in $\mathcal{C}_{=k[n-1]}$?

We let $M_{n,k}$ ($STM_{n,k}$, $CM_{n,k}$) denote the number of minimal
overlapping patterns in $\mathcal{F}_{n,k}$ ( $\mathcal{ST}(n^{k})$,
$\mathcal{C}_{=k[n-1]}$). Then we will be interested in the following
quantities:

$\displaystyle a_{n,k}$ $\displaystyle=$
$\displaystyle\frac{M_{n,k}}{|\mathcal{F}_{n,k}|},$ $\displaystyle b_{n,k}$
$\displaystyle=$ $\displaystyle\frac{STM_{n,k}}{|\mathcal{ST}(n^{k})|},\
\mbox{and}$ $\displaystyle c_{n,k}$ $\displaystyle=$
$\displaystyle\frac{CM_{n,k}}{|\mathcal{C}_{=k[n-1]}|}.$

Bóna studied the behavior of $a_{n,1}$ in [1]. In [1], Bóna proved that
$a_{n,1}\geq 3-e\approx 0.2817$. That is, he proved that at least 28.17% of
the permutations in $S_{n}$ are minimimal overlapping. Moreover, he proved
that $\lim\limits_{n\rightarrow\infty}a_{n,1}$ exists. The main goal of this
paper is to prove similar results for $a_{n,k}$, $b_{n,k}$, and $c_{n,k}$.

The outline of this paper is as follows. In Section 2, we shall give general
lower bound for $a_{n,k}$ for all $k$. In Section 3, we shall give formulas
for $M_{n,k}$ and $a_{n,k}$. In Section 4, we shall study the asymptotic
behavior of $\\{a_{n,k}\\}$ for fixed $k$. In Section 5, we shall analyze
$b_{n,k}$ and in Section 6, we shall analyze $c_{n,k}$. In section 7, we shall
briefly discuss some open questions about the problem of finding the number of
minimal overlapping permutations that start with a given initial segment.

##  2 Lower Bound for $a_{n,k}$

Bóna proved that the probability that a randomly selected pattern in
$\mathcal{F}_{n,1}$ is minimal overlapping is at least $3-e\approx 0.282$,
that is, $L_{1}=3-e$ is a lower bound for $\\{a_{n,1}\\}_{n\geq 1}$,
independent on $n$. Based on Bóna’s idea in [1], we are able to find a basic
lower bound $L_{k}$ for $\\{a_{n,k}\\}_{n\geq 1}$ for any given $k\geq 1$.

We say that $P\in\mathcal{F}_{n,k}$ is overlapping at position $i$ if
$\text{red}(P[1,\ldots,i])=\text{red}(P[n-i+1,\ldots,n])$. That is, the
reduction of the first $i$ columns of $P$ is equal to the reduction of the
last $i$ columns of $P$. Suppose $P\in\mathcal{F}_{n,k}$ is overlapping, then
there exists integer $i$, $2\leq i\leq n-1$ such that $P$ is overlapping at
position $i$. Furthermore, one can easily check that $P$ is overlapping if and
only if there exists integer $i$, $2\leq i<\frac{n}{2}+1$ such that $P$ is
overlapping at position $i$. Let $E_{i}$ be the event that $P$ is overlapping
at position $i$. If $2\leq i\leq\frac{n}{2}+1$, the probability that $E_{i}$
happens $Pr(E_{i})=\frac{(k!)^{i}}{(ik)!}$. That is, we can partition the
elements of $\mathcal{F}_{n,k}$ by the set of elements that lie in the first
$i$ columns of $P$ and the set of elements that lie in the last $i$ columns of
$P$. Once the filling of the first $i$ columns of $P$ is fixed, there are
$\frac{(ik)!}{(k!)^{i}}$ ways to arrange the elements in the last $i$ columns
and only one of them is favorable. If $\frac{n}{2}<i<\frac{n}{2}+1$,
$Pr(E_{i})\leq\frac{(k!)^{i}}{(ik)!}$. Then the probability that a randomly
selected pattern in $\mathcal{F}_{n,k}$ is overlapping is bounded by

$Pr\left(\bigcup_{2\leq i<\frac{n}{2}+1}E_{i}\right)\leq\sum_{2\leq
i<\frac{n}{2}+1}Pr(E_{i})\leq\sum_{2\leq
i<\frac{n}{2}+1}\frac{(k!)^{i}}{(ik)!}<\sum_{i\geq 2}\frac{(k!)^{i}}{(ik)!}.$

Then for a fixed $k$, we get a lower bound $L_{k}$ for $\\{a_{n,k}\\}_{n\geq
1}$.

######  Theorem 5.

$L_{k}=1-\sum_{i\geq 2}\frac{(k!)^{i}}{(ik)!}.$ (3)

Then by Theorem 5, we can compute $L_{1}$ and $L_{2}$ directly.

$\displaystyle L_{1}$ $\displaystyle=$ $\displaystyle 1-\sum_{i\geq
2}\frac{1}{i!}=1-(-2+e)=3-e\approx 0.282.$ $\displaystyle L_{2}$
$\displaystyle=$ $\displaystyle 1-\sum_{i\geq
2}\frac{(2!)^{i}}{(2i)!}=3-\sum_{i\geq
0}\frac{2^{i}}{(2i)!}=3-\frac{1}{2}\left(\sum_{i=0}\frac{(\sqrt{2})^{i}}{i!}+\sum_{i=0}\frac{(-\sqrt{2})^{i}}{i!}\right)$
$\displaystyle=$ $\displaystyle
3-\frac{1}{2}\left(e^{\sqrt{2}}+e^{-\sqrt{2}}\right)=3-\cosh(\sqrt{2})\approx
0.822.$

The results above indicate there are at least 28.2$\%$ of patterns in
$\mathcal{F}_{n,1}$ that are minimal overlapping, and at least 82.2$\%$ of
patterns in $\mathcal{F}_{n,2}$ that are minimal overlapping, no matter what
$n$ is.

Moreover, by observing Equation (3), one can easily find that the sequence
$\\{L_{k}\\}$ is monotone increasing. It agrees with our intuition because a
pattern is minimal overlapping as long as there exists one row whose reduction
is minimal overlapping and, hence, more rows means higher chance to be minimal
overlapping. Also, since $\\{L_{k}\\}$ is bounded by $1$, the sequence
converges.

######  Theorem 6.

$\lim_{k\rightarrow\infty}L_{k}=1.$ (4)

###### Proof.

Since

$L_{k}=1-\sum_{i\geq 2}\frac{(k!)^{i}}{(ik)!},$

to show (4) it suffices to show

$\lim_{k\rightarrow\infty}\sum_{i\geq 2}\frac{(k!)^{i}}{(ik)!}=0.$

For $i\geq 2$,

$\lim_{k\rightarrow\infty}\frac{(k!)^{i}}{(ik)!}=0\text{, }\phantom{123}\text{
}\left|\frac{(k!)^{i}}{(ik)!}\right|\leq\frac{1}{i^{2}}\phantom{123}\text{
}\text{ and }\phantom{123}\text{}\sum_{i\geq 2}\frac{1}{i^{2}}<\infty.$

Then by the dominated convergence theorem,

$\lim_{k\rightarrow\infty}\sum_{i\geq 2}\frac{(k!)^{i}}{(ik)!}=\sum_{i\geq
2}\lim_{k\rightarrow\infty}\frac{(k!)^{i}}{(ik)!}=0.$

∎

Thus we have the following corollary.

######  Corollary 7.

For a given $n$,

$\lim_{k\rightarrow\infty}a_{n,k}=1.$ (5)

Now we see no matter how large $n$ is, almost every pattern in
$\mathcal{F}_{n,k}$ is minimal overlapping as long as $k$ is large enough.
Another fact worth mentioning is that $\\{L_{k}\\}$ converges to $1$ rapidly.
By (3), $L_{1}\approx 0.282$, $L_{2}\approx 0.822$, $L_{3}\approx 0.950$,
$L_{4}\approx 0.986$, $L_{5}\approx 0.996$, $\cdots$.

##  3 Formulas for $M_{n,k}$ and $a_{n,k}$

It follows from our observations in the previous section that a pattern
$P\in\mathcal{F}_{n,k}$ is overlapping if and only if there exists a unique
integer $i$ such that $P$ is overlapping at position $i$ and the reduction of
the first $i$ columns of $P$ is minimally overlapping with $2\leq
i<\frac{n}{2}+1$. The basic idea of obtaining the formula for $M_{n,k}$, the
number of minimal overlapping patterns in $\mathcal{F}_{n,k}$, is to subtract
the number of overlapping patterns from the total number.

Assuming $n$ is fixed, we separate the discussion of $M_{n,k}$ into two cases.

Case 1. $k$ is an even number.

$\displaystyle M_{n,k}$ $\displaystyle=$
$\displaystyle\binom{nk}{k,k,\ldots,k}-M_{2,k}\binom{nk}{2k,2k}\binom{(n-4)k}{k,k,\cdots,k}-M_{3,k}\binom{nk}{3k,3k}\binom{(n-6)k}{k,k,\cdots,k}$
$\displaystyle-M_{4,k}\binom{nk}{4k,4k}\binom{(n-8)k}{k,k,\ldots,k}-\cdots-
M_{\frac{n}{2},k}\binom{nk}{\frac{1}{2}nk,\frac{1}{2}nk}$ $\displaystyle=$
$\displaystyle\frac{(nk)!}{(k!)^{n}}-\sum_{i=2}^{\frac{n}{2}}M_{i,k}\binom{nk}{ik,ik}\frac{((n-2i)k)!}{(k!)^{n-2i}}.$

The only significant difference between the even case and the odd case is the
term corresponding to patterns overlapping at position $\frac{n+1}{2}$.

Case 2. $n$ is an odd number.

$\displaystyle M_{n,k}$ $\displaystyle=$
$\displaystyle\binom{nk}{k,k,\ldots,k}-M_{2,k}\binom{nk}{2k,2k}\binom{(n-4)k}{k,k,\cdots,k}-M_{3,k}\binom{nk}{3k,3k}\binom{(n-6)k}{k,k,\cdots,k}$
$\displaystyle-\cdots-
M_{\frac{n-1}{2},k}\binom{nk}{\frac{1}{2}(n-1)k,\frac{1}{2}(n-1)k}-\sum_{P\in\mathcal{M}_{\frac{n+1}{2},k}}\text{mp}_{P,n}$
$\displaystyle=$
$\displaystyle\frac{(nk)!}{(k!)^{n}}-\sum_{i=2}^{\frac{n-1}{2}}M_{i,k}\binom{nk}{ik,ik}\frac{((n-2i)k)!}{(k!)^{n-2i}}-\sum_{P\in\mathcal{M}_{\frac{n+1}{2},k}}\text{mp}_{P,n}.$

Dividing $M_{n,k}$ by $|\mathcal{F}_{n,k}|$, we get formula of $a_{n,k}$ as
follows

######  Theorem 8.

If $n$ is even, $\displaystyle
a_{n,k}=1-\sum_{i=2}^{\frac{n}{2}}a_{i,k}\frac{(k!)^{i}}{(ik)!}.$ (6) If $n$
is odd, $\displaystyle
a_{n,k}=1-\sum_{i=2}^{\frac{n-1}{2}}a_{i,k}\frac{(k!)^{i}}{(ik)!}-b_{n,k},$
(7)

where
$b_{n,k}=\frac{\sum_{P\in\mathcal{M}_{\frac{n+1}{2},k}}\text{mp}_{P,n}}{|\mathcal{F}_{n,k}|}$.

It may seem that (6) and (7) gives us a way to recursively compute $a_{n,k}$,
but unfortunately this is not the case. That is, while the even terms depend
only on the previous values, the odd terms rely on both previous terms and
$\sum_{P\in\mathcal{M}_{(n+1)/2,k}}\text{mp}_{P,n}$ which is difficult to
compute. Indeed, we have no general way to compute $\text{mp}_{P,n}$ for a
fixed minimal overlapping $P$.

##  4 The limit of $a_{n,k}$

In this section, we study the asymptotic behavior of $\\{a_{n,k}\\}_{n\geq
1}$, for any given integer $k\geq 1$. Throughout this section, we shall assume
that $k$ is a fixed number greater than or equal to 1. We let $\\{d_{n}\\}$ be
the subsequence of $\\{a_{n,k}\\}_{n\geq 1}$ consisting of odd terms, ie.,
$d_{j}=a_{2j-1,k}$, $j=1,2,3,\cdots$. We let $\\{e_{n}\\}$ be the subsequence
consisting of even terms.

From equation (6) in Theorem 8, we see $\\{e_{n}\\}$ is a monotone decreasing
sequence and $a_{n,k}$ has lower bound $L_{k}$, hence $\\{e_{n}\\}$ is
convergent. To show $a_{n,k}$ has a limit, we need to show $\\{d_{n}\\}$
converges to the limit of $\\{e_{n}\\}$. This will result in the following
theorem.

######  Theorem 9.

For a fixed integer $k\geq 1$, $\lim\limits_{n\rightarrow\infty}a_{n,k}$
exists.

###### Proof.

We only need to show the limit of $d_{n}$ equals the limit of $e_{n}$. Since
$d_{n+1}=a_{2n+1,k}$ and $e_{n}=a_{2n,k}$, by (6) and (7), we have
$e_{n}-d_{n+1}=b_{2n+1,k}$.

$b_{2n+1,k}=\frac{\sum_{P\in\mathcal{M}_{n+1,k}}\text{mp}_{P,2n+1}}{|\mathcal{F}_{2n+1,k}|}\leq\frac{M_{n+1,k}\binom{(2n+1)k}{nk}}{|\mathcal{F}_{2n+1,k}|}$
(8)

The inequality holds because that the fact that the reduction of the first
$n+1$ columns of a pattern in $\mathcal{F}_{2n+1,k}$ is minimal overlapping
does not guarantee the pattern is overlapping at position $n+1$. In other
words, it is a necessary condition that the reduction of the first $n+1$
columns is minimal overlapping but that it is not sufficient. Take patterns in
$\mathcal{F}_{5,1}$ as an example. Assume the reduction of the first three
numbers is $1~{}3~{}2$ which is minimal overlapping. If the initial three
numbers are $3~{}4~{}2$, we can put $5~{}1$ in the end to make
$3~{}4~{}2~{}5~{}1$ overlapping at the middle position. However, a pattern
with prefix $3~{}4~{}2$ can not be overlapping at position $3$. We use RHS for
the right-handed side of (8).

RHS $\displaystyle=$
$\displaystyle\frac{\binom{(2n+1)k}{nk}M_{n+1,k}}{|\mathcal{F}_{2n+1,k}|}=\frac{\binom{(2n+1)k}{nk}|\mathcal{F}_{n+1,k}|a_{n+1,k}}{|\mathcal{F}_{2n+1,k}|}$
$\displaystyle=$
$\displaystyle\frac{(2nk+k)!(nk+k)!(k!)^{2n+1}}{(nk)!(nk+k)!(k!)^{n+1}(2nk+k)!}a_{n+1,k}$
$\displaystyle=$ $\displaystyle\frac{(k!)^{n}}{(nk)!}a_{n+1,k}$
$\displaystyle=$ $\displaystyle\frac{a_{n+1,k}}{|\mathcal{F}_{n,k}|}.$

As $n$ goes to infinity, $|\mathcal{F}_{n,k}|$ goes to infinity and because
$a_{n+1,k}$ is bounded by $1$,

$\lim_{n\rightarrow\infty}e_{n}-d_{n+1}=\lim_{n\rightarrow\infty}b_{2n+1,k}=0.$

Therefore,
$\lim\limits_{n\arrowvert\infty}{d_{n}}=\lim\limits_{n\arrowvert\infty}{e_{n}}$
and then hence $\lim\limits_{n\rightarrow\infty}a_{n,k}$ exists. ∎

Note that $|\mathcal{F}_{n,k}|$ increases rapidly as $n$ increases so that
$a_{n,k}$ converges rapidly. The larger $k$ becomes, the faster $a_{n,k}$
converges.

Let $l_{k}$ be the limit of $a_{n,k}$ as $n$ goes to infinity. Using Monte
Carlo methods, we computed approximate values for $l_{k}$ for $k=1,2,3,4$:
$l_{1}\approx 0.364$, $l_{2}\approx 0.823$, $l_{3}\approx 0.949$ and
$l_{4}\approx 0.986$. Comparing $L_{k}$ and $l_{k}$, we find they are very
close. This is not a coincidence because (3) is almost the same as (6) and (7)
and we know $a_{n,k}$ is close to $1$ when $n$ is large.

##  5 Standard tableaux of rectangular shapes

The set of all the standard Young tableaux of rectangular shape $n^{k}$ is
denoted by $\mathcal{ST}(n^{k})$ and clearly it is a subset of
$\mathcal{F}_{n,k}$. It is well-known that the cardinality of
$\mathcal{ST}(n^{2})$ is the $n$th Catalan number
$\text{Cat}(n)=\frac{1}{n+1}\binom{2n}{n}$. Then using the similar argument of
Theorem 5, we have a lower bound for $b_{n,2}$, where $b_{n,2}$ is proportion
of minimal overlapping patterns in $\mathcal{ST}(n^{2})$

$L^{S}_{2}=1-\sum_{i\geq 2}\frac{1}{\text{Cat}(i)}.$

To find the exact value of the lower bound, we must compute the sum
$\sum_{i\geq 2}\frac{1}{\text{Cat}(i)}$. Define a power series $f(x)$ as
follows

$f(x)=\sum_{i\geq 1}\frac{1}{\text{Cat}(i)}x^{i}.$

Then

$xf^{\prime}(x)=x\sum_{i\geq 1}\frac{i}{\text{Cat}(i)}x^{i-1}=\sum_{i\geq
1}\frac{i}{\text{Cat}(i)}x^{i}$

By the recursion of Catalan numbers
$\text{Cat}(i+1)=\frac{4i+2}{i+2}\text{Cat}(i)$,

$\displaystyle xf^{\prime}(x)$ $\displaystyle=$ $\displaystyle\sum_{i\geq
1}\frac{i+2-2}{\text{Cat}(i)}x^{i}=\sum_{i\geq
1}\frac{i+2}{\text{Cat}(i)}x^{i}-2\sum_{i\geq
1}\frac{1}{\text{Cat}(i)}x^{i}=\sum_{i\geq
1}\frac{4i+2}{\text{Cat}(i+1)}x^{i}-2f(x)$ $\displaystyle=$
$\displaystyle\sum_{i\geq
1}\frac{4(i+1)-2}{\text{Cat}(i+1)}x^{i}-2f(x)=4\sum_{i\geq
1}\frac{i+1}{\text{Cat}(i+1)}x^{i}-2\sum_{i\geq
1}\frac{1}{\text{Cat}(i+1)}x^{i}-2f(x)$ $\displaystyle=$
$\displaystyle\frac{4}{x}(xf^{\prime}(x)-x)-\frac{2}{x}(f(x)-x)-2f(x)=4f^{\prime}(x)-\frac{2x+2}{x}f(x)-2.$

So we obtain a first-order ordinary differential equation

$f^{\prime}(x)+\left(\frac{2x+2}{x^{2}-4x}\right)f(x)=\frac{2}{4-x}.$ (9)

Solving this differential equation (9) with the initial value condition
$f(0)=0$ for $f(x)$ yields

$\frac{(x-10)(x-4)x+24\sqrt{4x-x^{2}}\arcsin\left(\frac{\sqrt{x}}{2}\right)}{(4-x)^{3}}$

Setting $x=1$ in this formula for $f(x)$ gives our next theorem.

######  Theorem 10.

$\sum_{i\geq 1}\frac{1}{\text{Cat}(i)}=1+\frac{4\sqrt{3}\pi}{27}.$ (10)

Then by the above equation, we have the lower bound
$L^{S}_{2}=1-\frac{4\sqrt{3}\pi}{27}\approx 0.194$.

Similarly, for any given $k$, lower bounds for $b_{n,k}$, that is, lower bound
for the proportion of minimal overlapping patterns in $\mathcal{ST}(n^{k})$ is

$L_{k}^{S}=1-\sum_{i\geq 2}\frac{1}{Y_{i^{k}}},$

where $Y_{i^{k}}=|\mathcal{ST}(i^{k})|$ which could be counted by the hook-
length formula. We computed the following approximations for $L_{k}$ for
$k=3,4,5,6$.

$L_{3}^{S}\approx 0.774,\phantom{123}L_{4}^{S}\approx
0.926,\phantom{123}L_{5}^{S}\approx 0.976,\phantom{123}L_{6}^{S}\approx
0.992.$

It is easy for one to show that $\lim\limits_{k\rightarrow\infty}L_{k}^{S}=1$
which implies almost every pattern in $\mathcal{ST}(n^{k})$ is minimal
overlapping as $k$ is very large.

Next we shall find an upper bound for the proportion of minimal overlapping
standard tableaux of shape $n^{2}$. This is equivalent to finding a lower
bound for the proportion of overlapping patterns. For a pattern
$P\in\mathcal{ST}(n^{2})$, $n\geq 3$, we only consider patterns where the
reduction of the first two columns is the same as the reduction of the last
two columns. There are only two cases for such overlapping patterns. For Case
1 (Figure 4), the number of such overlapping patterns in
$\mathcal{ST}((n+2)^{2})$ is equal to $|\mathcal{ST}(n^{2})|$.

Figure 4: Reducing via the patterns in the first two columns for Case 1

For Case 2 (Figure 5), the number of such overlapping patterns in
$\mathcal{ST}((n+2)^{2})$ is equal to the number of standard Young tableaux of
skew shape $(n+2,n)/(2)$.

Figure 5: Reducing via the patterns in the first two columns for Case 2

It is easy to see that the number of standard tableaux of shape $(n+2,n)/(2)$
is equal to the number of standard tableaux of shape $(n+2,n)$ where 1 and 2
lie in the first row. But then the number of standard tableaux of $(n+2,n)$
where 1 and 2 lie in the first row is equal to the number of standard tableaux
of shape $(n+2,n)$ minus the number of standard tableaux of shape $(n+2,n)$
where 1 and 2 lie first column. But then the number of standard tableaux of
shape $(n+2,n)$ where 1 and 2 lie first column is equal to the number of
standard tableaux of shape $(n+1,n-1)$. Using the hook length formula for the
number of standard tableaux, it follows that

$\displaystyle|\mathcal{ST}(n+2,n)/(2)|$ $\displaystyle=$
$\displaystyle|\mathcal{ST}(n+2,n)|-|\mathcal{ST}(n+1,n-1)|$ $\displaystyle=$
$\displaystyle\frac{3(2n+2)!}{(n+3)!n!}-\frac{3(2n)!}{(n+2)!(n-1)!}$
$\displaystyle=$
$\displaystyle\frac{9n^{2}+9n+6}{(n+3)(n+2)(n+1)}\binom{2n}{n}.$

Since the lower bound for number of overlapping patterns in
$\mathcal{ST}((n+2)^{2})$ is
$|\mathcal{ST}(n^{2})|+|\mathcal{ST}((n+2,n)/(2))|$, an upper bound for
$b_{n+2,2}$, $n\geq 3$ is

$\displaystyle U_{n+2,2}^{S}$ $\displaystyle=$ $\displaystyle
1-\frac{|\mathcal{ST}(n^{2})|+|\mathcal{ST}((n+2,n)/(2))|}{|\mathcal{ST}((n+2)^{2})|}$
$\displaystyle=$ $\displaystyle\frac{3n^{2}+9n}{8n^{2}+16n+6}.$

As $n$ goes to infinity, $U_{n+2,2}^{S}$ converges to $0.375$. Therefore,
$\\{b_{n,2}\\}$ is asymptotically between $0.194$ and $0.375$.

##  6 Generalized Euler permutations

Elements in $\mathcal{C}_{=k[n-1]}$ are called generalized Euler permutations
or $k$-up-down permutations. Note that $2$-up-down permutations are usually
called up-down permutations. For example,
$\sigma=2~{}3~{}5~{}8~{}1~{}4~{}6~{}7$ is a $4$-up-down permutation of length
$8$ and $\mu=1~{}5~{}2~{}6~{}3~{}4$ is an up-down permutation permutation of
length $6$.

Next we give a lower bound $L^{E}_{k}$ for $\\{c_{n,k}\\}_{n\geq 2}$, that is,
the proportion of minimal overlapping patterns in $\mathcal{C}_{=k[n-1]}$.
Using essentially the same argument that we used to prove Theorem 5, we have a
lower bound $L^{E}_{k}$

$L^{E}_{k}=1-\sum_{j\geq 2}\frac{1}{|\mathcal{C}_{=k[j-1]}|},$

where $|\mathcal{C}_{=k[j-1]}|$ is the number of $k$-up-down permutations of
length $kj$. The generating function of $|\mathcal{C}_{=k[j-1]}|$ is

$\sum_{n\geq
0}|\mathcal{C}_{=k[j-1]}|\frac{t^{kn}}{(kn)!}=\frac{1}{\sum_{n\geq
0}\frac{(-1)^{n}t^{kn}}{(kn)!}}.$

See Stanley’s book, Chapter 3, page 389 [14]. It is apparent that for fixed
$k$, $L^{E}_{k}$ converges so we can calculate numerical approximation

$\displaystyle L^{E}_{2}$ $\displaystyle=$ $\displaystyle 1-\sum_{j\geq
2}\frac{1}{|\mathcal{C}_{=2[j-1]}|}=1-\frac{1}{5}-\frac{1}{61}-\frac{1}{1382}-\frac{1}{50521}-\cdots\approx
0.783,$ $\displaystyle L^{E}_{3}$ $\displaystyle=$ $\displaystyle
1-\sum_{j\geq
2}\frac{1}{|\mathcal{C}_{=3[j-1]}|}=1-\frac{1}{19}-\frac{1}{1513}-\frac{1}{315523}-\cdots\approx
0.947,$ $\displaystyle L^{E}_{4}$ $\displaystyle=$ $\displaystyle
1-\sum_{j\geq
2}\frac{1}{|\mathcal{C}_{=4[j-1]}|}=1-\frac{1}{69}-\frac{1}{33661}-\frac{1}{60376809}-\cdots\approx
0.985,$ $\displaystyle L^{E}_{5}$ $\displaystyle=$ $\displaystyle
1-\sum_{j\geq
2}\frac{1}{|\mathcal{C}_{=5[j-1]}|}=1-\frac{1}{251}-\frac{1}{750751}-\frac{1}{11593285251}-\cdots\approx
0.996.$

It is easy for one to show that $\lim\limits_{k\rightarrow\infty}L^{E}_{k}=1$
which means almost all patterns in $\mathcal{C}_{=k[n-1]}$ are minimal
overlapping when $k$ is large.

Next we will find an upper bound for $c_{n,2}$. It is well-known that numbers
of up-down permutations are Euler numbers. Suppose $E(n)$ is the $n$th Euler
number, then $|\mathcal{C}_{=2[n-1]}|=E(2n)$. By [15], the ratio of two
adjacent Euler numbers have asymptotic estimation as follows

$\frac{E(n+1)}{E(n)}\sim\frac{2(n+1)}{\pi}.$ (11)

To find an upper bound of minimal overlapping patterns, we only need to find a
lower bound for overlapping up-down permutations. Similar to Section 5, we
only consider patterns where the reduction of the first two columns is the
same as the reduction of the last two columns. In other words, we only
consider prefixes and suffixes of length $4$ in an up-down permutation and
they have the same reduction. In [12], the number of such overlapping up-down
permutations of length $2n$ is given as

$13E(2n)-32nE(2n-1)+10n(2n-1)E(2n-2),$

where $n\geq 4$. Hence we can get an upper bound for the percentage of minimal
overlapping patterns in $\mathcal{C}_{=2[n-1]}$.

$U^{E}_{n,2}=1-\frac{13E(2n)-32nE(2n-1)+10n(2n-1)E(2n-2)}{E(2n)}.$

Applying (11), we get an asymptotic upper bound

$U^{E}_{2}=\lim\limits_{n\rightarrow\infty}U^{E}_{n,2}=8\pi-\frac{5}{4}\pi^{2}-12\approx
0.795.$

Therefore, $\\{c_{n,2}\\}$ is asymptotically between $0.783$ and $0.795$.

##  7 Open questions

A natural extension of our results would be to find the proportion of minimal
overlapping patterns in $\mathcal{F}_{n,k}$ ($\mathcal{C}_{=k[n-1]}$,
$\mathcal{ST}(n^{k})$) whose first $j$ columns is equal to some fixed
$P\in\mathcal{F}_{j,k}$ among all the elements of $\mathcal{F}_{n,k}$
($\mathcal{C}_{=k[n-1]}$, $\mathcal{ST}(n^{k})$) whose first $j$ columns is
equal to $P$. For example, in the simplest case, we would be interested in the
question of how many permutations in $S_{n}$ starting with $m$ are minimal
overlapping.

It is not hard to see that for a fixed $m$, as $n$ approaches to infinity,
there are at least $(3-e)(n-1)!$ permutations in $S_{n}$ starting with $m$ are
minimal overlapping. Similar to Theorem 9, we can show that the proportion of
minimal overlapping patterns in $S_{n}$ starting with $m$ converges as $n$
goes to infinity.

We have used Monte Carlo methods to estimate the limit of the proportion of
minimal overlapping permutations starting among all permutations that start
with $m$ for $m=1,2,3,4,5,6,7$. Our computations yielded the following
estimates: $0.392$, $0.384$, $0.375$, $0.368$, $0.365$, $0.361$ and $0.358$
respectively. Noting that the sequence is monotone decreasing, we ask whether
this is true in general. That is, if $1\leq a<b\leq\lceil\frac{n}{2}\rceil$,
is it the case that as $n$ approaches infinity, is the proportion of minimal
overlapping permutations in $S_{n}$ that start with $a$ among all the
permutations of $S_{n}$ that start with $a$ greater than the proportion of
minimal overlapping permutations in $S_{n}$ that start with $b$ among all the
permutations of $S_{n}$ that start with $b$?

## References

  * [1] M. Bóna, Non-overlapping permutation patterns, Pure Math. and Applications, 22 (2011), 99–105.
  * [2] V. Dotsenko and A. Khoroshkin, Shuffle algebras, homology, and consecutive pattern avoidance, Algebra Number Theory, 7 (2013), 673–700.
  * [3] A.S. Duane and J.B. Remmel, Minimal overlapping patterns in colored permutations, Electronic J. Combinatorics, 18(2) (2011), P25, 34 pgs.
  * [4] S. Elizalde, The most and the least avoided consecutive patterns, Proc. Lond. Math. Soc. 106 (2013), 957–979
  * [5] S. Elizalde, A survey of consecutive patterns in permutations, to appear in Recent Trends in Combinatorics, IMA, 2015.
  * [6] J. Harmse, Pattern matching in column-strict fillings of rectangular arrays. PhD thesis, UC San Diego, 2011.
  * [7] J. Harmse and J.B. Remmel, Patterns in column strict fillings of rectangular arrays, Pure Math. and Applications, 22 (2011), 131–171.
  * [8] A. Mendes and J.B. Remmel, Permutations and words counted by consecutive patterns, Advances Appl. Math., 37 4, (2006), 443-480.
  * [9] A. Mendes and J.B. Remmel, Counting with symmetric functions, Developments in Mathematics, Springer, 2015.
  * [10] B. Nakamura, Computational approaches to consecutive pattern avoidance in permutations, Pure Math. and Applications, 22 (2011), 253–268.
  * [11] R. Pan and J.B. Remmel, Generalized cluster method for consecutive pattern matching in restricted combinatorial objects, in preparation.
  * [12] R. Pan and J.B. Remmel, Counting alternating permutations with prefix and suffix, in preparation.
  * [13] J.B. Remmel, Consecutive up-down patterns in up-down permutations, Electronic J. Combinatorics, 21(3) (2014), #P3.2.
  * [14] R.P. Stanley, _Enumerative combinatorics, vol. 1_ , Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1997.
  * [15] R. P. Stanley, A survey of alternating permutations, in Combinatorics and graphs, AMS, Providence, RI, 2010, 165–196.


# An embedding technique in the study of word-representabiliy of graphs

Sumin Huang Email<EMAIL_ADDRESS>School of Mathematical Sciences, Xiamen
University, Xiamen 361005, P.R. China  Sergey Kitaev Email:
<EMAIL_ADDRESS>Department of Mathematics and Statistics,
University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, United Kingdom
Artem Pyatkin Email<EMAIL_ADDRESS>Sobolev Institute of Mathematics,
Koptyug ave, 4, Novosibirsk, 630090, Russia

###### Abstract

Word-representable graphs, which are the same as semi-transitively orientable
graphs, generalize several fundamental classes of graphs. In this paper we
propose a novel approach to study word-representability of graphs using a
technique of homomorphisms. As a proof of concept, we apply our method to show
word-representability of the simplified graph of overlapping permutations that
we introduce in this paper. For another application, we obtain results on
word-representability of certain subgraphs of simplified de Bruijn graphs that
were introduced recently by Petyuk and studied in the context of word-
representability.

Keywords: simplified de Bruijn type graph, word-representability, semi-
transitive orientation, homomorphism

##  1 Introduction

###  1.1 Simplified de Bruijn graph and its subgraphs

Let $A(k)=\\{0,1,\ldots,k-1\\}$ be a $k$-letter alphabet. For any integers
$n\geq 2$ and $m\geq 0$, let $A^{n}_{m}(k)$ be the following set of words over
$A(k)$:

$A^{n}_{m}(k)=\\{x_{1}x_{2}\ldots x_{n}:x_{i}\in A(k)\text{ and
}|x_{i}-x_{i+1}|\geq m\\}.$

In particular, $A^{n}_{0}(k)$ is the set of all words over $A(k)$ of length
$n$.

A de Bruijn graph $B(n,k)$ is a digraph with vertex set $A^{n}_{0}(k)$ having
an arc from $x_{1}x_{2}\ldots x_{n}$ to $y_{1}y_{2}\ldots y_{n}$ if and only
if $x_{i+1}=y_{i}$ for all $i\in\\{1,2,\ldots,n-1\\}$. De Bruijn graphs are a
useful tool in combinatorics on words [8] and they find applications in
several areas outside of mathematics, for example, in bioinformatics [10].

The notion of the simplified de Bruijn graph is introduced in [9], and we
believe it to be a very natural and potentially useful tool in graph theory
and its various applications. The simplified de Bruijn graph $S(n,k)$ is the
simple graph obtained from $B(n,k)$ by removing orientations and loops and
replacing multiple edges between a pair of vertices by a single edge. Denote
by $S_{m}(n,k)$ the induced subgraphs of $S(n,k)$ with vertex set
$A^{n}_{m}(k)$. See Figure 1 for examples of just introduced objects.

111011110101010001100000 |  | 111011110101010001100000 |  | 010101
---|---|---|---|---
Figure 1: From left to right: the graphs $B(3,2)$, $S(3,2)$ and $S_{1}(3,2)$.

###  1.2 Simplified graphs of overlapping permutations

The graph of overlapping permutations $P(n)$ is defined in a way analogous to
the de Bruijn graph $B(n,k)$. However, here we require that the head and tail
of adjacent permutations have their letters appear in the same relative order.
Formally, the vertex set of $P(n)$ is the set of all $n!$ permutations of
$\\{1,2,\ldots,n\\}$, and there is an arc from a permutation $x_{1}x_{2}\ldots
x_{n}$ to a permutation $y_{1}y_{2}\ldots y_{n}$ if and only if, for each
$2\leq i<j\leq n$, either both $x_{i}<x_{j}$ and $y_{i-1}<y_{j-1}$ hold or
both $x_{i}>x_{j}$ and $y_{i-1}>y_{j-1}$ hold. The graph $P(n)$ is
instrumental in solving various problems related to permutations, for example,
in constructing a universal cycle for permutations [1].

The simplified graph of overlapping permutations $SP(n)$ is obtained from
$P(n)$ by removing orientations and loops and replacing multiple edges between
a pair of vertices by a single edge. To our best knowledge, the notion of the
simplified graph of overlapping permutations is introduced in this paper for
the first time. See Figure 2 for examples of just introduced objects.

123213132312231321 |  | 123213132312231321
---|---|---
Figure 2: From left to right: the graphs $P(3)$ and $SP(3)$.

###  1.3 Word-representability of graphs

The literature contains a substantial body of research papers focused on the
theory of word-representable graphs, as evidenced by references [4, 5, 6] and
related works. These graphs are of interest due to their connections to
algebra, graph theory, computer science, combinatorics on words, and
scheduling [5]. Notably, word-representable graphs extend the scope of several
important graph classes, including circle graphs, $3$-colorable graphs, and
comparability graphs. The ability to represent simplified de Bruijn graphs and
simplified graphs of overlapping permutations using words could expand the
range of potential applications for these graphs. This provides motivation for
studying these graphs from the perspective of word-representability.

Two letters $x$ and $y$ alternate in a word $w$ if after deleting in $w$ all
letters but the copies of $x$ and $y$ we either obtain a word $xyxy\cdots$ or
a word $yxyx\cdots$ (of even or odd length). A graph $G=(V,E)$ is word-
representable if and only if there exists a word $w$ over the alphabet $V$
such that letters $x$ and $y$, $x\neq y$, alternate in $w$ if and only if
$xy\in E$. The unique minimum (by the number of vertices) non-word-
representable graph on 6 vertices is the wheel graph $W_{5}$, while there are
25 non-word-representable graphs on 7 vertices [5].

An orientation of a graph is semi-transitive if it is acyclic, and for any
directed path $v_{0}\rightarrow v_{1}\rightarrow\cdots\rightarrow v_{k}$
either there is no arc from $v_{0}$ to $v_{k}$, or $v_{i}\rightarrow v_{j}$ is
an arc for all $0\leq i<j\leq k$. An induced subgraph on vertices
$\\{v_{0},v_{1},\ldots,v_{k}\\}$ of an oriented graph is a shortcut if it is
acyclic, non-transitive, and contains both the directed path $v_{0}\rightarrow
v_{1}\rightarrow\cdots\rightarrow v_{k}$ and the arc $v_{0}\rightarrow v_{k}$,
that is called the shortcutting edge. A semi-transitive orientation can then
be alternatively defined as an acyclic shortcut-free orientation. A
fundamental result in the area of word-representable graphs is the following
theorem.

######  Theorem 1 ([2]).

A graph is word-representable if and only if it admits a semi-transitive
orientation.

The following simple corollary of Theorem 1 is also instrumental for us.

######  Theorem 2 ([2]).

Any $3$-colorable graph is word-representable.

Directly related to our studies is the following theorem by Petyuk [9].

######  Theorem 3 ([9]).

For positive integers $n$ and $k$ with $k\geq 3$,

  * (i)

$S(n,2)=S_{0}(n,2)$ is word-representable;

  * (ii)

$S(2,k)=S_{0}(2,k)$ is non-word-representable;

  * (iii)

$S(3,k)=S_{0}(3,k)$ is non-word-representable.

We will provide a sketch of the proof of Theorem 3(i) in Section 2 in order to
introduce our notation and color classes that will be used in this paper.

###  1.4 Results in this paper

In this paper, we continue the research on word-representability of the
simplified de Bruijn graph initiated in [9], and extend the studies to the
simplified graph of overlapping permutations. More specifically, the following
conjecture is stated in [9]:

######  Conjecture 1.

$S(n,k)$ is non-word-representable for $n\geq 4$ and $k\geq 3$.

Towards settling this conjecture it is natural to consider induced subgraphs
of $S(n,k)$, such as $S_{m}(n,k)$, that have simpler structure but may still
be non-word-representable. So, if $S_{m}(n,k^{\prime})$ is non-word-
representable for some $m,n,k^{\prime}$ then $S_{m}(n,k)$ and hence $S(n,k)$,
are non-word-representable for every $k\geq k^{\prime}$.

In order to study word-representability of $S_{m}(n,k)$, we use an embedding
technique based on the well-known notion of graph homomorphisms (see, e.g.
[3]). Let $G$ and $H$ be two graphs. Assume that there exists a mapping $f$
from $V(G)$ to $V(H)$ preserving adjacency (i.e. if $uv\in E(G)$ then
$f(u)f(v)\in E(H)$). Then such a mapping $f$ is called a homomorphism (or just
an embedding) from $G$ to $H$. For instance, for a $k$-colorable graph $G$,
its $k$-coloring induces a homomorphism from $G$ to $K_{k}$ (the complete
graph of order $k$).

We found out that homomorphisms can be useful for finding potential semi-
transitive orientations of $G$. To the best of our knowledge, this is the
first use of the homomorphisms in the area of word-representable graphs
(although the proof of Theorem 2 in [2] may be considered as a simplest
application of this technique). Informally, the basic steps of the embedding
technique (that will be indicated explicitly in the proofs of Theorem 4 and
Lemmas 5–8) are as follows:

Step 1. Given a graph $G$, find a word-representable graph $H$ such that there
exists a homomorphism $f$ from $G$ to $H$. Based on a fixed acyclic
orientation of $H$, orient all edges in $G$ as in $H$ (i.e. $u\rightarrow v$
in $G$ if $f(u)\rightarrow f(v)$ in the oriented $H$). Clearly, we obtain an
acyclic orientation of $G$.

Step 2. Find all directed paths $f(v_{0})\rightarrow
f(v_{1})\rightarrow\cdots\rightarrow f(v_{k})$, $k\geq 3$, with
$f(v_{0})\rightarrow f(v_{k})$ in the oriented $H$. We call such paths
shortcutting paths. If no shortcutting paths exist in $H$, then the
orientation of $G$ is semi-transitive, and we terminate the procedure. For
instance, Theorem 2 can be proved by embedding a 3-colorable graph into a
triangle and orienting the triangle transitively.

Step 3. Analyze each shortcutting path found in Step 2. If none of them
induces a shortcut in $G$ then we obtain a desired semi-transitive orientation
of $G$.

Remark. We can find all directed paths in Step 2, for instance, in the
following way. Let $M$ be the adjacency matrix of $H$, i.e. $a_{ij}=1$ if
there is an arc from $v_{i}$ to $v_{j}$ in $H$ and $a_{ij}=0$ otherwise. Then
$H$ contains a shortcutting path of length $p$ from $v_{i}$ to $v_{j}$ with
the shortcutting edge $v_{i}v_{j}$ if and only if both matrices $M$ and its
$p$-th power $M^{p}$ have positive elements in position $(i,j)$.

Of course, Step 3 is not always applicable since there can be a homomorphism
from a non-word-representable graph to a word-representable graph (for
instance, a homomorphism from $W_{5}$ to $K_{4}$). However, sometimes the
approach works providing elegant proofs of word-representability for quite
complicated graphs.

As an application of the embedding technique, we will prove the following two
theorems.

######  Theorem 4.

For any positive integer $n$, $SP(n)$ is word-representable.

Theorem 4 is proved in Section 3. In our proof of Theorem 4, the oriented $H$
found in Step 1 contains no shortcutting paths.

######  Theorem 5.

Let $m,n,k$ be positive integers.

  * (i)

For $n=2,3,4$ and $k\leq(n+1)m$, $S_{m}(n,k)$ is word-representable. Moreover,
$S_{m}(2,k)$ is non-word-representable for $k\geq 3m+1$.

  * (ii)

For $n\geq 5$ and $k\leq 2mn$, $S_{m}(n,k)$ is word-representable.

Theorem 5 is proved in Section 4 and in Appendix.

In general, it is desirable that an orientation of $H$ fixed in Step 1 is
semi-transitive, which is the case in the proofs of Theorem 4 (mentioned
above) and Lemmas 5, 6 and 8 (related to Theorem 5(ii)). However, this is not
a necessary condition as is demonstrated by us in the proof of Lemma 7 in
Section 4.4 (related to Theorem 5(ii)).

##  2 Preliminaries

In this section we provide simple (known) statements that are required for
deriving our further results. The following lemma reveals relations among
$S_{m}(n,k)$ for various $m$ and $k$.

######  Lemma 1.

For any positive integers $m,n,k$ with $k\geq 2$, we have

  * (i)

$S_{m}(n,k)$ is isomorphic to a subgraph of $S_{m}(n,k+1)$;

  * (ii)

$S_{1}(n,k)$ is isomorphic to a subgraph of $S_{m}(n,(k-1)m+1)$.

###### Proof.

It is clear that (i) holds. To prove (ii) consider the following embedding of
$S_{1}(n,k)$ into $S_{m}(n,(k-1)m+1)$. For any vertex $\omega=x_{1}x_{2}\ldots
x_{n}$ in $S_{1}(n,k)$, let $f(\omega)$ be the word of length $n$ obtained by
multiplying each letter of $\omega$ by $m$, that is,
$f(\omega)=(mx_{1})(mx_{2})\ldots(mx_{n}).$ Since $x_{i}\leq k-1$, $f(\omega)$
is a vertex in $S_{m}(n,(k-1)m+1)$. Also, $\omega\omega^{\prime}\in
E(S_{1}(n,k))$ if and only if $f(\omega)f(\omega^{\prime})\in
E(S_{m}(n,(k-1)m+1))$, which implies that (ii) holds. ∎

We also need a proof of $3$-colorability of $S_{0}(n,2)$ that was found by
Petyuk in [9]. Here we rewrite the original proof in a more convenient
notation that will be of use for us later on.

A $3$-colorability of $S_{0}(n,2)$. We first introduce the following types of
words:

  * $\bullet$

$e_{1}$ (resp., $e_{0})$ represents words consisting of a positive even number
of 1s (resp., 0s) only;

  * $\bullet$

$o_{1}$ (resp., $o_{0})$ represents words consisting of an odd number of 1s
(resp., 0s) only;

  * $\bullet$

$a_{1}$ (resp., $a_{0})$ represents non-empty words beginning with 1 (resp.,
0);

  * $\bullet$

$b_{1}$ (resp., $b_{0})$ represents either words beginning with 1 (resp., 0)
or an empty word.

Then the vertices in $S_{0}(n,2)$ may be represented (in different ways) using
this notation. The following observation is easy to verify.

######  Observation 1.

Let $w$ be a word representing a vertex in $S_{0}(n,2)$ and let the word
$w^{\prime}$ be obtained from $w$ by removing the first letter. Then

  * (i)

if $w$ has the form $e_{1}b_{0}$ (resp., $e_{0}b_{1}$) then $w^{\prime}$ has
the form $o_{1}b_{0}$ (resp., $o_{0}b_{1}$);

  * (ii)

if $w$ has the form $o_{1}b_{0}$ (resp., $o_{0}b_{1}$) then $w^{\prime}$ has
either the form $e_{1}b_{0}$ (resp., $e_{0}b_{1}$) or the form $b_{0}$ (resp.,
$b_{1}$).

Consider two cases.

Case 1. $n$ is even. In this case, each vertex of $S_{0}(n,2)$ can be
represented by exactly one of
$\\{e_{0}b_{1},e_{1}b_{0},o_{1}e_{0}a_{1},o_{1}o_{0}b_{1},o_{0}e_{1}a_{0},o_{0}o_{1}b_{0}\\}$,
which is called the form of this vertex. Then we can color the vertices in
$S_{0}(n,2)$ based on their forms as follows:

$\displaystyle\text{\bf Red: }e_{0}b_{1},e_{1}b_{0};$ $\displaystyle\text{\bf
Blue: }o_{1}e_{0}a_{1},o_{1}o_{0}b_{1};$ $\displaystyle\text{\bf Green:
}o_{0}e_{1}a_{0},o_{0}o_{1}b_{0}.$

Case 2. $n$ is odd. Similarly, we color the vertices in $S_{0}(n,2)$ based on
their forms as follows:

$\displaystyle\text{\bf Red: }e_{0}a_{1},e_{1}a_{0};$ $\displaystyle\text{\bf
Blue: }o_{1},o_{1}o_{0}a_{1},o_{1}e_{0}b_{1};$ $\displaystyle\text{\bf Green:
}o_{0},o_{0}o_{1}a_{0},o_{0}e_{1}b_{0}.$

Using Observation 1, it is not difficult to verify that in both cases there
are no monochromatic edges (note that the vertices of the forms
$e_{1},e_{0},o_{1},$ and $o_{0}$ are unique and $S_{0}(n,2)$ has no loops),
and thus we obtain a proper 3-coloring of $S_{0}(n,2)$.

##  3 Word-representability of $SP(n)$

In this section, we give a proof of Theorem 4 using the embedding technique.
Note that $SP(1)$ is a single vertex while $SP(2)$ is a single edge. Both of
these graphs are word-representable. Next, we consider the case of $n\geq 3$.

Step 1. Let $H=S_{0}(n-1,2)$. For any vertex $\omega=x_{1}x_{2}\ldots x_{n}$
in $SP(n)$, let $\tau(\omega)=y_{1}\ldots y_{n-1}$ be such that $y_{i}=0$ if
$x_{i}>x_{i+1}$ and $y_{i}=1$ otherwise. Then $\tau(w)$ is a mapping from
$V(SP(n))$ to $V(S_{0}(n-1,2))$. Let us show that $\tau$ is a homomorphism.
Assume that $\omega\omega^{\prime}$ is an edge in $E(SP(n))$, where
$\omega=x_{1}x_{2}\ldots x_{n}$,
$\omega^{\prime}=x^{\prime}_{1}x^{\prime}_{2}\ldots x^{\prime}_{n}$ and
$\omega\rightarrow\omega^{\prime}$ is an arc in $P(n)$.

If $\tau(\omega)=y_{1}y_{2}\ldots y_{n-1}$, then
$\tau(\omega^{\prime})=y_{2}\ldots y_{n-1}y_{n}$ by definition of $\tau$.
Thus, if $\tau(\omega)\neq\tau(\omega^{\prime})$, then there exists an edge
between $\tau(\omega)$ and $\tau(\omega^{\prime})$. However,
$\tau(\omega)=\tau(\omega^{\prime})$ implies that
$y_{1}=\cdots=y_{n}\in\\{0,1\\}$ so that
$\omega=\omega^{\prime}\in\\{123\ldots n,\ n(n-1)(n-2)\ldots 1\\}$, which is a
contradiction with $\omega\neq\omega^{\prime}$. So $\tau(\omega)$ is adjacent
to $\tau(\omega^{\prime})$ in $S_{0}(n-1,2)$, as desired.

Let $R\cup B\cup G$ be a 3-coloring partition of $V(S_{0}(n-1,2))$. Orient
$S_{0}(n-1,2)$ so that any vertex in $R$ is a source and any vertex in $G$ is
a sink.

Step 2. Orient all edges in $SP(n)$ as in $S_{0}(n-1,2)$ (i.e., $u\rightarrow
v$ in $SP(n)$ if $\tau(u)\rightarrow\tau(v)$ in the oriented $S_{0}(n-1,2)$).

Since there are no shortcutting paths in the oriented $S_{0}(n-1,2)$, we
obtain a desired semi-transitive orientation of $SP(n)$ (Step 3 is not
needed). By Theorem 1, $SP(n)$ is word-representable.

##  4 Word-representability of $S_{m}(n,k)$

###  4.1 The case of $n=2$

######  Lemma 2.

If $m\geq 1$ and $k\leq 3m$ then $S_{m}(2,k)$ is word-representable.

###### Proof.

For all pairs of adjacent vertices $x_{1}x_{2}$ and $y_{1}y_{2}$ in
$S_{m}(2,k)$, orient the edge by the lexicographical order (i.e. we have
$x_{1}x_{2}\rightarrow y_{1}y_{2}$ if $x_{1}x_{2}$ is lexicographically
smaller than $y_{1}y_{2}$). It is clear that this orientation is acyclic. We
claim that the oriented graph contains no directed path of length 3, which
implies that there are no shortcuts in this orientation and thus $S_{m}(2,k)$
is word-representable.

Indeed, suppose that there is a directed edge from $x_{1}x_{2}$ to
$y_{1}y_{2}$ in $S_{m}(2,k)$. Then $x_{1}x_{2}$ is lexicographically smaller
than $y_{1}y_{2}$, i.e. $y_{1}\geq x_{1}$. Moreover, either $x_{2}=y_{1}$ or
$x_{1}=y_{2}$. If $x_{2}=y_{1}$ then $x_{2}\geq x_{1}$. By definition of
$S_{m}(2,k)$, we have $x_{2}-x_{1}\geq m$, and so, $y_{1}\geq x_{1}+m$. If
$y_{2}=x_{1}$ then, by a similar argument, $y_{1}\geq y_{2}+m=x_{1}+m$. Hence,
in both cases, $y_{1}\geq x_{1}+m$. For
$\\{\omega_{1},\omega_{2},\omega_{3},\omega_{4}\\}\subseteq V(S_{m}(2,k))$,
suppose that there is a directed path
$\omega_{1}\rightarrow\omega_{2}\rightarrow\omega_{3}\rightarrow\omega_{4}$ of
length 3. Then, the first letter of $\omega_{4}$ is at least $3m$. However,
since $k\leq 3m$, any letter in $A$ is at most $3m-1$, a contradiction. So
there are no directed paths of length 3, as desired. ∎

To finish the study of the case of $n=2$, it remains to prove that
$S_{m}(2,k)$ is non-word-representable for $k\geq 3m+1$. By Lemma 1(i), it is
sufficient to show that $S_{m}(2,3m+1)$ is non-word-representable, and by
Lemma 1(ii), our aim is to prove that $S_{1}(2,4)$ is non-word-representable.
Since this proof is a tedious case-analysis requiring certain special
encodings, it is moved to Appendix.

###  4.2 A bipartite subgraph of $S_{m}(n,k)$

In this section, we introduce some notations necessary for our proofs in the
rest of the paper. Let

$A^{n}_{m}(k,<):=\\{x_{1}x_{2}\ldots x_{n}:x_{i}\leq x_{i+1}-m,\ 1\leq i\leq
n-1\\}$

and

$A^{n}_{m}(k,>):=\\{x_{1}x_{2}\ldots x_{n}:x_{i}\geq x_{i+1}+m,\ 1\leq i\leq
n-1\\}$

be, respectively, the sets of increasing and decreasing words in
$A^{n}_{m}(k)$. We denote the subgraphs of $S_{m}(n,k)$ induced by
$A^{n}_{m}(k,<)$ and $A^{n}_{m}(k,>)$ by $S^{<}_{m}(n,k)$ and
$S^{>}_{m}(n,k)$, respectively. Then we claim that both $S^{<}_{m}(n,k)$ and
$S^{>}_{m}(n,k)$ are triangle-free. Indeed, suppose
$\omega_{1}\omega_{2}\omega_{3}$ is a triangle in $S^{<}_{m}(n,k)$. Let
$\omega_{1}=x_{1}x_{2}\ldots x_{n}$ with $x_{i}\leq x_{i+1}-m$. Since
$\omega_{2}$ is adjacent to $\omega_{3}$, their first letters must be
different. Because $\omega_{1}\omega_{2}$ and $\omega_{1}\omega_{3}$ are edges
in $S^{<}_{m}(n,k)$, $\\{\omega_{2},\omega_{3}\\}=\\{x_{0}x_{1}\ldots
x_{n-1},x_{2}\ldots x_{n}x_{n+1}\\}$ for some $x_{0}\leq x_{1}-m$ and
$x_{n+1}\geq x_{n}+m$, which is a contradiction with $\omega_{2}\omega_{3}\in
E(S^{<}_{m}(n,k))$.

######  Lemma 3.

$S^{<}_{m}(2,4m)$ is bipartite.

###### Proof.

Suppose that $C$ is a shortest odd cycle in $S^{<}_{m}(2,4m)$. Then $C$ is
chord-free. Orient the edges in $C$ in the same way as they are oriented in de
Bruijn graph $B(2,4m)$ and denote the obtained directed graph by
$\mathop{C}\limits^{\rightarrow}$. Since $k=4m$, the longest directed path in
$B(2,4m)$ (and hence in $\mathop{C}\limits^{\rightarrow}$) is of length at
most 2.

If there are no directed paths of length 2 in
$\mathop{C}\limits^{\rightarrow}$, then $\mathop{C}\limits^{\rightarrow}$ is
clearly an even cycle, a contradiction.

Suppose that $xy\rightarrow yz\rightarrow zw$ is a directed path of length 2
in $\mathop{C}\limits^{\rightarrow}$. Then $xy$ and $zw$ are a source and a
sink in $\mathop{C}\limits^{\rightarrow}$, respectively. If the other
neighbour of $xy$ in $C$, say $ya$, is a sink, then $C$ contains the following
path (arrows indicate the directions of the edges in
$\mathop{C}\limits^{\rightarrow}$):

$by\rightarrow ya\leftarrow xy\rightarrow yz\rightarrow zw.$

However, in this case, there is a chord $by\rightarrow yz$ in $C$, which is a
contradiction. Thus, $xy$, or generally the head of any directed path of
length 2, is not adjacent to any sink. Similarly, the tail of any directed
path of length 2 is not adjacent to any source. This implies that
$\mathop{C}\limits^{\rightarrow}$ comprises of a series of alternate directed
paths of length 2. Then $C$ is of even length, which is a contradiction.

Therefore $S^{<}_{m}(2,4m)$ is bipartite, as desired. ∎

Assume that $A$ is a subset of $A_{m}^{n}(k)$. For any word $\omega$ in
$A^{n-1}_{m}(k)$, the cluster with respect to $\omega$ is the subset of $A$
comprised of all words that begin or end with $\omega$. A cluster is non-
trivial if it contains at least two vertices. The cluster graph
$\mathcal{C}(A)$ of $A$ is the graph whose vertex set is the set of all non-
trivial clusters of $A$. There is an edge between two clusters in
$\mathcal{C}(A)$ if and only if they have a common vertex in $A$. Note that
$\mathcal{C}(A)$ is a subgraph of $S_{m}(n-1,k)$ provided $n\geq 2$. For
example, if $A=\\{0123,1234,2123,2345\\}$, then the cluster with respect to
$123$ is $\\{0123,1234,2123\\}$, while the cluster with respect to $012$ is
$\\{0123\\}$, and the cluster with respect to $124$ is the empty set. In this
case, $\mathcal{C}(A)$ is a single edge with vertex set $\\{123,234\\}$.

######  Lemma 4.

If $n\geq 2$ and $k\leq 2mn$ then $S^{<}_{m}(n,k)$ is bipartite.

###### Proof.

Since $S^{<}_{m}(n,k)$ is a subgraph of $S^{<}_{m}(n,k+1)$, it is sufficient
to prove that $S^{<}_{m}(n,2mn)$ is bipartite. We apply the induction on $n$.
By Lemma 3, $S^{<}_{m}(n,2mn)$ is bipartite for $n=2$. Assume that
$S^{<}_{m}(n,2mn)$ is bipartite. Now we consider the graph
$S^{<}_{m}(n+1,2m(n+1))$.

Suppose that $C$ is a shortest (and hence chord-free) odd cycle in
$S^{<}_{m}(n+1,2m(n+1))$ and the length of $C$ is $2t+1$. Direct the edges in
$C$ in the same way as they are oriented in de Bruijn graph $B(n+1,2m(n+1))$
and obtain the directed graph $\mathop{C}\limits^{\rightarrow}$. Let
$\omega_{1}^{\prime}\omega_{1}\omega_{2}\omega_{2}^{\prime}$ be four
consecutive vertices in $C$. Without loss of generality, assume that
$\omega_{2}$ starts with $\omega$ and ends with $\omega^{\prime}$, where
$\omega$ and $\omega^{\prime}$ are both in $A^{n}_{m}(k,<)$. Based on the
orientation of $\mathop{C}\limits^{\rightarrow}$, we have the following
observations.

  * $\bullet$

At most one of $\\{\omega_{1},\omega_{2}\\}$ is a sink or a source. Otherwise,
without loss of generality, suppose that $\omega_{1}$ is a sink and
$\omega_{2}$ is a source. Then both $\omega_{1}$ and $\omega_{2}^{\prime}$
begin with $\omega^{\prime}$, while $\omega_{1}^{\prime}$ ends with
$\omega^{\prime}$. This implies that $\omega_{1}^{\prime}$ is adjacent to
$\omega_{2}^{\prime}$ in $S^{<}_{m}(n+1,2m(n+1))$, which is a contradiction.

  * $\bullet$

If $\omega_{2}$ is a sink then
$\\{\omega_{1},\omega_{2},\omega_{2}^{\prime}\\}$ in $C$ is the cluster with
respect to $\omega$.

  * $\bullet$

If $\omega_{2}$ is a source then
$\\{\omega_{1},\omega_{2},\omega_{2}^{\prime}\\}$ is the cluster with respect
to $\omega^{\prime}$.

  * $\bullet$

If none of $\omega_{1}$ and $\omega_{2}$ is a sink or a source and
$\omega_{1}\rightarrow\omega_{2}$ then $\\{\omega_{1},\omega_{2}\\}$ is the
cluster with respect to $\omega$.

  * $\bullet$

If none of $\omega_{1}$ and $\omega_{2}$ is a sink or a source and
$\omega_{2}\rightarrow\omega_{1}$ then $\\{\omega_{1},\omega_{2}\\}$ is the
cluster with respect to $\omega^{\prime}$.

Let $s$ be the total number of sinks and sources in
$\mathop{C}\limits^{\rightarrow}$. Then $s$ must be even. Combining with the
above observations, the cluster derived from consecutive vertices in $C$ has
size 3 if it contains a sink or a source and has size 2 otherwise. Thus, the
cluster graph $\mathcal{C}(V(C))$ also contains a cycle $C^{\prime}$ of length
$2t+1-s$ (recall that the length of $C$ is $2t+1$), which is still odd. We
give an illustration of $\mathop{C}\limits^{\rightarrow}$ and
$\mathcal{C}(V(C))$ for the graph $S_{1}^{<}(4,8)$ in Figure 3. In this
figure, since $t=7$ and $s=4$, the length of $C^{\prime}$ is $11$.

Now, let $x$ be the smallest letter occurring in any word in $V(C)$. For any
letter $x_{0}\in\\{x,x+1,\ldots,x+m-1\\}$, if $\omega=x_{0}x_{1}\ldots x_{n}$
is a word in $V(C)$ beginning with $x_{0}$, then $x_{1}\geq x_{0}+m\geq x+m$,
and $\omega$ must be a source in $\mathop{C}\limits^{\rightarrow}$. In this
case, $\omega$ is in the cluster with respect to $x_{1}\ldots x_{n}$, which
does not contain $x_{0}$. Thus, no word in $C^{\prime}$ contains any letter in
$\\{x,x+1,\ldots,x+m-1\\}$. Similarly, no word in $C^{\prime}$ contains any
letter in $\\{y,y-1,\ldots,y-m+1\\}$, where $y$ is the largest letter in
$V(C)$. Then, the alphabet comprised of all letters occurring in
$V(C^{\prime})$ has size at most $2m(n+1)-2m=2mn$.

Note that the cluster graph $\mathcal{C}(V(C))$ is a subgraph of
$S^{<}_{m}(n,2m(n+1))$. Then, $C^{\prime}$ is isomorphic to a subgraph of
$S^{<}_{m}(n,2mn)$, which is a contradiction to the induction hypothesis.
Hence, any cycle in $S^{<}_{m}(n+1,2m(n+1))$ is an even cycle and
$S^{<}_{m}(n+1,2m(n+1))$ is bipartite, as desired. ∎

Figure 3: The oriented cycle $\mathop{C}\limits^{\rightarrow}$ and the cluster
graph $\mathcal{C}(V(C))$ in $S_{1}^{<}(4,8)$.

Remark. In Lemmas 3 and 4, the bounds on $k$ are sharp because
$S^{<}_{1}(2,5)$ contains an odd cycle

$01-12-23-34-13-01$

and $S^{<}_{1}(3,7)$ contains an odd cycle

$012-123-234-345-456-245-124-012.$

###  4.3 Word-representability of $S_{m}(n,k)$ for odd $n\geq 3$

First, we show that Theorem 5(ii) holds for every odd $n\geq 5$.

######  Lemma 5.

For any odd $n\geq 5$ and $k\leq 2mn$, $S_{m}(n,k)$ is word-representable.

###### Proof.

By Lemma 4, $S^{<}_{m}(n,k)$ is bipartite, the parts of which are denoted by
$R_{1}$ and $R_{2}$. Let $\overline{R}_{1}\cup\overline{R}_{2}$ be a partition
of $A^{n}_{m}(k,>)$, where

$\overline{R}_{i}=\\{x_{n}x_{n-1}\ldots x_{1}\ |\ x_{1}x_{2}\ldots x_{n}\in
R_{i}\\}\text{ for }i=1,2.$

Then $S^{>}_{m}(n,k)$ is also bipartite with parts
$\overline{R}_{1}\cup\overline{R}_{2}$.

For each vertex $\omega=x_{1}x_{2}\ldots x_{n}$ in $S_{m}(n,k)$, put
$\tau(\omega)=y_{1}\ldots y_{n-1}$ where $y_{i}=0$ if $x_{i}>x_{i+1}$ and
$y_{i}=1$ otherwise. Then $\tau$ is a mapping from $S_{m}(n,k)$ to
$S_{0}(n-1,2)$. Also, recall that $S_{0}(n-1,2)$ is 3-colorable, whose
vertices can be colored based on its forms introduced in Section 2:

$\displaystyle\text{\bf Red: }e_{0},e_{1},e_{0}a_{1},e_{1}a_{0};$
$\displaystyle\text{\bf Blue: }o_{1}e_{0}a_{1},o_{1}o_{0}b_{1};$
$\displaystyle\text{\bf Green: }o_{0}e_{1}a_{0},o_{0}o_{1}b_{0}.$

Note that a word of the form $e_{0}b_{1}$ (resp. $e_{1}b_{0}$) can be either
$e_{0}$ or $e_{0}a_{1}$ (resp. $e_{1}$ or $e_{1}a_{0}$). Here we separate
these two cases. By the definition of $A^{n}_{m}(k,<)$ and $A^{n}_{m}(k,>)$,
the form of $\tau(\omega)$ is $e_{1}$ (resp., $e_{0}$) if and only if $\omega$
is a vertex in $R_{1}\cup R_{2}$ (resp.,
$\overline{R}_{1}\cup\overline{R}_{2}$).

$R^{\prime}$$B$$\overline{R}_{2}$$R_{2}$$G$ Figure 4: A graph $H$ and its
orientation.

Step 1. Let $H$ be the underlying (undirected) graph with vertex set
$\\{R_{2},\overline{R}_{2},R^{\prime},B,G\\}$ in Figure 4. Consider the
following mapping $f$ from $S_{m}(n,k)$ to $H$.

  * $\bullet$

If $\omega\in R_{2}$ then $f(\omega)=R_{2}$.

  * $\bullet$

If $\omega\in\overline{R}_{2}$ then $f(\omega)=\overline{R}_{2}$.

  * $\bullet$

If $\omega\in R_{1}\cup\overline{R}_{1}$ or the form of $\tau(\omega)$ is one
of $\\{e_{0}a_{1},e_{1}a_{0}\\}$ then $f(\omega)=R^{\prime}$.

  * $\bullet$

If the form of $\tau(\omega)$ is one of
$\\{o_{1}e_{0}a_{1},o_{1}o_{0}b_{1}\\}$ then $f(\omega)=B$.

  * $\bullet$

If the form of $\tau(\omega)$ is one of
$\\{o_{0}e_{1}a_{0},o_{0}o_{1}b_{0}\\}$ then $f(\omega)=G$.

Clearly, all sets of vertices of $S_{m}(n,k)$ mapped into the same vertex of
$H$ are independent. Since there are no edges between $R_{2}$ and
$\overline{R}_{2}$, $f$ is a homomorphism from $S_{m}(n,k)$ to $H$. Then
direct $H$ as in Figure 4.

Step 2. Note that the orientation of $H$ is acyclic and contains only two
shortcutting paths of length at least 3:

$\displaystyle R^{\prime}\rightarrow B\rightarrow R_{2}\rightarrow G;$
$\displaystyle R^{\prime}\rightarrow B\rightarrow\overline{R}_{2}\rightarrow
G.$

Now direct each edge in $S_{m}(n,k)$ as in $H$ (i.e. $u\rightarrow v$ in
$S_{m}(n,k)$ if $f(u)\rightarrow f(v)$ in $H$). It remains to prove that the
orientation of $S_{m}(n,k)$ contains no shortcuts and hence it is semi-
transitive.

Step 3. Suppose that there exists a directed path
$\omega_{R^{\prime}}\rightarrow\omega_{B}\rightarrow\omega_{R_{2}}\rightarrow\omega_{G}$
with $f(\omega_{X})=X$ for all $X\in\\{R^{\prime},B,R_{2},G\\}$, and the path
introduces a potential shortcutting edge, that is,
$\omega_{R^{\prime}}\rightarrow\omega_{G}$.

Let $\omega_{R_{2}}=x_{1}x_{2}\ldots x_{n}$ with $x_{i}\leq x_{i+1}-m$. Since
$n$ is odd and the forms of $\tau(\omega_{G})$ and $\tau(\omega_{B})$ start
with $o_{0}$ and $o_{1}$ respectively, we have $\omega_{B}=x_{2}\ldots
x_{n-1}x_{n}y$ and $\omega_{G}=zx_{1}x_{2}\ldots x_{n-1}$, where $y\leq
x_{n}-m$ and $z\geq x_{1}+m$.

Since $\omega_{R^{\prime}}$ is adjacent to $\omega_{G}$, we have either
$\omega_{R^{\prime}}=wzx_{1}\ldots x_{n-2}$ or
$\omega_{R^{\prime}}=x_{1}\ldots x_{n-1}w$ for some $w$. Since $n\geq 5$, in
the former case the form of $\tau(\omega_{R^{\prime}})$ is $e_{0}e_{1}$, or
$o_{1}o_{0}e_{1}$, while in the latter case, it is either $o_{1}o_{0}$ or
$e_{1}$. In either case, the form of $\tau(\omega_{R^{\prime}})$ belongs to
the set $F_{1}=\\{o_{1}o_{0},o_{1}o_{0}e_{1},e_{0}e_{1},e_{1}\\}$. On the
other hand, $\omega_{R^{\prime}}$ is adjacent to $\omega_{B}$, and hence
either $\omega_{R^{\prime}}=ux_{2}\ldots x_{n}$ or
$\omega_{R^{\prime}}=x_{3}\ldots x_{n}yu$ for some $u$. In the former case,
the form of $\tau(\omega_{R^{\prime}})$ is either $e_{1}$ or $o_{0}o_{1}$,
while in the latter case it may be $e_{1}e_{0}$ or $e_{1}o_{0}o_{1}$. Then,
the form of $\tau(\omega_{R^{\prime}})$ belongs to the set
$F_{2}=\\{o_{0}o_{1},e_{1}e_{0},e_{1}o_{0}o_{1},e_{1}\\}$. Clearly, $F_{1}\cap
F_{2}=\\{e_{1}\\}$. But if the form of $f(\omega_{R^{\prime}})$ is $e_{1}$,
then $\omega_{R^{\prime}}=x_{1}\ldots x_{n-1}w=ux_{2}\ldots
x_{n}=x_{1}x_{2}\ldots x_{n}=\omega_{R_{2}}$, a contradiction.

So, there exists no shortcut induced by
$\\{\omega_{R^{\prime}},\omega_{B},\omega_{R_{2}},\omega_{G}\\}$. Similarly,
there are no shortcuts induced by
$\\{\omega_{R^{\prime}},\omega_{B},\omega_{\overline{R}_{2}},\omega_{G}\\}$.
Hence, the orientation of $S_{m}(n,k)$ is shortcut-free and therefore it is
semi-transitive. By Theorem 1, $S_{m}(n,k)$ is word-representable for all odd
$n\geq 5$ and $k\leq 2mn$. ∎

We prove the remaining case of $n=3$ in the following lemma.

######  Lemma 6.

For $k\leq 4m$, $S_{m}(3,k)$ is word-representable.

###### Proof.

By Lemma 1, it is sufficient to show that $S_{m}(3,4m)$ is word-representable.
Let $A$, $B$ and $C$ be the following subsets of $A^{3}_{m}(4m,<)$:

$\displaystyle A$ $\displaystyle:=\\{x_{1}x_{2}x_{3}\in A^{3}_{m}(4m,<):0\leq
x_{1}\leq m-1\text{ and }3m\leq x_{3}\leq 4m-1\\};$ $\displaystyle B$
$\displaystyle:=\\{x_{1}x_{2}x_{3}\in A^{3}_{m}(4m,<):m\leq x_{1}\leq
2m-1\text{ and }3m\leq x_{3}\leq 4m-1\\};$ $\displaystyle C$
$\displaystyle:=\\{x_{1}x_{2}x_{3}\in A^{3}_{m}(4m,<):0\leq x_{1}\leq
m-1\text{ and }2m\leq x_{3}\leq 3m-1\\}.$

Since $x_{3}-x_{1}\geq 2m$ for $x_{1}x_{2}x_{3}\in A^{3}_{m}(4m,<)$, $A\cup
B\cup C$ is a partition of $A^{3}_{m}(4m,<)$. Note that any vertex in $A$ is
an isolated vertex in $S^{<}_{m}(3,4m)$ and all edges in $S^{<}_{m}(3,4m)$ are
between $B$ and $C$. Let $R_{1}=A\cup B$ and $R_{2}=C$. Then $S_{m}^{<}(3,4m)$
is bipartite with parts $R_{1}\cup R_{2}$. Let
$\overline{R}_{1}\cup\overline{R}_{2}$ be a partition of $A^{n}_{m}(4m,>)$,
where

$\overline{R}_{i}=\\{x_{3}x_{2}x_{1}\ |\ x_{1}x_{2}x_{3}\in R_{i}\\}\text{ for
}i=1,2.$

Then, $S^{>}_{m}(3,4m)$ is also bipartite with parts
$\overline{R}_{1}\cup\overline{R}_{2}$.

Step 1. Define a mapping from $S_{m}(3,4m)$ to the graph $H$ in Figure 4 as
follows. Let $w=x_{1}x_{2}x_{3}$ be a vertex of $S_{m}(3,4m)$.

  * $\bullet$

If $\omega\in R_{2}$, then $f(\omega)=R_{2}$.

  * $\bullet$

If $\omega\in\overline{R}_{2}$, then $f(\omega)=\overline{R}_{2}$.

  * $\bullet$

If $\omega\in R_{1}\cup\overline{R}_{1}$ then $f(\omega)=R^{\prime}$.

  * $\bullet$

If $x_{2}\geq x_{1}+m$ and $x_{2}\geq x_{3}+m$, then $f(\omega)=B$.

  * $\bullet$

If $x_{2}\leq x_{1}-m$ and $x_{2}\leq x_{3}-m$, then $f(\omega)=G$.

Step 2. Direct $S_{m}(3,4m)$ as in $H$. Again, note that $H$ contains only two
shortcutting paths of length at least 3:

$\displaystyle R^{\prime}\rightarrow B\rightarrow R_{2}\rightarrow G;$
$\displaystyle R^{\prime}\rightarrow B\rightarrow\overline{R}_{2}\rightarrow
G.$

Step 3. Suppose that there exists a directed path
$\omega_{R^{\prime}}\rightarrow\omega_{B}\rightarrow\omega_{R_{2}}\rightarrow\omega_{G}$
with $f(\omega_{X})=X$ for all $X\in\\{R^{\prime},B,R_{2},G\\}$, and the path
introduces a potential shortcutting edge, that is,
$\omega_{R^{\prime}}\rightarrow\omega_{G}$. Assume that
$\omega_{R_{2}}=x_{1}x_{2}x_{3}$ with $x_{1}+m\leq x_{2}\leq x_{3}-m$.
According to the forms of $\omega_{B}$ and $\omega_{G}$, we have
$\omega_{B}=x_{2}x_{3}z$ and $\omega_{G}=yx_{1}x_{2}$ where $x_{1}+m\leq y$
and $z\leq x_{3}-m$. Since $\omega_{R^{\prime}}$ is adjacent to $\omega_{B}$,
we have $\omega_{R^{\prime}}=vx_{2}x_{3}$ for some $v\leq x_{2}-m$ or
$\omega_{R^{\prime}}=x_{3}zv$ for some $v\leq z-m$. Since
$\omega_{R^{\prime}}$ is adjacent to $\omega_{G}$, we have
$\omega_{R^{\prime}}=x_{1}x_{2}u$ for some $u\geq x_{2}+m$ or
$\omega_{R^{\prime}}=uyx_{1}$ for some $u\geq y+m$. So, two cases are
possible. If $\omega_{R^{\prime}}=x_{1}x_{2}u=vx_{2}x_{3}$ then
$v=x_{1},u=x_{3}$ and $\omega_{R^{\prime}}=x_{1}x_{2}x_{3}=\omega_{R_{2}},$ a
contradiction. If $\omega_{R^{\prime}}=uyx_{1}=x_{3}zv$ then $v=x_{1},u=x_{3}$
and $z=y,$ i.e. $\omega_{R^{\prime}}=x_{3}yx_{1}$. Note that
$\omega_{R^{\prime}}\in\overline{R}_{1}$ and hence $x_{1}yx_{3}$ is a word in
$R_{1}$. However, since $\omega_{R_{2}}=x_{1}x_{2}x_{3}\in R_{2}$, $0\leq
x_{1}\leq m-1$ and $2m\leq x_{3}\leq 3m-1$. This implies $x_{1}yx_{3}$ should
be in $R_{2}$ but not in $R_{1}$, a contradiction.

So, there are no shortcuts induced by
$\\{\omega_{R^{\prime}},\omega_{B},\omega_{R_{2}},\omega_{G}\\}$. Similarly,
there are no shortcuts induced by
$\\{\omega_{R^{\prime}},\omega_{B},\omega_{\overline{R}_{2}},\omega_{G}\\}$.
Hence, the orientation of $S_{m}(3,4m)$ is shortcut-free and therefore it is
semi-transitive. By Theorem 1, $S_{m}(3,4m)$ is word-representable, as
desired. ∎

###  4.4 Word-representability of $S_{m}(n,k)$ for even $n\geq 4$

First, we show that Theorem 5(ii) holds for any even $n\geq 6$.

######  Lemma 7.

For even $n\geq 6$ and $k\leq 2mn$, $S_{m}(n,k)$ is word-representable.

###### Proof.

By Lemma 4, $S^{<}_{m}(n,k)$ is bipartite, and we denote its parts by $B_{1}$
and $B_{2}$. Let $G_{1}\cup G_{2}$ be a partition of $A^{n}_{m}(k,>)$, where

$G_{i}=\\{x_{n}x_{n-1}\ldots x_{1}\ |\ x_{1}x_{2}\ldots x_{n}\in
B_{i}\\}\text{ for }i=1,2.$

Then $S^{>}_{m}(n,k)$ is also bipartite with parts $G_{1}\cup G_{2}$.

For a vertex $\omega=x_{1}x_{2}\ldots x_{n}$ in $S_{m}(n,k)$, let
$\tau(\omega)=y_{1}\ldots y_{n-1}$ where $y_{i}=0$ if $x_{i}>x_{i+1}$ and
$y_{i}=1$ otherwise. Then $\tau$ is a mapping from $S_{m}(n,k)$ to
$S_{0}(n-1,2)$. Recall that in the case of even $n$ the color classes of
$S_{0}(n-1,2)$ are as follows:

$\displaystyle\text{\bf Red: }e_{0}a_{1},e_{1}a_{0};$ $\displaystyle\text{\bf
Blue: }o_{1},o_{1}o_{0}a_{1},o_{1}e_{0}b_{1};$ $\displaystyle\text{\bf Green:
}o_{0},o_{0}o_{1}a_{0},o_{0}e_{1}b_{0}.$

Note that the form of $\tau(\omega)$ is $o_{1}$ (resp., $o_{0}$) if and only
if $\omega$ is a vertex in $B_{1}\cup B_{2}$ (resp., $G_{1}\cup G_{2}$).

$B_{3}$$B_{1}$$G_{2}$$G_{4}$$B_{4}$$R_{1}$$R_{2}$$B_{2}$$G_{3}$$G_{1}$ Figure
5: A graph $H$ and its orientation.

Step 1. Let $H$ be the underlying graph with the vertex set

$\\{R_{1},R_{2},B_{1},B_{2},B_{3},B_{4},G_{1},G_{2},G_{3},G_{4}\\}$

in Figure 5. Consider the following mapping $f$ from $S_{m}(n,k)$ to $H$.

  * $\bullet$

If the form of $\tau(\omega)$ is $e_{0}a_{1}$ then $f(\omega)=R_{1}$.

  * $\bullet$

If the form of $\tau(\omega)$ is $e_{1}a_{0}$ then $f(\omega)=R_{2}$.

  * $\bullet$

If $\omega\in B_{1}$ then $f(\omega)=B_{1}$.

  * $\bullet$

If $\omega\in B_{2}$ then $f(\omega)=B_{2}$.

  * $\bullet$

If the form of $\tau(\omega)$ is $o_{1}o_{0}a_{1}$ then $f(\omega)=B_{3}$.

  * $\bullet$

If the form of $\tau(\omega)$ is $o_{1}e_{0}b_{1}$ then $f(\omega)=B_{4}$.

  * $\bullet$

If $\omega\in G_{1}$ then $f(\omega)=G_{1}$.

  * $\bullet$

If $\omega\in G_{2}$ then $f(\omega)=G_{2}$.

  * $\bullet$

If the form of $\tau(\omega)$ is $o_{0}o_{1}a_{0}$ then $f(\omega)=G_{3}$.

  * $\bullet$

If the form of $\tau(\omega)$ is $o_{0}e_{1}b_{0}$ then $f(\omega)=G_{4}$.

Clearly, all sets of vertices of $S_{m}(n,k)$ mapped into the same vertex of
$H$ are independent. For any vertex $\omega$ mapped into $G_{1}\cup G_{2}$,
$\tau(\omega)$ has the form $o_{0}$; so, it may be adjacent only to a vertex
$\omega^{\prime}$ for which $\tau(\omega^{\prime})$ has the form $o_{1}e_{0}$,
or $e_{0}o_{1}$, or $o_{0}$. So, a neighbour of $\omega$ can only be mapped
into $G_{1}\cup G_{2}\cup R_{1}\cup B_{4}$. Similarly, a neighbour of a vertex
from $B_{1}\cup B_{2}$ can only be mapped into $B_{1}\cup B_{2}\cup R_{2}\cup
G_{4}$. Also, if $\omega$ was mapped in $G_{3}$ then $\tau(\omega)$ has the
form $o_{0}o_{1}a_{0}$ and for each of its neighbour $\omega^{\prime}$,
$\tau(\omega^{\prime})$ has the form $e_{0}a_{1}$, or $o_{1}o_{0}a_{1}$, or
$o_{1}a_{0}$. So, $\omega^{\prime}$ must be in $R_{1}\cup B_{3}\cup B_{4}$. By
similar arguments, any neighbour of a vertex from $B_{3}$ is mapped into
$R_{2}\cup G_{3}\cup G_{4}$.

Finally, if $\omega$ was mapped in $G_{4}$ then $\tau(\omega)$ has the form
$o_{0}e_{1}b_{0}$ and for each of its neighbour $\omega^{\prime}$,
$\tau(\omega^{\prime})$ has the form $e_{0}a_{1}$, or $e_{1}a_{0}$, or
$o_{1}$, or $o_{1}o_{0}a_{1}$. In either case, $\omega^{\prime}$ was not
mapped into $B_{4}$. So, $f$ is a homomorphism from $S_{m}(n,k)$ to $H$. Then
direct $H$ as in Figure 5.

Step 2. Note that there are four shortcutting paths in $H$:

$\displaystyle G_{2}\rightarrow R_{1}\rightarrow G_{1}\rightarrow B_{4};$
$\displaystyle G_{2}\rightarrow R_{1}\rightarrow G_{3}\rightarrow B_{4};$
$\displaystyle G_{4}\rightarrow B_{1}\rightarrow R_{2}\rightarrow B_{2};$
$\displaystyle G_{4}\rightarrow B_{3}\rightarrow R_{2}\rightarrow B_{2}.$

Note that the shortcutting paths in the right column are shortcuts. Direct the
edges of $S_{m}(n,k)$ as in $H$. Since the orientation of $H$ is acyclic, the
orientation of $S_{m}(n,k)$ is also acyclic. We have to verify that the
orientation contains no shortcuts.

Step 3. Suppose that there exists a directed path
$\omega_{G_{2}}\rightarrow\omega_{R_{1}}\rightarrow\omega_{G_{1}}\rightarrow\omega_{B_{4}}$
with $f(\omega_{X})=X$ for $X\in\\{G_{2},R_{1},G_{1},B_{4}\\}$, and the path
introduces a potential shortcutting edge, that is,
$\omega_{G_{2}}\rightarrow\omega_{B_{4}}$. Assume
$\omega_{G_{2}}=x_{1}x_{2}\ldots x_{n}$ with $x_{i}\geq x_{i+1}+m$. Since the
form of $\tau(\omega_{R_{1}})$ is $e_{0}x_{1}$ and
$\omega_{G_{2}}\omega_{R_{1}}\in E(S_{m}(n,k))$, $\omega_{R_{1}}=x_{2}\ldots
x_{n}y$ with $y\geq x_{n}+m$. Since $\omega_{R_{1}}\omega_{G_{1}}\in
E(S_{m}(n,k))$, $\omega_{G_{1}}=x^{\prime}_{1}x_{2}\ldots x_{n}$ with
$x^{\prime}_{1}\geq x_{2}+m$ and $x^{\prime}_{1}\neq x_{1}$. Then we have
$\omega_{B_{4}}=zx^{\prime}_{1}x_{2}\ldots x_{n-1}$ with $z\leq
x^{\prime}_{1}-m$. However, $\omega_{G_{2}}\omega_{B_{4}}\in E(S_{m}(n,k))$ if
and only if $x_{1}=x^{\prime}_{1}$. Thus, $\omega_{G_{2}}\omega_{B_{4}}\notin
E(S_{m}(n,k))$, a contradiction.

Then, we consider the shortcutting path $G_{2}\rightarrow R_{1}\rightarrow
G_{3}\rightarrow B_{4}$. Suppose that there exists a directed path
$\omega_{G_{2}}\rightarrow\omega_{R_{1}}\rightarrow\omega_{G_{3}}\rightarrow\omega_{B_{4}}$
with $f(\omega_{X})=X$ for $X\in\\{G_{2},R_{1},G_{3},B_{4}\\}$ and also
$\omega_{G_{2}}\rightarrow\omega_{B_{4}}$. Assume
$\omega_{G_{2}}=x_{1}x_{2}\ldots x_{n}$ with $x_{i}\geq x_{i+1}+m$. Then we
have $\omega_{R_{1}}=x_{2}\ldots x_{n}y$ and $\omega_{G_{3}}=x_{3}\ldots
x_{n}yz$ with $y\geq x_{n}+m$ and $z\leq y-m$. However, since $n\geq 6$, no
neighbour of $\omega_{G_{3}}$ was mapped into $B_{4}$, a contradiction.

By similar arguments, no shortcut was mapped into the shortcutting paths
$G_{4}\rightarrow B_{1}\rightarrow R_{2}\rightarrow B_{2}$ and
$G_{4}\rightarrow B_{3}\rightarrow R_{2}\rightarrow B_{2}$. Hence, the
orientation of $S_{m}(n,k)$ is shortcut-free and therefore it is semi-
transitive. By Theorem 1, $S_{m}(n,k)$ is word-representable for all even
$n\geq 6$ and $k\leq 2mn$.∎

The remaining case of $n=4$ is proved in the following lemma.

######  Lemma 8.

For $k\leq 5m$, $S_{m}(4,k)$ is word-representable.

###### Proof.

By Lemma 1, it is sufficient to show that $S_{m}(4,5m)$ is word-representable.
Let $A$, $B$ and $C$ be the following subsets of $A^{4}_{m}(5m,<)$:

$\displaystyle A$ $\displaystyle:=\\{x_{1}x_{2}x_{3}x_{4}\in
A^{4}_{m}(5m,<):0\leq x_{1}\leq m-1\text{ and }4m\leq x_{4}\leq 5m-1\\};$
$\displaystyle B$ $\displaystyle:=\\{x_{1}x_{2}x_{3}x_{4}\in
A^{4}_{m}(5m,<):m\leq x_{1}\leq 2m-1\text{ and }4m\leq x_{4}\leq 5m-1\\};$
$\displaystyle C$ $\displaystyle:=\\{x_{1}x_{2}x_{3}x_{4}\in
A^{4}_{m}(5m,<):0\leq x_{1}\leq m-1\text{ and }3m\leq x_{4}\leq 4m-1\\}.$

Since $x_{4}-x_{1}\geq 3m$ for $x_{1}x_{2}x_{3}x_{4}\in A^{4}_{m}(5m,<)$,
$A\cup B\cup C$ is a partition of $A^{4}_{m}(5m,<)$. Note that any vertex in
$A$ is an isolated vertex in $S^{<}_{m}(4,5m)$ and all edges in
$S^{<}_{m}(4,5m)$ are between $B$ and $C$. Let $B_{1}=A\cup B$ and $B_{2}=C$.
Then $S_{m}^{<}(4,5m)$ is bipartite with parts $B_{1}\cup B_{2}$. Let
$G_{1}\cup G_{2}$ be a partition of $A^{4}_{m}(5m,>)$, where

$G_{i}=\\{x_{4}x_{3}x_{2}x_{1}\ |\ x_{1}x_{2}x_{3}x_{4}\in B_{i}\\}\text{ for
}i=1,2.$

Then $S^{>}_{m}(4,5m)$ is also bipartite with parts $G_{1}\cup G_{2}$.

$B_{3}$$B_{1}$$G_{2}$$G_{4}$$B_{4}$$R_{1}$$R_{2}$$B_{2}$$G_{3}$$G_{1}$ Figure
6: A graph $H$ and its orientation.

Steps 1, 2. In what follows, we use the same notation as in Lemma 7 but a
different orientation of $H$ given in Figure 6. Direct $S_{m}(4,5m)$ as in $H$
and note that $H$ contains only two shortcutting paths of length at least 3:

$\displaystyle R_{1}\rightarrow G_{2}\rightarrow G_{1}\rightarrow B_{4};$
$\displaystyle R_{2}\rightarrow G_{4}\rightarrow B_{2}\rightarrow B_{1}.$

Step 3. Suppose that there exists a directed path
$\omega_{R_{1}}\rightarrow\omega_{G_{2}}\rightarrow\omega_{G_{1}}\rightarrow\omega_{B_{4}}$
with $f(\omega_{X})=X$ for all $X\in\\{R_{1},G_{2},G_{1},B_{4}\\}$, and the
path introduces a potential shortcutting edge, that is,
$\omega_{R_{1}}\rightarrow\omega_{B_{4}}$. By definitions of $G_{2}$ and
$G_{1}$, assume that $\omega_{G_{2}}=x_{2}x_{3}x_{4}x_{5}$ and
$\omega_{G_{1}}=x_{1}x_{2}x_{3}x_{4}$, where $x_{i}\geq x_{i+1}+m$, $4m\leq
x_{1}\leq 5m-1$ and $0\leq x_{5}\leq m-1$. Then, we have
$\omega_{R_{1}}=x_{3}x_{4}x_{5}y$ with $y\geq x_{5}+m$ and
$\omega_{B_{4}}=zx_{1}x_{2}x_{3}$ with $z\leq x_{1}-m$. However,
$\omega_{R_{1}}$ is not adjacent to $\omega_{B_{4}}$ in $S_{m}(4,5m)$, a
contradiction. So there are no shortcuts induced by
$\\{\omega_{R_{1}},\omega_{G_{2}},\omega_{G_{1}},\omega_{B_{4}}\\}$.

Suppose now that there exists a directed path
$\omega_{R_{2}}\rightarrow\omega_{G_{4}}\rightarrow\omega_{B_{2}}\rightarrow\omega_{B_{1}}$
with $f(\omega_{X})=X$ for all $X\in\\{R_{2},G_{4},B_{2},B_{1}\\}$ and also
$\omega_{R_{2}}\rightarrow\omega_{B_{1}}$. Assume that
$\omega_{B_{1}}=x_{2}x_{3}x_{4}x_{5}$ and
$\omega_{B_{2}}=x_{1}x_{2}x_{3}x_{4}$, where $x_{i}\leq x_{i+1}+m$, $4m\leq
x_{5}\leq 5m-1$ and $0\leq x_{1}\leq m-1$. Then, we have
$\omega_{R_{2}}=x_{3}x_{4}x_{5}y$ with $y\leq x_{5}-m$ and
$\omega_{G_{4}}=zx_{1}x_{2}x_{3}$ with $z\geq x_{1}+m$. But then
$\omega_{R_{2}}$ is not adjacent to $\omega_{G_{4}}$ in $S_{m}(4,5m)$, a
contradiction. So, there are no shortcuts induced by
$\\{\omega_{R_{2}},\omega_{G_{4}},\omega_{B_{2}},\omega_{B_{1}}\\}$. Hence,
the orientation of $S_{m}(4,5m)$ is shortcut-free and therefore it is semi-
transitive. By Theorem 1, $S_{m}(4,5m)$ is word-representable, as desired. ∎

##  5 Conclusion

In this paper, we introduce a novel approach to study word-representability of
graphs with the help of homomorphisms. In the proof of Theorem 4, we find a
homomorphism $f$ from $SP(n)$ to a 3-colorable graph $S_{0}(n-1,2)$. In the
proof of Theorem 5, we find a homomorphism $f$ from $S_{m}(n,k)$ to a graph
with 5 vertices (for odd $n$) or a graph with 10 vertices (for even $n$).

As the result, we have proved:

$\bullet$ For $n=2$, $S_{m}(2,k)$ is word-representable if and only if $k\leq
3m$;

$\bullet$ For $n=3$, $S_{m}(3,k)$ is word-representable if $k\leq 4m$;

$\bullet$ For $n=4$, $S_{m}(4,k)$ is word-representable if $k\leq 5m$;

$\bullet$ For $n\geq 5,\ S_{m}(n,k)$ is word-representable if $k\leq 2mn$.

We leave it as an open problem whether or not the “if” in the last three
statements can be replaced by “if and only if”.

Acknowledgement. The authors are grateful to the anonymous referees for their
valuable comments.

## References

  * [1] F. Chung, P. Diaconis, R. Graham. Universal cycles for combinatorial structures. Discrete Math. 110 (1992) 43–59.
  * [2] M. M. Halldórsson, S. Kitaev, A. Pyatkin. Semi-transitive orientations and word-representable graphs. Discr. Appl. Math. 201 (2016) 164–171.
  * [3] P. Hell, J. Nešetřil. Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications, vol. 28, 2004. Oxford University Press.
  * [4] S. Kitaev. A Comprehensive Introduction to the Theory of Word-Representable Graphs. Lect. Notes in Comp. Sci. 10396 (2017) 36–67.
  * [5] S. Kitaev and V. Lozin. Words and Graphs, Springer, 2015.
  * [6] S. Kitaev and A. Pyatkin. Word-Representable Graphs: a Survey, J. Appl. and Industr. Math. 12 (2018) 2, 278–296.
  * [7] S. Kitaev, H. Sun. Human-verifiable proofs in the theory of word-representable graph. arXiv:2110.05405v2.
  * [8] M. Lothaire. Combinatorics on words, Encyclopedia of Mathematics and its Applications, vol. 17 (1983) Addison-Wesley Publishing Co., Reading, Mass.
  * [9] A. V. Petyuk. On word-representability of simplified de Bruijn graphs. arXiv:2210.14762.
  * [10] P. A. Pevzner, H. Tang, M. S. Waterman. An Eulerian path approach to DNA fragment assembly. Proceedings of the National Academy of Sciences 98 (17) (2001) 9748–9753.

## Appendix: Proof of non-word-representability of $S_{1}(2,4)$

Our proof uses the following lemmas.

######  Lemma 9 ([7]).

Suppose that an undirected graph $G$ has a cycle $C=x_{1}x_{2}\cdots
x_{m}x_{1}$, where $m\geq 4$ and the vertices in
$\\{x_{1},x_{2},\ldots,x_{m}\\}$ do not induce a clique in $G$. If $G$ is
oriented semi-transitively, and $m-2$ edges of $C$ are oriented in the same
direction then the remaining two edges of $C$ are oriented in the opposite
direction.

######  Lemma 10 ([7]).

If $G$ is word-representable and $u$ is an arbitrary vertex in $G$, then there
exists a semi-transitive orientation of $G$ with source $u$.

The proof is a tedious case-analysis with many similar procedures. So, we use
some encoding for them that allows to shorten the text drastically. By a
“line” of a proof we mean a sequence of instructions that directs us in
orienting a partially oriented graph and necessarily ends with detecting a
shortcut. Each line of the proof is marked by its number in bold font. There
are four types of instructions:

  * $\bullet$

“B” followed by “$X\rightarrow Y$ (Copy $Z$)” reads “Branch on edge $XY$”.
This means that we make a copy of the current graph (it is called Copy $Z$),
direct the edge $X\rightarrow Y$ and proceed further. Note that Copy $Z$ will
be considered later with an opposite orientation $Y\rightarrow X$.

  * $\bullet$

“MC” followed by a number $X$ means “Move to Copy $X$”. Each line except for
the first one must start with this instruction. Moreover, this instruction is
always followed by “$Y\rightarrow X$” that orients a branching edge in the
opposite way.

  * $\bullet$

One or two “O” followed by “$X_{i}\rightarrow Y_{i}$” together with “(C”
followed by a cycle “$Z_{1}-\cdots-Z_{k}$)”. This instruction means “Orient
the listed edges $X_{i}\rightarrow Y_{i}$ since otherwise the cycle
$Z_{1}-\cdots-Z_{k}$ either becomes directed or contradicts Lemma 9.

  * $\bullet$

“$S:X_{1}-\cdots-X_{k}$” means “Verify that the path $X_{1}-\cdots-X_{k}$”
induces a shortcut with the shortcutting edge $X_{1}\rightarrow X_{k}$. This
instruction concludes each line of the proof.

We refer to [7] for more details on the format of the proof below.

Figure 7: $S_{1}(2,4)$. The bold numbers are the labels of vertices in
$S_{1}(2,4)$.

The proof: We label the vertices in $S_{1}(2,4)$ in brackets in bold in Figure
7. By Lemma 10, without loss of generality, assume vertex 6 is a source in a
semi-transitive orientation. The rest of the proof goes as follows.

1. B8$\rightarrow$12 (Copy 2) B1$\rightarrow$10 (Copy 3) B7$\rightarrow$12 (Copy 4) O7$\rightarrow$ 1 (C1-7-12-6) O2$\rightarrow$10 O7$\rightarrow$2 (C1-10-2-7) O8$\rightarrow$2 (C2-8-12-7) S:6-8-2-10

2. MC4 12$\rightarrow$7 O1$\rightarrow$7 (C1-7-12-6) O8$\rightarrow$2 O2$\rightarrow$7 (C2-8-12-7) O2$\rightarrow$10 (C1-10-2-7) S:6-8-2-10

3. MC3 10$\rightarrow$1 B7$\rightarrow$12 (Copy 5) O7$\rightarrow$1 (C1-7-12-6) B9$\rightarrow$10 (Copy 6) O9$\rightarrow$5 O5$\rightarrow$1 (C1-10-9-5) O5$\rightarrow$8 (C1-6-8-5) O5$\rightarrow$11 (C1-6-11-5) O9$\rightarrow$11 (C5-11-9) O9$\rightarrow$2 O2$\rightarrow$8 (C2-9-5-8) O2$\rightarrow$7 (C2-8-12-7) O2$\rightarrow$4 O4$\rightarrow$1 (C1-7-2-4) O4$\rightarrow$11 (C1-5-11-4) S:9-2-4-11

4. MC6 10$\rightarrow$9 O12$\rightarrow$9 (C6-12-9-10) O2$\rightarrow$9 O7$\rightarrow$2 (C2-9-12-7) O5$\rightarrow$9 O7$\rightarrow$5 (C2-9-5-7) O5$\rightarrow$1 (C1-10-9-5) O5$\rightarrow$8 (C1-6-8-5) S:5-8-12-9

5. MC5 12$\rightarrow$7 O1$\rightarrow$7 (C1-7-12-6) O10$\rightarrow$2 O2$\rightarrow$7 (C1-10-2-7) O8$\rightarrow$2 (C2-8-12-7) O8$\rightarrow$5 O5$\rightarrow$7 (C2-8-5-7) O1$\rightarrow$5 (C1-6-8-5) O10$\rightarrow$9 O9$\rightarrow$5 (C1-10-9-5) O9$\rightarrow$2 (C2-9-5-7) O9$\rightarrow$12 (C2-9-12-7) S:6-10-9-12

6. MC2 12$\rightarrow$8 B1$\rightarrow$10 (Copy 7) B7$\rightarrow$12 (Copy 8) O7$\rightarrow$1 (C1-7-12-6) O2$\rightarrow$10 O7$\rightarrow$2 (C1-10-2-7) O2$\rightarrow$8 (C2-8-12-7) O5$\rightarrow$8 O7$\rightarrow$5 (C2-8-5-7) O5$\rightarrow$1 (C1-6-8-5) O9$\rightarrow$10 O5$\rightarrow$9 (C1-10-9-5) O2$\rightarrow$9 (C2-9-5-7) O12$\rightarrow$9 (C2-9-12-7) S:6-12-9-10

7. MC8 12$\rightarrow$7 O1$\rightarrow$7 (C1-7-12-6) B9$\rightarrow$10 (Copy 9) O9$\rightarrow$12 (C6-12-9-10) O9$\rightarrow$2 O2$\rightarrow$7 (C2-9-12-7) O9$\rightarrow$5 O5$\rightarrow$7 (C2-9-5-7) O1$\rightarrow$5 (C1-10-9-5) O8$\rightarrow$5 (C1-6-8-5) S:9-12-8-5

8. MC9 10$\rightarrow$9 O5$\rightarrow$9 O1$\rightarrow$5 (C1-10-9-5) O8$\rightarrow$5 (C1-6-8-5) O11$\rightarrow$5 (C1-6-11-5) O11$\rightarrow$9 (C5-11-9) O2$\rightarrow$9 O8$\rightarrow$2 (C2-9-5-8) O7$\rightarrow$2 (C2-8-12-7) O4$\rightarrow$2 O1$\rightarrow$4 (C1-7-2-4) O11$\rightarrow$4 (C1-5-11-4) S:11-4-2-9

9. MC7 10$\rightarrow$1 B7$\rightarrow$12 (Copy 10) O7$\rightarrow$1 (C1-7-12-6) O2$\rightarrow$8 O7$\rightarrow$2 (C2-8-12-7) O10$\rightarrow$2 (C1-10-2-7) S:6-10-2-8

10. MC10 12$\rightarrow$7 O1$\rightarrow$7 (C1-7-12-6) O10$\rightarrow$2 O2$\rightarrow$7 (C1-10-2-7) O10$\rightarrow$3 O2$\rightarrow$8 (C2-8-12-7) S:6-10-2-8