# The absence of monochromatic triangle implies various properly colored
spanning trees

Ruonan Li Supported by National Natural Science Foundation of China (No.
11901459), China Scholarship Council (No. 202306290113) and the Institute for
Basic Science (IBS-R029-C4). E-mail<EMAIL_ADDRESS>School of Mathematics
and Statistics, Northwestern Polytechnical University, Xi’an, Shaanxi, 710129,
P.R. China  Xi’an-Budapest Joint Research Center for Combinatorics
Northwestern Polytechnical University, Xi’an, Shaanxi,710129, P.R. China
Ruhui Lu E-mail<EMAIL_ADDRESS>School of Mathematics and Statistics,
Northwestern Polytechnical University, Xi’an, Shaanxi, 710129, P.R. China
Xi’an-Budapest Joint Research Center for Combinatorics
Northwestern Polytechnical University, Xi’an, Shaanxi,710129, P.R. China
Xueli Su E-mail<EMAIL_ADDRESS>School of Mathematics and Statistics,
Northwestern Polytechnical University, Xi’an, Shaanxi, 710129, P.R. China
Xi’an-Budapest Joint Research Center for Combinatorics
Northwestern Polytechnical University, Xi’an, Shaanxi,710129, P.R. China
Shenggui Zhang Supported by National Natural Science Foundation of China (No.
12071370, No. 12131013) and Shaanxi Fundamental Science Research Project for
Mathematics and Physics (No.22JSZ009). E-mail<EMAIL_ADDRESS>School of
Mathematics and Statistics, Northwestern Polytechnical University, Xi’an,
Shaanxi, 710129, P.R. China  Xi’an-Budapest Joint Research Center for
Combinatorics
Northwestern Polytechnical University, Xi’an, Shaanxi,710129, P.R. China

###### Abstract

An edge-colored graph $G$ is called properly colored if every two adjacent
edges are assigned different colors. A monochromatic triangle is a cycle of
length 3 with all the edges having the same color. Given a tree $T_{0}$, let
$\mathcal{T}(n,T_{0})$ be the collection of $n$-vertex trees that are
subdivisions of $T_{0}$. It is conjectured that for each fixed tree $T_{0}$ of
$k$ edges, there is a function $f(k)$ such that for each integer $n\geq f(k)$
and each $T\in\mathcal{T}(n,T_{0})$, every edge-colored complete graph $K_{n}$
without containing monochromatic triangle must contain a properly colored copy
of $T$. We confirm the conjecture in the case that $T_{0}$ is a star. A weaker
version of the above conjecture is also obtained. Moreover, to get a nice
quantitative estimation of $f(k)$ requires determining the constraint Ramsey
number of a monochromatic triangle and a rainbow $k$-star, which is of
independent interest.

##  1 Introduction

Let $G$ be an edge-colored graph. We say $G$ is monochromatic if all the edges
are of the same color, and rainbow if all the edges are of distinct colors,
and lexical if there is a total order of $V(G)$ such that edges $uv$ and $xy$
have a same color if and only if $\min\\{u,v\\}=\min\\{x,y\\}$. The Canonical
Ramsey Theorem founded by Erdős and Rado [12] states that given an integer
$k$, each edge-colored complete graph of sufficiently large order always
contains a $k$-clique $H$, which is either monochromatic or rainbow or
lexical. In fact, the absence of certain rainbow (monochromatic) subgraph
often forces a giant connected subgraph that is monochromatic (colors fully
mixed). For instance, Erdős and Rado [12] observed that every $2$-colored
complete graph always contains a monochromatic spanning tree. Gallai partition
theorem [14](c.f.[17]) implies that the absence of rainbow triangle in edge-
colored complete graphs forces a spanning 2-colored subgraph. Studying a
conjecture proposed by Andersen [4], Alon, Pokrovskiy and Sudakov [3] proved
that each edge-colored $K_{n}$ without monochromatic path of length $2$
contains a rainbow path of length $n-o(n)$. Asymptotically solving a
conjecture given by Bollobás and Erdős[8], Lo’s result [25] tells that each
edge-colored $K_{n}$ without monochromatic star of size $(1/2-\epsilon)n$
always contains a properly colored Hamilton cycle when $n$ is sufficiently
large. An edge-colored graph is called properly colored (say “PC ” for short)
if every two adjacent edges are of distinct colors. In this paper, we continue
the exploration of spanning properly colored subgraphs in edge-colored
complete graphs when a fixed monochromatic configuration is forbidden.

An easy observation given by Barr [5] tells that each edge-colored $K_{n}$
without containing a monochromatic triangle (say “mono-$C_{3}$-free” for
short) must contain a PC Hamilton path. Under the same condition, the first
author [22] studied the existence of PC Hamilton cycles and obtained a full
characterization of the counterexamples. Particularly, when $n\geq 6$, every
counterexample acts locally like a non-strongly-connected directed graph. In
fact, for any PC spanning target graphs containing cycles, an edge-colored
complete graph transformed from a transitive tournament is always a
counterexample. Therefore it is natural to study the existence of properly
colored spanning trees in mono-$C_{3}$-free complete graphs. For more
relations between edge-colored graphs and directed graphs, we refer the
readers to [13, 24, 23, 1, 11].

Let $T_{0}$ be a fixed tree. We use $\mathcal{T}(n,T_{0})$ to denote the
collection of $n$-vertex trees that are subdivisions of $T_{0}$. Note that a
Hamilton path can be regarded as a subdivision of $K_{2}$. We show the
existence of a properly colored spanning tree which is a subdivision of a
given tree.

######  Theorem 1.

Let $T_{0}$ be a tree of $k$ edges and let $G$ be a mono-$C_{3}$-free edge-
colored $K_{n}$ with $n\geq(k+2)!$. Then there exists a tree
$T\in\mathcal{T}(n,T_{0})$ such that $G$ contains a PC copy of $T$.

In the above theorem, there is no control on the distribution of subdividing
vertices on different edges of $T_{0}$. We wonder the existence of all
possible subdivisions and therefore propose the following conjecture.

######  Conjecture 1.

Let $T_{0}$ be a tree of $k$ edges and let $G$ be a mono-$C_{3}$-free edge-
colored $K_{n}$. There exists a function $f(k)$ such that if $n\geq f(k)$,
then for each tree $T\in\mathcal{T}(n,T_{0})$, $G$ contains a PC copy of $T$.

We confirm the above conjecture when $T_{0}$ is a star. For $k\geq 3$, a
subdivision of a $k$-star is called a $k$-spider. A leg in a $k$-spider $T$ is
a path $P$ from the unique $k$-degree vertex to a leaf of $T$. If $P$ contains
$\ell$ edges, then we say the leg $P$ is of length $\ell$. Use $C_{3}$ and
$S_{k}$ to denote a triangle and a star of $k$ edges. Let $g(S_{k},C_{3})$ to
be the maximum number $N$ such that there exists an edge-colored $K_{N}$
containing neither a rainbow $S_{k}$ nor a monochromatic $C_{3}$. The
existence of $g(S_{k},C_{3})$ is guaranteed by the Canonical Ramsey Theorem.
In literature, Gyárfás, Lehel, Schelp and Tuza [16] studied the Local Ramsey
number; Jamison, Jiang and Ling [20] defined the Constraint Ramsey Number.
Both definitions are consistent with $g(S_{k},C_{3})$. We will use the
notation $g(S_{k},C_{3})$ to state our main result. A weak upper bound of
$g(S_{k},C_{3})$ is given in Section 4, which is applied in the proof of
Theorem 1.

######  Theorem 2.

Given an integer $k\geq 3$, let $G$ be a mono-$C_{3}$-free edge-colored
$K_{n}$. If $n\geq 6k\cdot g(S_{k},C_{3})+2k^{3}+2k^{2}+8k$, then for every
$k$ positive integers $\ell_{1}\geq\ell_{2}\geq\cdots\geq\ell_{k}$ satisfying
$\sum_{i=1}^{k}\ell_{i}=n-1$, $G$ contains a properly colored spanning spider
$T$ with legs of lengths $\ell_{1},\ell_{2},\ldots,\ell_{k}$, respectively.

Sketch of the proofs. To prove Theorem 1, we first show the existence of every
properly colored tree on $k$ edges (this is guaranteed by the Canonical Ramsey
Theorem for sufficiently large $n$. Our proof gives an explicit bound for
$n$), and then embed the remaining vertices greedily. However, the greedy
method can not guarantee the number of subdividing vertices on each edge
precisely as whatever we want. Therefore the key point in the proof of Theorem
2 is using some extensible structures as glue to merge vertices in
mono-$C_{3}$-free complete graphs into legs. If the host graph has many “nice
bowties”, then we are home. Otherwise, by removing constant number of
vertices, the host graph is essentially a multipartite tournament with certain
properties inherent from the “mono-$C_{3}$-free” condition. Then by analyzing
the structure of this multipartite tournament, we obtain a certain oriented
tree which is almost the spanning tree we desired, except for the first leg.
Applying some structural lemmas proved in Section 2, we finally embed the
remaining vertices.

In Section 2, we define some crucial structures and obtain related properties.
In Section 3, we study the “mono-$C_{3}$-free tournament” and show the
existence of a certain oriented tree which is almost spanning. The proofs of
Theorems 1 and 2 are deliverd in Section 4.

##  2 Preliminaries

###  2.1 Related notions

Let $G$ be an undirected graph. For each $U\subseteq V(G)$, we write $G-U$ for
$G[V(G)\setminus U]$. If $U=\\{v\\}$ is a singleton, we write $G-v$ rather
than $G-\\{v\\}$. Instead of $G-V(G^{\prime})$ we simply write $G-G^{\prime}$.
For a set of edges $F$, we define $G-F:=(V(G),E(G)\setminus F)$ and
$G+F:=(V(G)\cup V(F),E(G)\cup F)$; as above, $G-\\{e\\}$ and $G+\\{e\\}$ are
abbreviated to $G-e$ and $G+e$. Let $P$ be a path in $G$. The length of $P$ is
the number of edges on $P$.

Let $G$ be an edge-colored graph. Denote by $col(e)$ and $col(G)$,
respectively, the color of an edge $e$ and the set of colors assigned to
$E(G)$. For a vertex $v\in V(G)$, the color degree of $v$ in $G$, denoted by
$d^{c}_{G}(v)$ is the number of distinct colors assigned to the edges incident
to $v$. We use $\delta^{c}(G)=\min\\{d^{c}_{G}(v):v\in V(G)\\}$ to denote the
_minimum color degree_ of $G$, and $\Delta^{mon}_{G}(v)=\max_{c\in
col(G)}|\\{u\in V(G)\setminus\\{v\\}:col(uv)=c\\}|$ to denote the _maximum
monochromatic degree_ of $v$. For two disjoint subsets $V_{1}$ and $V_{2}$ of
$V(G)$, denote by $col(V_{1},V_{2})$ the set of colors appearing on the edges
between $V_{1}$ and $V_{2}$ in $G$. When $V_{1}=\\{v\\}$, use $col(v,V_{2})$
to denote $col(\\{v\\},V_{2})$.

Let $D$ be a directed graph. We use $V(D)$ and $A(D)$ to denote the vertex set
and the arc set of $D$. If $uv\in A(D)$, then we say $u$ dominates $v$, and
denote it by $u\rightarrow v$. For two disjoint subsets $X$, $Y$ of $V(D)$, if
each arc $uv$ between $X$ and $Y$ satisfies that $u\in X$ and $v\in Y$, then
we say $X\rightarrow Y$. For a vertex $u\in V(D)$, denote by $N^{+}_{D}(u)$
the set of vertices that are dominated by $u$, and denote by $N^{-}_{D}(u)$
the set of vertices that are dominating $u$. The cardinality of $N^{+}_{D}(u)$
and $N^{-}_{D}(u)$ are denoted by $d^{+}_{D}(u)$ and $d^{-}_{D}(u)$,
respectively. When this is no ambiguity, we often omit the subscript $D$.

For other notations and terminologies not defined here, we refer the reader to
[9].

###  2.2 Extensible structures

The main challenge for embedding PC spanning trees is to merge pieces of PC
structures together. We find the following configurations can be used as glue
for extending a PC path with certain constraints.

######  Definition 1 (Center edge of a colored triangle).

Let $S$ be an edge-colored triangle, if $col(e)\not\in col(S-e)$ for an edge
$e$ in $S$, then we say $e$ is a center edge of $S$.

Apparently, every rainbow triangle contains $3$ center edges, every 2-colored
triangle contains a unique center edge and every monochromatic triangle
contains no center edge.

######  Definition 2 (Nice $t$-shovel).

Let $Y$ be an edge-colored graph, consisting of a path $P=w_{1}w_{2}\cdots
w_{t}~{}(t\geq 1)$ and a triangle $S=u_{1}u_{2}u_{3}u_{1}$ with $V(P)\cap
V(S)=\\{w_{1}\\}=\\{u_{1}\\}$, as shown in the Figure 1(a). We call $Y$ a
$t$-shovel. If $P$ is a PC path, $u_{2}u_{3}$ is a center edge of $S$ and
$col(w_{1}w_{2})\not\in col\left(w_{1},\\{u_{2},u_{3}\\}\right)$, then we say
$Y$ is a nice $t$-shovel. For a nice $t$-shovel $Y$ with $t\geq 2$, we call
$u_{1}=w_{1}$ the center of $Y$.

######  Definition 3 (Nice bowtie).

Let $F_{1}$ be a graph obtained by identifying one vertex of two disjoint
triangles (see Figure 1(b)) and let $F_{2}$ be a graph obtained by adding an
edge between two disjoint triangles (see Figure 1(c)). Then we call both
$F_{1}$ and $F_{2}$ bowtie. To be specific, we say $F_{1}$ is a short bowtie
and $F_{2}$ is a long bowtie. Let $F_{1}$ and $F_{2}$ be labeled as Figure
1(b) and Figure 1(c). We say $u_{0}$ is the center of $F_{1}$ and
$u_{3},u_{4}$ are centers of $F_{2}$. If $u_{1}u_{2}$ and $u_{3}u_{4}$ in
$F_{1}$ are center edges of their lying triangles and
$col(u_{0},\\{u_{1},u_{2}\\})\cap col(u_{0},\\{u_{3},u_{4}\\})=\emptyset$,
then we say $F_{1}$ is a nice short bowtie (or nice bowtie). If
$F_{2}-\\{v_{1},v_{2}\\}$ and $F_{2}-\\{v_{5},v_{6}\\}$ are nice shovels, then
we say $F_{2}$ is a nice long bowtie (or nice bowtie).

(a) A $t$-shovel

(b) A short bowtie $F_{1}$ with $u_{0}$ as a center

(c) A long bowtie $F_{2}$ with $v_{3}$ and $v_{4}$ as centers

Figure 1: Extensible structures

The following lemmas are useful in the proofs of the main theorems.

######  Lemma 1.

Let $G$ be a mono-$C_{3}$-free edge-colored $K_{n}$ and let
$P=v_{1}v_{2}\cdots v_{t}$ be a PC path in $G$ with $t\geq 2$. If a vertex
$v\in V(G)\setminus V(P)$ satisfies $col(vv_{i})=col(v_{i}v_{i+1})$ for some
$i\in[1,t-1]$, then there exists $j\in[i,t-1]$ such that $Q=v_{1}v_{2}\cdots
v_{j}vv_{j+1}\cdots v_{t}$ is a PC path with $col(vv_{j})=col(v_{j}v_{j+1})$.

###### Proof.

Let $j$ be the largest integer in $[1,t-1]$ satisfying
$col(vv_{j})=col(v_{j}v_{j+1})$. Then $j\geq i$. Since $vv_{j}v_{j+1}v$ is not
a monochromatic $C_{3}$, we have $col(vv_{j})\neq col(vv_{j+1})$. If $j=t-1$,
then $Q=v_{1}v_{2}\cdots v_{t-1}vv_{t}$ is a desired PC path. If $j\leq t-2$,
then by the maximality of $j$, we have $col(vv_{j+1})\neq
col(v_{j+1}v_{j+2})$, which implies $Q=v_{1}v_{2}\cdots v_{j}vv_{j+1}\cdots
v_{t}$ is a desired PC path. ∎

######  Lemma 2.

Let $G$ be a mono-$C_{3}$-free edge-colored $K_{n}$. Then for each vertex
$v\in V(G)$, there is a PC Hamilton path in $G$ starting at $v$.

###### Proof.

Fix a vertex $v$, let $P=v_{1}v_{2}\cdots v_{t}$ be a longest PC path in $G$
with $v_{t}=v$. Suppose, to the contrary, that $P$ is not a Hamilton path.
Then for a vertex $u\in V(G)\setminus V(P)$, there holds
$col(uv_{1})=col(v_{1}v_{2})$. Apply Lemma 1 to the pair $(P,u)$. We get a
longer PC path starting at $v_{t}=v$, a contradiction. ∎

######  Lemma 3 (Spanning nice shovel).

Let $G$ be a mono-$C_{3}$-free edge-colored $K_{n}$ with $n\geq 3$. Then $G$
contains a spanning subgraph which is a nice $(n-2)$-shovel.

###### Proof.

When $n=3$, it is trivial. When $n=4$, if $G$ has a vertex $v$ satisfying
$d^{c}(v)=2$ or $G$ is a PC graph, then we can obtain a nice shovel
immediately. Otherwise since no monochromatic triangle exists, $G$ has only
one vertex of color degree 1 and three vertices of color degree 3, which also
implies the existence of a spanning nice shovel.

Now consider the case $n\geq 5$. Let $Y$ be a largest PC shovel contained in
$G$ with $S=u_{1}u_{2}u_{3}u_{1}$ being the triangle in $Y$, $u_{1}=w_{1}$ and
$P=w_{1}w_{2}\cdots w_{t}$ being the remaining path in $Y$. The above analysis
implies $t\geq 2$. Suppose that $V(Y)\neq V(G)$. Let $v$ be a vertex in
$V(G)\setminus V(Y)$.

######  Case 1.

$col(vu_{1})\not\in col(u_{1},\\{u_{2},u_{3}\\})$.

For each $j\in[1,t-1]$, define $P_{j}=w_{1}w_{2}\cdots w_{j}vw_{j+1}\cdots
w_{t}$ and define $P_{t}=w_{1}w_{2}\cdots w_{t}v$. If $P_{j}$ is a PC path for
some $j\in[2,t]$, then $P_{j}$ and the triangle $u_{1}u_{2}u_{3}u_{1}$ form a
nice shovel larger than $Y$, a contradiction. So none of the paths
$P_{t},P_{t-1},\ldots,P_{2}$ is a PC path. This implies that
$col(vw_{j})=col(w_{j}w_{j-1})$ for all $j\in[2,t]$. Since the triangle
$vw_{2}w_{1}v$ is not monochromatic we have $col(vw_{2})\neq col(vw_{1})$.
Therefore $P_{1}=w_{1}vw_{2}\cdots w_{t}$ and the triangle
$u_{1}u_{2}u_{3}u_{1}$ form a nice shovel larger than $Y$, a contradiction.

######  Case 2.

$col(vu_{1})\in col(u_{1},\\{u_{2},u_{3}\\})$.

Without loss of generality, assume that $col(vu_{1})=col(u_{1}u_{2})=\alpha$.
For each $j\in[2,t-1]$, define $P_{j}=w_{1}w_{2}\cdots w_{j}u_{3}w_{j+1}\cdots
w_{t}$ and define $P_{t}=w_{1}w_{2}\cdots w_{t}u_{3}$. If $P_{j}$ is a PC path
for some $j\in[2,t]$, then $P_{j}$ and the triangle $u_{1}u_{2}vu_{1}$ form a
nice shovel larger than $Y$, a contradiction. So none of the paths
$P_{t},P_{t-1},\ldots,P_{2}$ is a PC path. This implies that
$col(u_{3}w_{j})=col(w_{j}w_{j-1})$ for all $j\in[2,t]$. Since the triangle
$u_{3}w_{2}w_{1}u_{3}$ is not monochromatic we have $col(u_{3}w_{2})\neq
col(u_{3}w_{1})$. If $col(u_{3}w_{1})\neq\alpha$, then
$P_{1}=w_{1}u_{3}w_{2}\cdots w_{t}$ and the triangle $u_{1}u_{2}vu_{1}$ form a
nice shovel larger than $Y$(see Figure 2(a)), a contradiction. Therefore
$col(u_{3}w_{1})=col(u_{2}w_{1})=col(vw_{1})=\alpha$ and $\alpha\neq
col(w_{1}w_{2})$. Now consider the triangle $vu_{2}u_{3}v$. None of the three
edges in the triangle is of color $\alpha$ (otherwise together with $u_{1}$,
we get a monochromatic triangle). Without loss of generality, assume
$u_{2}u_{3}$ is a center edge of the triangle $vu_{2}u_{3}v$. Then
$P_{1}=vw_{1}w_{2}\cdots w_{t}$ and the triangle $vu_{2}u_{3}v$ form a nice
shovel larger than $Y$(see Figure 2(b)), a contradiction.

(a) $col(u_{3}u_{1})\neq\alpha$

(b) $col(u_{3}u_{1})=\alpha$

Figure 2: Cases for a larger nice shovel

∎

######  Lemma 4.

Let $G$ be a mono-$C_{3}$-free edge-colored $K_{n}$. Let $S$ and $Y$ be
vertex-disjoint subgraphs of $G$ such that $S=u_{1}u_{2}u_{3}u_{1}$ is a
triangle with $u_{2}u_{3}$ being a center edge and $Y$ is a nice shovel or a
vertex set of size at most 2. Then $G$ contains a PC path $P=z_{1}z_{2}\cdots
z_{\ell}$ such that $V(P)=V(S)\cup V(Y)$, $z_{1}=u_{1}$ and
$col(z_{1}z_{2})\in col(u_{1},\\{u_{2},u_{3}\\})$.

###### Proof.

We leave the easy case $|Y|\leq 2$ to be checked by readers. Now assume that
$Y$ is a nice shovel. Let $S^{\prime}=v_{1}v_{2}v_{3}v_{1}$ be the unique
triangle in $Y$ with $v_{2}v_{3}$ being the center edge. Let $w_{1}=v_{1}$ and
$w_{1}w_{2}\cdots w_{t}$ be the unique Hamilton path in $Y-\\{v_{2},v_{3}\\}$.
Let $col(u_{2}u_{3})=c_{1}$ and $col(v_{2}v_{3})=c_{2}$. If there is an edge
between $\\{u_{2},u_{3}\\}$ and $\\{v_{2},v_{3}\\}$ assigned a color distinct
to both $c_{1}$ and $c_{2}$, then a desired PC path can be found immediately.
This argument, together with the mono-$C_{3}$-free condition, implies that
$col(u_{2}u_{3})\neq col(v_{2}v_{3})$. Without loss of generality, assume
$col(u_{2}u_{3})=1$, $col(v_{2}v_{3})=2$ and $col(u_{2}v_{2})=1$. The
mono-$C_{3}$-free condition again forces $col(u_{3}v_{2})=2$,
$col(u_{3}v_{3})=1$ and $col(u_{2}v_{3})=2$ (see Figure 3).

Figure 3: Colors between $S$ and $Y$

If $col(u_{1}u_{2})\neq 2$ or $col(v_{1}v_{3})\neq 1$, then
$u_{1}u_{2}v_{3}u_{3}v_{2}v_{1}w_{2}\cdots w_{t}$ or
$u_{1}u_{2}v_{2}u_{3}v_{3}v_{1}w_{2}\cdots w_{t}$ is a desired PC path. For
the remaining case that $col(u_{1}u_{2})=2$ and $col(v_{1}v_{3})=1$, we
consider the PC path $P_{1}=v_{3}v_{1}w_{2}\cdots w_{t}$. Since
$col(u_{3}v_{3})=col(v_{3}v_{1})=1$, by Lemma 1, $G$ contains a PC path
$P^{\prime}_{1}=x_{1}x_{2}\cdots x_{t+2}$, where
$V(P_{1}^{\prime})=V(P_{1})\cup\\{u_{3}\\}$, $x_{1}=v_{3}$ and
$col(x_{1}x_{2})=col(v_{3}v_{1})$. Then $u_{1}u_{2}v_{2}x_{1}x_{2}\cdots
x_{t+2}$ is a desired PC path. This complets the proof. ∎

##  3 Directed almost spanning trees in mono-$C_{3}$-free tournament

Let $G$ be an edge-colored graph. If there is a function $h:V(G)\rightarrow
col(G)$ such that $col(uv)=h(u)$ or $h(v)$ for each edge $uv\in E(G)$. Then we
can define a directed graph $D_{G}$ with $V(D_{G})=V(G)$ and $uv\in A(D_{G})$
if and only if $col(uv)=h(u)$ and $col(uv)\neq h(v)$. Such an edge-colored
graph $G$ is called “degenerate” in [24]. An easy observation in [23] states
that each PC cycle in $G$ must be a directed cycle in $D_{G}$ and vise versa.
This one-to-one relationship does not hold if we study paths or trees instead
of cycles. One can easily check that a PC path in $G$ is not necessarily a
directed path in $D_{G}$. However, certain oriented trees in $D_{G}$
correspond to PC trees in $G$.

Let $G$ be a mono-$C_{3}$-free edge-colored $K_{n}$. When $G$ is degenerate,
we will see that $D_{G}$ acts like a tournament. In the following, we define
such a digraph and obtain an oriented-tree-embedding result by several lemmas.
This embedding result is applied in the proof of Theorem 2.

######  Definition 4.

Given $t\geq 2$, let $D$ be a multipartite tournament such that each partite
set has at most 2 vertices and $N^{+}\left(x\right)\cap
N^{+}\left(y\right)=\emptyset$ for every pair of distinct vertices $x$ and $y$
from a same partite set. Then we say $D$ is a mono-$C_{3}$-free tournament.

######  Lemma 5 (Li [22]).

Given $t\geq 2$, let $D$ be a strongly connected mono-$C_{3}$-free tournament
with $|V(D)|\geq 4$, then each vertex of $D$ is contained in directed cycles
of lengths from $4$ to $|V(D)|$.

######  Lemma 6.

Given $t\geq 2$, let $D$ be a mono-$C_{3}$-free tournament. Let
$D_{0},D_{1},\ldots,D_{p}$ ($p\geq 0$) be strongly connected components of $D$
such that for $0\leq i<j\leq p$, either $D_{j}\rightarrow D_{i}$ or there is
no arc between $D_{i}$ and $D_{j}$. If $|V(D)|\geq 3$, then the following
statements hold.
$(a)$ If $p=0$, then $D$ contains a directed Hamilton cycle.
$(b)$ If $p\geq 1$ and $|N^{+}_{D}(v)|\geq 1$ for all $v\in V(D)$, then each
partite set of size $2$ is contained in $D_{0}$, $D-D_{0}$ is a tournament and
$D_{j}\rightarrow D_{i}$ for $0\leq i<j\leq p$.
$(c)$ If $|N^{+}_{D}(v)|\geq 1$ for all $v\in V(D)$, then $D$ contains a
directed Hamilton path.
$(d)$ If there are at least two partite sets of size $2$ in $D$, then all the
partite sets of size $2$ are contained in $D_{0}$, $D-D_{0}$ is a tournament
and $D_{j}\rightarrow D_{i}$ for $0\leq i<j\leq p$.

###### Proof.

The case $|V(D)|=3$ can be verified immediately. Assume $|V(D)|\geq 4$. Then
the statement $(a)$ holds by Lemma 5. To prove $(b)$, suppose that some
partite set $W=\\{x,y\\}$ is not contained in $D_{0}$. If $W\cap
V(D_{0})=\emptyset$, then each $z\in V(D_{0})$ must be a common out-neighbour
of $x$ and $y$, a contradiction. If $W\cap V(D_{0})\neq\emptyset$, say $W\cap
V(D_{0})=\\{x\\}$ and $y\in D_{i}$ for some $i\in[1,p]$, then by the condition
that $|N^{+}_{D}(x)|\geq 1$, there must be a vertex $z\in V(D_{0})$ such that
$x\rightarrow z$. Note that $D$ is a multipartite tournament, we have
$y\rightarrow z$, a contradiction. Therefore each partite set of size $2$ is
contained in $D_{0}$, which implies that $D-D_{0}$ is a tournament and
$D_{j}\rightarrow D_{i}$ for $0\leq i<j\leq p$. So the statement $(b)$ holds.
The statement $(c)$ can be obtained directly by statements $(a)$ and $(b)$. To
prove $(d)$, assume that $W_{1},W_{2},\ldots,W_{s}$ are partite sets of size
$2$ in $D$ with $s\geq 2$ and $W_{i}=\\{x_{i},y_{i}\\}$ $(i\in[1,s])$. For
distinct indices $a$ and $b$ in $[1,s]$, let $D^{\prime}=D[W_{a}\cup W_{b}]$.
If there is a vertex $v\in V(D^{\prime})$ such that $d^{-}_{D^{\prime}}(v)=2$,
then either $v\in N^{+}(x_{a})\cap N^{+}(y_{a})$ or $v\in N^{+}(x_{b})\cap
N^{+}(y_{b})$, a contradiction. So $D^{\prime}$ must be a directed cycle of
length $4$. By the arbitrariness of $a$ and $b$, we know that
$D[\cup^{s}_{i=1}W_{i}]$ is a strongly connected digraph. Therefore
$D[\cup^{s}_{i=1}W_{i}]\subseteq D_{0}$ (otherwise each vertex $v\in V(D_{0})$
is in $N^{+}(x_{i})\cap N^{+}(y_{i})$ for every $W_{i}$), which implies that
$D-D_{0}$ is a tournament and $D_{j}\rightarrow D_{i}$ for $0\leq i<j\leq p$.
So the statement $(d)$ holds. ∎

######  Lemma 7.

Let $D$ be a mono-$C_{3}$-free tournament. Let ${P}=v_{1}v_{2}\cdots v_{t}$ be
a directed path in $D$. Assume there exists a vertex $v\in V(D)\setminus
V({P})$ such that $v\rightarrow v_{i}$ for some $i\in[1,t]$. Then $D$ contains
a directed path ${P^{\prime}}=u_{1}u_{2}\cdots u_{t+1}$, where
$V({P^{\prime}})=V({P})\cup\\{v\\}$ and $u_{t+1}=v_{t}$.

###### Proof.

Let $j$ be a minimum integer in $[1,t]$ such that $v\rightarrow v_{j}$. If
$j=1$, then ${P^{\prime}}=vv_{1}\cdots v_{t-1}v_{t}$ is a desired directed
path. If $j\geq 2$, then $v_{j}\in N^{+}(v)\cap N^{+}(v_{j-1})$. This implies
that $v$ and $v_{j-1}$ belong to distinct partite set. By the assumption of
$j$, we have $vv_{j-1}\not\in A(D)$. Therefore $v_{j-1}\rightarrow v$ and
${P^{\prime}}=v_{1}\cdots v_{j-1}vv_{j}v_{j+1}\cdots v_{t}$ is a directed path
in $D$. ∎

Given positive integers $\\{l_{i}\\}^{k}_{i=2}(k\geq 2)$, let $P_{i}$ be a
directed path of length $l_{i}$ from $u_{i}$ to $u$ for each $i\in[2,k]$,
satisfying $V(P_{i})\cap V(P_{j})=\\{u\\}$ for $2\leq i<j\leq k$. Let $x,y$ be
two vertices not in $\cup^{k}_{i=2}V(P_{i})$. Define a directed tree
$T^{*}_{l_{2},\ldots,l_{k}}$ (see Figure 4) as

$V(T^{*}_{l_{2},\ldots,l_{k}})=\\{x,y\\}\cup\bigcup_{i=2}^{k}V(P_{i})\text{~{}~{}and~{}~{}}A(T^{*}_{l_{2},\ldots,l_{k}})=\\{ux,uy\\}\cup\bigcup_{i=2}^{k}A(P_{i}).$

We call $u$ the root of $T^{*}_{l_{2},\ldots,l_{k}}$.

Figure 4: The tree $T^{*}_{3,3,2,1}$

######  Theorem 3.

For $k\geq 2$ and $\ell_{2}\geq\ell_{3}\geq\cdots\geq\ell_{k}\geq 1$, let $D$
be a mono-$C_{3}$-free tournament on
$n\geq\sum^{k}_{i=2}{\ell_{i}}+2k^{2}+2k+6$ vertices. If $|N^{+}_{D}(v)|\geq
2$ for all $v\in V(D)$. Then $D$ contains a subgraph isomorphic to
$T^{*}_{\ell_{2},\ldots,\ell_{k}}$.

###### Proof.

We use $D_{0},D_{1}\ldots,D_{p}$ to denote the strongly connected components
of $D$. Let $U=V(D)\setminus V(D_{0})$. If $|U|\geq\sum_{i=2}^{k}{\ell_{i}}$,
then $p\geq 1$ and by Lemma 6(b), we can assume that $D_{j}\rightarrow D_{i}$
for $0\leq i<j\leq p$ and $D[U]$ is a tournament with $P$ being a directed
Hamilton path in $D[U]$. Decompose $P$ into $k-1$ vertices disjoint directed
paths $P_{2},P_{3},\ldots,P_{k}$ ending at $v_{2},v_{3},\ldots,v_{k}$ of
length $\ell_{2}-1,\ell_{3}-1,\ldots,\ell_{k}-1$, respectively. Take a vertex
$v_{0}\in D_{0}$. Then $v_{i}\rightarrow v_{0}$ for all $2\leq i\leq k$. Since
$|N^{+}(v_{0})|>2$, there are two distinct vertices $x,y\in D_{0}$ satisfying
$v_{0}\rightarrow x$ and $v_{0}\rightarrow y$. Those paths and together with
$x,y,v_{0}$ form a tree $T^{*}_{\ell_{2},\ldots,\ell_{k}}$. The remaining case
is $|U|<\sum_{i=2}^{k}{\ell_{i}}$. Take $k-1$ integers
$\ell^{\prime}_{2},\ldots,\ell^{\prime}_{k}$ such that
$0\leq\ell^{\prime}_{i}\leq\ell_{i}$ for each $i\in[2,k]$ and
$\sum_{i=2}^{k}{\ell^{\prime}_{i}}+|U|=\sum_{i=2}^{k}{\ell_{i}}$. Then
$|V(D_{0})|\geq\sum_{i=2}^{k}{\ell^{\prime}_{i}}+2k^{2}+2k+6$.

######  Claim 1.

If $D_{0}$ contains a subgraph $T_{1}$ isomorphic to
$T^{*}_{\ell^{\prime}_{2},\ldots,\ell^{\prime}_{k}}$, then $D$ contains a
subgraph isomorphic to $T^{*}_{\ell_{2},\ldots,\ell_{k}}$.

###### Proof.

Denote by $u$ the root of $T_{1}$ and by $u_{2},\ldots,u_{k}$ the $k$ leafs of
$T_{1}$ with $d^{-}_{T_{1}}(u_{i})=0$ for $2\leq i\leq k$. Define
$r_{i}=\ell_{i}-\ell^{\prime}_{i}$ for $i\in[2,k]$. Since
$|U|=\sum_{i=2}^{k}r_{i}$ and $D[U]$ is a tournament (by Lemma 6(b)), $U$ can
be partitioned into $k-1$ parts such that the $i$-th part is a tournament of
order $r_{i}$. Note that for every pair of vertices $u\in U$ and $v\in D_{0}$,
we have $u\rightarrow v$. Hence $T_{1}$ can be extended into a tree
$T^{*}_{\ell_{2},\ldots,\ell_{k}}$ by vertices in $U$. ∎

By Claim 1, it remains to prove that $D_{0}$ contains a
$T^{*}_{\ell^{\prime}_{2},\ldots,\ell^{\prime}_{k}}$ as a subgraph. Without
loss of generality, assume that $\ell^{\prime}_{i}\geq 1$ for $i\in[2,t]$. Let
$v$ be a vertex with minimum out-degree in $D_{0}$. Let $A=N^{+}_{D_{0}}(v)$
and $B=N^{-}_{D_{0}}(v)$. Then $|A|\leq\frac{|D_{0}|-1}{2}$. Since each vertex
in $D_{0}$ is adjacent to at least $|D_{0}|-2$ vertices, we have

$|B|\geq|D_{0}|-2-|A|\geq|D_{0}|-2-\frac{|D_{0}|-1}{2}\geq\frac{|D_{0}|-3}{2}\geq
k^{2}+k+1.$ (1)

If $|B|\geq\sum_{i=2}^{k}\ell^{\prime}_{i}$, then let $P$ be a longest
directed path in $D_{0}[B\cup\\{v\\}]$ with $v$ being the ending vertex. By
Lemma 7, $P$ is a directed Hamilton path in $D_{0}[B\cup\\{v\\}]$. Decompose
$P$ into disjoint directed paths $P_{2},\ldots,P_{k}$ ending at
$v_{2},v_{3},\ldots,v_{k}$ of lengths
$\ell^{\prime}_{2}-1,\ell^{\prime}_{3}-1,\ldots,\ell^{\prime}_{k}-1$,
respectively. Recall that $|N^{+}_{D}(v)|\geq 2$ and
$N^{+}_{D}(v)=N^{+}_{D_{0}}(v)=A$. There are two distinct vertices $x,y\in
A=N^{+}(v)$. Note that $\\{v_{2},v_{3},\ldots,v_{k}\\}\subseteq N^{-}(v)$. We
get a $T^{*}_{\ell^{\prime}_{2},\ldots,\ell^{\prime}_{k}}$ as
$(\cup_{i\in[2,k]}(P_{i}+v_{i}v))\cup\\{uw_{1},uw_{2}\\}$.

Now we assume $|B|\leq\sum_{i=2}^{k}\ell^{\prime}_{i}-1$. This implies

$|A|\geq|D_{0}|-2-|B|\geq 2k^{2}+2k+4+\sum_{i=2}^{k}\ell^{\prime}_{i}-|B|\geq
2k^{2}+2k+5.$ (2)

######  Claim 2.

If $D_{0}[A]$ contains $k-1$ disjoint directed paths
$P_{2},P_{3},\ldots,P_{k}$ ending at vertices $a_{2},a_{3},\ldots a_{k}$
respectively and satisfying the following conditions:
$(i)$ $1\leq|P_{i}|\leq\max\\{\ell_{i}^{\prime}-1,1\\}$ and
$d^{+}_{B}(a_{i})\geq k-1$ for $2\leq i\leq k$;
$(ii)$ there is a set $W\subseteq A\setminus\cup_{i=1}^{k}V(P_{i})$ with
$w\rightarrow z$ for every $w\in W$ and every $z\in\cup_{i=1}^{k}V(P_{i})$ or
$W=\emptyset$ such that

$|W|+\sum_{i=2}^{k}|P_{i}|+|B|\geq\sum_{i=2}^{k}\max\\{\ell^{\prime}_{i},2\\},$

then $D_{0}$ contains a $T^{*}_{q_{2},\ldots,q_{k}}$. Here
$q_{i}=\max\\{\ell^{\prime}_{i},2\\}$ for $2\leq i\leq k$.

###### Proof.

Condition $(i)$ tells the existence of a $k-1$ matching $\\{a_{i}b_{i}:2\leq
i\leq k\\}$ for a set $\\{b_{i}:2\leq i\leq k\\}\subseteq B$. Let $u_{i}$ be
the starting vertex of $P_{i}$ and let $L_{i}=u_{i}P_{i}a_{i}b_{i}v$ for
$2\leq i\leq k$. Apparently $L_{i}$ is a directed path of length between $2$
and $\max\\{\ell^{\prime}_{i},2\\}$. We assert that for each vertex
$x\in(W\cup B)\setminus\\{b_{i}:2\leq i\leq k\\}$ and each $L_{i}$, there is a
vertex $y^{x}_{i}\in V(L_{i})$ such that $x\rightarrow y^{x}_{i}$. This can be
done by setting $y^{x}_{i}=v$ when $x\in B\setminus\\{b_{i}:2\leq i\leq k\\}$
and setting $y^{x}_{i}=a_{i}$ when $x\in W$. Note that
$|W|+\sum_{i=2}^{k}|P_{i}|+|B|\geq\sum_{i=2}^{k}\max\\{\ell^{\prime}_{i},2\\}.$
By Lemma 7, we can extend each path $L_{i}$ first by vertices in
$B\setminus\\{b_{i}:2\leq i\leq k\\}$ and then by vertices in $W$ until each
leg reach a length of $\max\\{\ell^{\prime}_{i},2\\}$. Recall that $|A|\geq
2k^{2}+2k+4+\sum_{i=2}^{k}\ell^{\prime}_{i}-|B|$. There are at least $2k^{2}$
vertices in $A$ not added into legs. Choose two of them as out-neighbors of
$v$. Then we find a $T^{*}_{q_{2},\ldots,q_{k}}$. ∎

To satisfy the condition of Claim 2, we need to analyse the structure of
$D_{0}[A]$. If $D_{0}[A]$ is a tournament or $D_{0}[A]$ has at least two
partite sets of size two, then set $A^{\prime}=A$. If there is exactly one
partite set of size two contained in $D_{0}[A]$, say $W=\\{x,y\\}$, then set
$A^{\prime}=A-x$. In both cases, we can assume that
$Q_{1},Q_{2},\ldots,Q_{t}(t\geq 1)$ are strongly connected components of
$D_{0}[A^{\prime}]$ with $Q_{j}\rightarrow Q_{i}$ for $1\leq i<j\leq t$ (by
Lemma 6), $A^{\prime}\subset A$ and $|A^{\prime}|\geq|A|-1\geq 2k^{2}+2k+4$.
Now we analyse $D_{0}[A^{\prime}]$ instead of $D_{0}[A]$. The following claim
tells that either some $Q_{j}$ is large or there is an index $j$ such that
both $\sum_{i\leq j}|Q_{i}|$ and $\sum_{i>j}|Q_{i}|$ are large.

######  Claim 3.

There exists some $j\in[1,t]$ such that one of the following holds
$(i)$ $\sum_{i=1}^{j}|Q_{i}|\geq k-1$ and $\sum_{i=j+1}^{t}|Q_{i}|\geq k-1$;
$(ii)$ $|Q_{j}|\geq|A^{\prime}|-2k+4$;

###### Proof.

Recall that $|A^{\prime}|\geq 2k^{2}+2k+4$. Let $j$ be the smallest index in
$[1,t]$ such that $\sum_{i=1}^{j}|Q_{i}|\geq k-1$. So
$\sum_{i=1}^{j-1}|Q_{i}|\leq k-2$. If $(i)$ does not hold, then
$\sum_{i=j+1}^{t}|Q_{i}|\leq k-2$. Therefore

$|Q_{j}|\geq|A^{\prime}|-\sum_{i=j+1}^{t}|Q_{i}|-\sum_{i=1}^{j-1}|Q_{i}|\geq|A^{\prime}|-(k-2)-(k-2)=|A^{\prime}|-2k+4.$

∎

Now we proceed the proof by analyzing the two cases in Claim 3.

######  Case 1.

There exists some $j\in[1,t]$ such that $\sum_{i=1}^{j}|Q_{i}|\geq k-1$ and
$\sum_{i=j+1}^{t}|Q_{i}|\geq k-1$

In this case, apply Lemma 6(c) to $D_{0}[\cup_{i=1}^{j}Q_{i}]$, we get a
directed Hamilton path $P$ in $D_{0}[\cup_{i=1}^{j}Q_{i}]$. Note that
$N^{+}_{D_{0}}(z)\subseteq B\cup\left(\cup_{i=1}^{j}Q_{i}\right)=B\cup V(P)$
for each vertex $z\in V(P)$ and $v$ is a vertex in $D_{0}$ with minimum out-
degree. We have

$d^{+}_{D_{0}}(z,B)\geq d^{+}_{D_{0}}(z)-|P|\geq
d^{+}_{D_{0}}(v)-|P|=|A|-\sum_{i=1}^{j}|Q_{i}|\geq\sum_{i=j+1}^{t}|Q_{i}|\geq
k-1.$

Set $W:=\cup_{i=j+1}^{t}Q_{i}.$ If
$|P|\geq\sum_{i=2}^{k}\max\\{\ell^{\prime}_{i}-1,1\\}$, then find $k-1$
disjoint paths $P_{2},P_{2},\ldots,P_{k}$ in $P$ such that
$|P_{i}|=\max\\{\ell^{\prime}_{i}-1,1\\}$ for $i\in[2,k]$. Then

$|W|+\sum_{i=2}^{k}|P_{i}|+|B|>\sum_{i=2}^{k}|P_{i}|+k-1\geq\sum_{i=2}^{k}\max\\{\ell^{\prime}_{i},2\\}.$

If $|P|<\sum_{i=2}^{k}\max\\{\ell^{\prime}_{i}-1,1\\}$, then let
$P_{2},P_{3},\ldots,P_{k}$ be a decomposition of $P$ into $k-1$ disjoint paths
such that $1\leq|P_{i}|\leq\max\\{\ell^{\prime}_{i}-1,1\\}$ for $i\in[2,k]$
(this is possible since $|P|=\sum_{i=1}^{j}|Q_{i}|\geq k-1$). By (2), we have

$|W|+\sum_{i=2}^{k}|P_{i}|+|B|=|A^{\prime}|+|B|\geq\sum_{i=2}^{k}\ell^{\prime}_{i}+2k^{2}+2k+3>\sum_{i=2}^{k}\max\\{\ell^{\prime}_{i},2\\}.$

In both situations, we obtain a tree
$T^{*}_{\ell^{\prime}_{2},\ldots,\ell^{\prime}_{k}}$ by Claim 2.

######  Case 2.

There exists some $j\in[1,t]$ such that $|Q_{j}|\geq|A^{\prime}|-2k+4$.

In this case, by Lemma 5, $Q_{j}$ contains a directed Hamilton cycle
$C=w_{1}w_{2}\cdots w_{h}w_{1}$. Let $h_{2},h_{3},\ldots,h_{k}$ be positive
integers such that $h_{i}\leq\max\\{\ell^{\prime}_{i}-1,1\\}$ for $2\leq i\leq
k$, $\sum_{i=2}^{k}h_{i}\leq|C|=h$ and $\sum_{i=2}^{k}h_{i}$ is maximum. We
say a sequence of indices $(\alpha_{2},\alpha_{3},\ldots,\alpha_{k})$ is a
model on $C$ if $\alpha_{j+1}=\alpha_{j}+h_{j}$ for $2\leq j\leq k-1$. Here
the addition is on $\mathbb{Z}_{h}$. Given a model, we can find vertex
disjoint paths $P_{2},P_{3},\ldots,P_{k}$ such that $P_{i}$ is of length
$h_{i}-1$ and ending at the vertex $w_{\alpha_{i}}$. Note that
$\sum_{i=2}^{k}|P_{i}|\geq\min\left\\{h,\sum_{i=2}^{k}(\ell^{\prime}_{i}-1)\right\\}$.
We have

$\displaystyle\sum_{i=2}^{k}|P_{i}|+|B|$
$\displaystyle\geq\min\left\\{h,\sum_{i=2}^{k}(\ell^{\prime}_{i}-1)\right\\}+|B|$
$\displaystyle\geq\min\left\\{|A^{\prime}|-2k+4,\sum_{i=2}^{k}(\ell^{\prime}_{i}-1)\right\\}+|B|$
$\displaystyle\geq\min\left\\{|A|+|B|-2k+3,\sum_{i=2}^{k}(\ell^{\prime}_{i}-1)+|B|\right\\}.$

By (1) and (2), there holds
$\sum_{i=2}^{k}|P_{i}|+|B|\geq\sum_{i=2}^{k}\max\\{\ell^{\prime}_{i},2\\}$. If
there is a model $(\alpha_{2},\alpha_{3},\ldots,\alpha_{k})$ such that
$d^{+}_{D_{0}}(w_{\alpha_{i}},B)\geq k-1$ for $2\leq i\leq k$. We can obtain a
$T^{*}_{\ell^{\prime}_{2},\ldots,\ell^{\prime}_{k}}$ by Claim 2.

Now assume that for every model $(\alpha_{2},\alpha_{3},\ldots,\alpha_{k})$,
there exists a vertex $w_{\alpha_{i}}$ such that
$d^{+}_{D_{0}}(w_{\alpha_{i}},B)\leq k-2$. Let
$M_{0}=(\alpha_{2},\alpha_{3},\ldots,\alpha_{k})$ be a model on $C$. Define
$M_{j}=(\alpha_{2}+j,\alpha_{3}+j,\ldots,\alpha_{k}+j)$ for $1\leq j\leq h-1$.
Here the addition is on $\mathbb{Z}_{h}$. Then $M_{j}$ is also a model on $C$.
Let $\mathcal{M}=\\{M_{i}:0\leq i\leq h-1\\}$. Let

$X=\\{\alpha:d^{+}_{D_{0}}(w_{\alpha},B)\leq k-2\\}.$

Note that each $\alpha\in X$ lies in exactly $k-1$ models in $\mathcal{M}$,
and for each model $M_{i}$, there is at least one entry belonging to $X$.
Therefore

$|X|\geq\frac{|\mathcal{M}|}{k-1}=\frac{h}{k-1}\geq\frac{|A^{\prime}|-2k+4}{k-1}.$

Let $H$ be the induced subgraph of $D_{0}$ on $\\{w_{\alpha}:\alpha\in X\\}$.
Then there is a vertex $z$ in $H$ with $d_{H}^{+}(z)\leq\frac{|X|-1}{2}$. Then

$\displaystyle|A|=d^{+}_{D_{0}}(v)\leq d^{+}_{D_{0}}(z)$ $\displaystyle\leq
d^{+}_{H}(z)+|A\setminus X|+d^{+}_{D_{0}}(z,B)$
$\displaystyle\leq\frac{|X|-1}{2}+|A|-|X|+k-2.$

Hence $|X|\leq 2k-5$. Recall that
$|X|\geq\frac{|A^{\prime}|-2k+1}{k-1}\geq\frac{|A|-2k}{k-1}$. We get

$|A|\leq 2k^{2}-5k+5,$

which contradicts (2) that $|A|\geq 2k^{2}+2k+5$. The proof is complete. ∎

##  4 Proofs of Theorem 1 and 2

Recall that $g(S_{k},C_{3})$ is the maximum number $N$ such that there exists
an edge-colored $K_{N}$ containing neither a rainbow $S_{k}$ nor a
monochromatic $C_{3}$. We will use this notation to state the proofs of main
theorems.

######  Proposition 1.

$g(S_{k},C_{3})<(k+1)!$ for every integer $k\geq 1$.

###### Proof.

We prove by induction on $k$. When $k=1$, it is trivial. Assume that the
statement holds for $g(S_{k-1},C_{3})$. Let $G$ be a mono-$C_{3}$-free edge-
colored $K_{n}$ with $n\geq(k+1)!$. By the inductive hypothesis, $G$ contains
a rainbow $(k-1)$-star with $v$ being the vertex of degree $k-1$. If
$d^{c}_{G}(v)\geq k$, then the proof is complete. If $d^{c}_{G}(v)\leq k-1$,
then there exists a vertex set $W$ of size at least $\frac{(k+1)!-1}{k-1}\geq
k!$. Since $|W|\geq k!$, by the inductive hypothesis and the assumption that
$G$ is mono-$C_{3}$-free, $G[W]$ contains a rainbow $(k-1)$-star $T$ with $u$
being the center vertex of degree $k-1$. Note that $G$ has no monochromatic
triangle, we know that $col(v,W)\cap col(T)=\emptyset$. So $T+uv$ is a rainbow
$k$-star. ∎

######  Lemma 8.

Given a positive integer $k\geq 1$, let $G$ be a mono-$C_{3}$-free edge-
colored $K_{n}$ with $n\geq(k+2)!$, then $G$ contains a PC copy of every tree
of $k$ edges.

###### Proof.

By induction on $k$. The case $k=1$ can be verified immediately. Assuming that
the conclusion holds for every tree of $k-1$ edges. Let $T$ be a tree of $k$
edges with a leaf vertex $x$ and a pendent edge $xy$. Define $V_{0}=\\{v\in
V(G):d^{c}(v)\leq k-1\\}$ and $V_{1}=V(G)\setminus V_{0}$. Since $G[V_{0}]$
contains no rainbow $S_{k}$, by Proposition 1, we have $|V_{0}|<(k+1)!$.
Therefore $|V_{1}|>(k+2)!-(k+1)!>(k+1)!.$ By the inductive hypothesis,
$G[V_{1}]$ contains a subgraph $T^{\prime}$ which is a PC copy of $T-x$. Let
$\varphi:\ V(T)\setminus\\{x\\}\rightarrow V(T^{\prime})$ be an isomorphism
mapping from $T-x$ to $T^{\prime}$. Let $y^{\prime}=\varphi(y)$. By the
definition of $V_{1}$, we have $d^{c}_{G}(y^{\prime})\geq k$. Note that
$|T^{\prime}-y|\leq k-1$. There exists a vertex $x^{\prime}\in V(G)\setminus
V(T^{\prime})$ such that $col(y^{\prime}x^{\prime})\notin
col(y^{\prime},V(T^{\prime}))$. Hence $T^{\prime}+y^{\prime}x^{\prime}$ is a
PC copy of $T$ in $G$. The proof is complete. ∎

###### Proof of Theorem 1.

By Lemma 8, $G$ contains a PC copy of $T_{0}$. Denote by $T_{1}$ a maximal PC
subgraph of $G$ such that $T_{1}$ is a subdivision of $T_{0}$. If
$V(T_{1})=V(G)$, then we are done. Otherwise, for each edge $xy\in E(T_{1})$,
denote by $T_{1}(x,y)$ and $T_{1}(y,x)$ the two connected components of
$T_{1}-xy$ containing $x$ and $y$, respectively. For a vertex $u\in
V(G)\backslash V(T_{1})$, if $col(ux)=col(xy)$, then we say the triple
$(u,x,y)$ is compatible to $T_{1}$. By the assumption that $T_{1}$ is maximal,
for every leaf vertex $x$ and the pendent edge $xy$ in $T_{1}$, the triple
$(u,x,y)$ is compatible. Now let $(u,x,y)$ be a triple compatible to $T_{1}$
with $|T_{1}(y,x)|$ being the minimum (here $x$ may not be a leaf vertex).
Since $G$ is mono-$C_{3}$-free and $col(ux)=col(xy)$, we have $col(uy)\neq
col(ux)$. If $col(uy)\not\in col(y,N_{T_{1}(y,x)}(y))$, then $T_{1}-xy+xu+uy$
forms a PC subdivision of $T_{0}$ larger than $T_{1}$, a contradiction. Hence
there exists a vertex $z\in N_{T_{1}(y,x)}(y)$ with $col(uy)=col(yz)$. This
implies that $(u,y,z)$ is compatible to $T_{1}$ with
$|T_{1}(z,y)|<|T_{1}(y,x)|$, a contradiction. ∎

###### Proof of Theorem 2.

The proof is given by distinguishing the number of vertex-disjoint nice
bowties in $G$.

######  Case 1.

There are at least $g(S_{k},C_{3})+1$ vertex-disjoint nice bowties in $G$.

Let $B_{1},\cdots,B_{s}$ be vertex-disjoint nice bowties in $G$ with $s\geq
g(S_{k},C_{3})+1$ such that $G-\cup^{h}_{i=1}{V(B_{i})}$ contains no nice
bowtie. Pick one center $v_{i}$ from each bowtie $B_{i}$ ($1\leq i\leq s$) to
form a set $W$. Since $G$ is mono-$C_{3}$-free and $|W|\geq g(S_{k},C_{3})+1$,
there exists a rainbow $k$-star $S_{k}$ in $G[W]$. Without loss of generality,
assume $V(S_{k})=\\{v_{0},v_{1},v_{2},\ldots,v_{k}\\}$ and $v_{0}$ is the
$k$-degree vertex in $S_{k}$.

For $1\leq i\leq k$, since $v_{i}$ is a center vertex of the bowtie $B_{i}$,
there exists a subgraph $X_{i}\subseteq B_{i}$ such that $X_{i}+v_{i}v_{0}$ is
either a nice 2-shovel or a nice 3-shovel. Denote by $Y_{i}$ the nice shovel
$X_{i}+v_{i}v_{0}$. Then $Y_{1},Y_{2},\ldots,Y_{k}$ are disjoint shovels
overlapping at the vertex $v_{0}$. We will obtain a desired PC spider by
extending or shrinking these shovels.

Define $I=\\{1,2,\ldots,k\\}$ and $I^{-}=\\{i\in I:\ell_{i}\leq|Y_{i}|-1\\}$.
For each $i\in I^{-}$, we can modify $Y_{i}$ into a leg of length $\ell_{i}$
by removing $|Y_{i}|-1-\ell_{i}$ vertices. Let $R$ be the removed vertices.
Then $U=(V(G)\setminus\cup^{k}_{i=1}V(Y_{i}))\cup R$ is the set of vertices
waiting to be embedded. Note that $|U|=\sum_{i\in I\setminus
I^{-}}{(\ell_{i}-|Y_{i}|+1)}$. We partition $U$ into $|I\setminus I^{-}|$
disjoint sets $\\{U_{i}\\}_{i\in I\setminus I^{-}}$ such that
$|U_{i}|=\ell_{i}-|Y_{i}|+1$ for each $i\in I\setminus I^{-}$. Then by Lemma
3, each $G[U_{i}]$ of order at least $3$ contains a spanning nice shovel
$F_{i}$. Set $F_{i}=U_{i}$ when $|U_{i}|\leq 2$. Apply Lemma 4 to the triangle
in $Y_{i}$ and $F_{i}$ for all $i\in I\setminus I^{-}$, we get a desired PC
spanning tree in $G$.

######  Case 2.

The number of vertex-disjoint nice bowties in $G$ is at most $g(S_{k},C_{3})$.

In this case we will first find a structure that is almost the spider we want
except the first leg, which is a nice 1-shovel. Then we get the final spider
by extending this shovel into a leg of length $\ell_{1}$. To state the proof,
we need more definitions. Let $S$ be a spider with precisely $k-1$ legs of
lengths $\ell_{2},\ell_{3},\ldots,\ell_{k}$ respectively, let $Y$ be a
triangle and let $O^{*}_{\ell_{2},\ldots,\ell_{k}}$ be the graph obtained by
identifying a vertex in $Y$ with the center of $S$. We call
$O^{*}_{\ell_{2},\ldots,\ell_{k}}$ an octopus. The legs of
$O^{*}_{\ell_{2},\ldots,\ell_{k}}$ are exactly the legs of $S$. We say
$O^{*}_{\ell_{2},\ldots,\ell_{k}}$ is nice if $S$ is a PC spider and $Y\cup P$
is a nice shovel for each leg $P$ of $S$. If $G$ contains a nice octopus
$O^{*}_{\ell_{2},\ldots,\ell_{k}}$, then let
$F=G-O^{*}_{\ell_{2},\ldots,\ell_{k}}$. By Lemma 3, $F$ contains a spanning
nice shovel $F^{\prime}$ when $|F|\geq 3$. Set $F^{\prime}=F$ when $|F|\leq
2$. Apply Lemma 4 to $F^{\prime}$ and the triangle in
$O^{*}_{\ell_{2},\ldots,\ell_{k}}$, we get a desired PC spider. Therefore the
following claim holds.

######  Claim A.

If $G$ contains a nice octopus $O^{*}_{\ell_{2},\ldots,\ell_{k}}$, then $G$
contains a PC spider with legs of lengths $\ell_{1},\ell_{2},\ldots,\ell_{k}$.

Let $B_{1},B_{2},\ldots,B_{s}$ be vertex-disjoint nice bowties in $G$ such
that there is no nice bowtie in $H:=G\setminus\cup_{i=1}^{s}V(B_{i})$. Then
$s\leq g(S_{k},C_{3})$. Recall that each bowtie has at most $6$ vertices. We
have $|H|\geq n-6g(S_{k},C_{3})$. Note that $\ell_{1}\geq\frac{n-1}{k}\geq
6g(S_{k},C_{3})+2k^{2}+2k+7$. Then

$|H|=1+\sum_{i=2}^{k}\ell_{i}+\ell_{1}-6g(S_{k},C_{3})\geq\sum_{i=2}^{k}\ell_{i}+2k^{2}+2k+8.$

For each vertex $v$ in $H$, we claim that at most one color in
$col(v,N_{H}(v))$ appears more than once at $v$. Otherwise by the
mono-$C_{3}$-free condition, $H$ contains a nice short bowtie with $v$ being
the center vertex, which contradicts the choice of $H$.

######  Claim B.

For each vertex $v\in V(H)$, at most one color in $col(v,N_{H}(v))$ appears
more than once at $v$.

There could be a vertex $v$ with no color repeats at $v$. Let $V_{1}=\\{v\in
V(H):\Delta^{mon}_{H}(v)=1\\}$ and $V_{2}=\\{v\in V(H):\Delta^{mon}_{H}(v)\geq
2\\}$.

If $|V_{1}|\geq 3$, then let $v_{1},v_{2},v_{3}$ be distinct vertices in
$V_{1}$. By the definition of $V_{1}$, the cycle $v_{1}v_{2}v_{3}v_{1}$ must
be a rainbow triangle. Let $H^{\prime}=H-\\{v_{1},v_{2},v_{3}\\}$. Recall that
$|H|\geq\sum_{i=2}^{k}\ell_{i}+2k^{2}+2k+8$. We have
$|H^{\prime}|\geq\sum_{i=2}^{k}\ell_{i}+2k^{2}+2k+5$. Let
$X_{2},X_{3},\ldots,X_{k}$ be disjoint sets in $H^{\prime}$ such that
$|X_{i}|=\ell_{i}$ for $2\leq i\leq k$. By Lemma 2, there is a PC path $P_{i}$
on $\\{v_{1}\\}\cup X_{i}$ with $v_{1}$ being the starting vertex for $2\leq
i\leq k$. Since $\Delta^{mon}_{H^{\prime}}(v_{1})=1$, the triangle
$v_{1}v_{2}v_{3}v_{1}$ and paths $P_{2},P_{3},\ldots,P_{k}$ form a nice
octopus $O^{*}_{\ell_{2},\ldots,\ell_{k}}$. By Claim A, we are home.

If $2\leq\Delta^{mon}_{H}(x)\leq 2k^{2}+2k+7$ for some vertex $x\in V_{2}$,
then assume $\alpha$ is the color such that $\Delta^{mon}_{H}(x)=|\\{u\in
V(H):col(ux)=\alpha\\}|$. Let $U_{\alpha}=\\{u\in V(H):col(ux)=\alpha\\}$ and
$H^{\prime}=H-U_{\alpha}$. Then $|H^{\prime}|\geq\sum_{i=2}^{k}\ell_{i}+1$.
Let $X_{2},X_{3},\ldots,X_{k}$ be disjoint sets in $H^{\prime}-x$ such that
$|X_{i}|=\ell_{i}$ for $2\leq i\leq k$. By Lemma 2, there is a PC path $P_{i}$
on $\\{x\\}\cup X_{i}$ with $v_{1}$ being the starting vertices for $2\leq
i\leq k$. Note that $\Delta^{mon}_{H^{\prime}}(x)=1$. Choose distinct vertices
$a,b\in U_{\alpha}$, then the triangle $xabx$ and paths
$P_{2},P_{3},\ldots,P_{k}$ form a nice octopus
$O^{*}_{\ell_{2},\ldots,\ell_{k}}$. By Claim A, we are home.

The remaining case is that $|V_{1}|\leq 2$ and $\Delta^{mon}_{H}(x)\geq
2k^{2}+2k+8$ for every $x\in V_{2}$. Let $H_{1}=H-V_{1}$. Then
$|H_{1}|\geq\sum_{i=2}^{k}\ell_{i}+2k^{2}+2k+6$ and
$\Delta^{mon}_{H_{1}}(u)\geq 2k^{2}+2k+6$ for every vertex $u\in V(H_{1})$.
Let $f(u)$ be the unique color appearing more than once in
$col(u,N_{H_{1}}(u))$. We claim that for any two vertices $u,v\in V(H_{1})$,
there holds $col(u)=f(u)$ or $f(v)$. Otherwise, $H$ contains a nice long
bowtie with $u$ and $v$ being the center vertices, which contradicts the
choice of $H$.

######  Claim C.

For each pair of vertices $u,v\in V(H)$, we have $col(uv)=f(u)$ or $f(v)$.

Now construct an auxiliary digraph $D$ satisfying $V(D)=V(H_{1})$ and
$A(D)=\\{uv:col(uv)=f(u)\ \text{and}\ col(uv)\neq f(v)\\}.$ Since $H_{1}$ is
mono-$C_{3}$-free, according to Claim C and Definition 4, the directed graph
$D$ is a mono-$C_{3}$-free tournament with $N^{+}_{D}(u)\geq 2k^{2}+2k+6>2$
for every vertex $u\in V(H_{1})$. Recall that
$|H_{1}|\geq\sum_{i=2}^{k}\ell_{i}+2k^{2}+2k+6$. By Theorem 3, $D$ contains a
subgraph $T^{*}_{\ell_{2},\cdots,\ell_{k}}$, which is a nice octopus
$O^{*}_{\ell_{2},\ldots,\ell_{k}}$ in $G$. Again we obtain the desired PC
spanning tree by Claim A. The proof is complete. ∎

##  5 Conclusion

Tree embedding has become an increasingly popular research area in recent
years. It has been extensively studied in various contexts, such as spanning
trees or almost spanning trees in random graphs [26], random directed graphs
[27], $(n,d,\lambda)$ graphs [18, 19], tournaments [7, 6], dense directed
graphs [21], edge-colored graphs [15] and finite vector spaces[10]. This paper
demonstrates that in edge-colored complete graphs, the absence of
monochromatic triangle implies the existence of PC copies of every spanning
tree, which is a subdivision of a $k$-star. The most challenging part in the
proof is the case of multipartite tournaments. In fact, every $n$-vertex
rooted tree oriented from each child-vertex to its father-vertex, is contained
in a transitive tournament $D$ on $n$ vertices. Color each arc in $D$ with the
label of its tail, resulting an edge-colored complete graph, which is
mono-$C_{3}$-free and contains PC copies of every spanning tree. Motivated by
this example, we ask the following question.

######  Question 1.

Let $T$ be an $n$-vetrex tree with maximum degree at most $\Delta$ and let $G$
be a mono-$C_{3}$-free edge-colored $K_{n}$. Does $G$ always contain a PC copy
of $T$ when $n$ is sufficiently large?

A graph $G$ is called $\mathcal{T}(n,\Delta)$-universal if $G$ contains every
spanning tree with maximum degree at most $\Delta$. The statement of above
question is also inspired by a question from Alon, Krivelevich and Sudakov[2]
on the $\mathcal{T}(n,\Delta)$-universal property of $(n,d,\lambda)$-graphs.
We also observed that the result of Benford and Montgomery[6] may help dealing
with the multipartite tournament case in further research on Conjecture 1. It
would be interesting to see more connections between Conjecture 1 and tree
embedding results in graphs and digraphs.

Acknowledgements. Part of this work was initiated soon after the first author
began her visit to the Institute for Basic Science in Korea. She greatly
appreciates the hospitality and the pleasant atmosphere in Extremal
Combinatorics and Probability Group that contributed to the successful
completion of this work.

## References

  * [1] R. Aharoni, M. DeVos, and R. Holzman.  Rainbow triangles and the Caccetta-Häggkvist conjecture.  Journal of Graph Theory, 92(4):347–360, 2019.
  * [2] N. Alon, M. Krivelevich, and B. Sudakov.  Embedding nearly-spanning bounded degree trees.  Combinatorica, 27(6):629–644, 2007.
  * [3] N. Alon, A. Pokrovskiy, and B. Sudakov.  Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles.  Israel Journal of Mathematics, 222(1):317–331, 2017.
  * [4] L. D. Andersen.  Hamilton circuits with many colours in properly edge-coloured complete graphs.  Mathematica Scandinavica, 64(1):5–14, 1989.
  * [5] O. Barr.  Properly coloured Hamiltonian paths in edge-coloured complete graphs without monochromatic triangles.  Ars Combinatoria, 50:316–318, 1998.
  * [6] A. Benford and R. Montgomery.  Trees with few leaves in tournaments.  Journal of Combinatorial Theory, Series B, 155:141–170, 2022.
  * [7] A. Benford and R. Montgomery.  Trees with many leaves in tournaments, 2022.  arXiv:2207.06384 [math].
  * [8] B. Bollobás and P. Erdős.  Alternating Hamiltonian cycles.  Israel Journal of Mathematics, 23(2):126–131, 1976.
  * [9] J. A. Bondy and U. S. R. Murty.  Graph theory.  Springer Publishing Company, Incorporated, 2008.
  * [10] D. Chakraborti and B. Lund.  Almost spanning distance trees in subsets of finite vector spaces, 2024\.  arXiv:2306.12023 [math].
  * [11] L. Ding, J. Hu, G. Wang, and D. Yang.  Properly colored short cycles in edge-colored graphs.  European Journal of Combinatorics, 100:103436, Feb. 2022.
  * [12] P. Erdős and R. Rado.  A combinatorial theorem.  Journal of the London Mathematical Society, 25:249–255, 1950.
  * [13] S. Fujita, R. Li, and G. Wang.  Decomposing edge-coloured graphs under colour degree constraints.  Combinatorics, Probability and Computing, 28(5):755–767, 2019.
  * [14] T. Gallai.  Transitiv orientierbare Graphen.  Acta Mathematica. Academiae Scientiarum Hungaricae, 18:25–66, 1967\.
  * [15] S. Glock, D. Kühn, R. Montgomery, and D. Osthus.  Decompositions into isomorphic rainbow spanning trees.  Journal of Combinatorial Theory, Series B, 146:439–484, 2021.
  * [16] A. Gyárfás, J. Lehel, R. H. Schelp, and Z. Tuza.  Ramsey numbers for local colorings.  Graphs and Combinatorics, 3(1):267–277, 1987.
  * [17] A. Gyárfás and G. Simonyi.  Edge colorings of complete graphs without tricolored triangles.  Journal of Graph Theory, 46(3):211–216, 2004.
  * [18] J. Han and D. Yang.  Spanning trees in sparse expanders, 2023.  arXiv:2211.04758 [math].
  * [19] J. Hyde, N. Morrison, A. Muyesser, and M. Pavez-Signe.  Spanning trees in pseudorandom graphs via sorting networks, 2023.  arXiv:2311.03185 [math].
  * [20] R. E. Jamison, T. Jiang, and A. C. H. Ling.  Constrained Ramsey numbers of graphs.  Journal of Graph Theory, 42(1):1–16, 2003.
  * [21] A. Kathapurkar and R. Montgomery.  Spanning trees in dense directed graphs.  Journal of Combinatorial Theory, Series B, 156:223–249, 2022.
  * [22] R. Li.  Properly colored cycles in edge-colored complete graphs without monochromatic triangle: A vertex-pancyclic analogous result.  Discrete Mathematics, 344(11):112573, 2021.
  * [23] R. Li, H. Broersma, and S. Zhang.  Vertex-disjoint properly edge‐colored cycles in edge‐colored complete graphs.  Journal of Graph Theory, 94(3):476–493, 2020.
  * [24] R. Li, B. Li, and S. Zhang.  A classification of edge-colored graphs based on properly colored walks.  Discrete Applied Mathematics, 283:590–595, 2020.
  * [25] A. Lo.  Properly coloured Hamiltonian cycles in edge-coloured complete graphs.  Combinatorica, 36(4):471–492, 2016.
  * [26] R. Montgomery.  Spanning trees in random graphs.  Advances in Mathematics, 356:106793, 2019.
  * [27] R. Montgomery.  Spanning cycles in random directed graphs.  2022\.  arXiv:2103.06751 [math].


# TURBO CODED OFDM-OQAM USING HILBERT TRANSFORM

Kasturi Vasudevan1, Surendra Kota1, Lov Kumar1,
Himanshu Bhusan Mishra2
1Dept of EE IIT Kanpur India;
2Dept of Electronics IIT-ISM Dhanbad India

Keywords: OFDM-OQAM, FBMC, GFDM, OFDM, SSB, frequency
offset, average SNR per bit, BER, matched filter, Hilbert transform,
turbo code

ABSTRACT

Orthogonal frequency division multiplexing (OFDM) with offset quadrature
amplitude modulation (OQAM) has been widely discussed in the literature and is
considered a popular waveform for 5th generation (5G) wireless
telecommunications and beyond. In this work, we show that OFDM-OQAM can be
generated using the Hilbert transform and is equivalent to single sideband
modulation (SSB), that has roots in analog telecommunications. The transmit
filter for OFDM-OQAM is complex valued whose real part is given by the pulse
corresponding to the root raised cosine spectrum and the imaginary part is the
Hilbert transform of the real part. The real-valued digital information
(message) are passed through the transmit filter and frequency division
multiplexed on orthogonal subcarriers. The message bandwidth corresponding to
each subcarrier is assumed to be narrow enough so that the channel can be
considered ideal. Therefore, at the receiver, a matched filter can used to
recover the message. Turbo coding is used to achieve bit-error-rate (BER) as
low as $10^{-5}$ at an average signal-to-noise ratio (SNR) per bit close to 0
db. The system has been simulated in discrete time.

## INTRODUCTION

Orthogonal frequency division multiplexing (OFDM) [1, 2, 3] and OFDM offset
quadrature amplitude modulation (OFDM-OQAM) [4] are the preferred modulation
techniques for transmission of digital information over frequency selective
channels, both fading and non-fading. The variants of OFDM-OQAM [5, 6, 7, 8,
9] are known as filter bank multicarrier (FBMC) [4, 5, 6, 7] and universal
filtered multicarrier (UFMC) [10, 11] and generalized frequency division
multiplexing (GFDM) [12, 13, 14] in the literature.

One of the key advantages of OFDM-OQAM/FBMC/UFMC over OFDM is its immunity
against carrier frequency offsets (CFO). In other words, it may not be
necessary for an OFDM-OQAM/FBMC/UFMC system to estimate and cancel the CFO,
unlike OFDM. However, it has been shown in [1, 2, 3] that it is possible to
estimate and cancel the CFO very accurately with large scope for parallel
processing. The other important feature of OFDM-OQAM is the spectral
containment of each subcarrier using a transmit filter, which is absent in
OFDM. However, OFDM is more attractive than OFDM-OQAM in terms of
implementation simplicity.

In this work, we demonstrate that OFDM-OQAM/FBMC/UFMC can be efficiently
implemented using the Hilbert transform at the transmitter and a matched
filter at the receiver [15]. It must be noted that using OQAM would improve
the symbol density in time-frequency space, at the cost of introducing
intersymbol interference (ISI) at the matched filter output and increasing the
receiver complexity. Therefore, in this work, we do not use OQAM and yet have
a symbol density in time frequency space greater than unity. We however retain
the nomenclature “OFDM-OQAM/FBMC/UFMC” since this work deals with multicarrier
communications.

We use the following notation. Complex quantities are denoted by a tilde e.g.,
$\tilde{p}(t)$, estimates are denoted by hat e.g., $\hat{b}$ and convolution
is denoted by star e.g., $p(t)\star g(t)$. This article is organized as
follows. We first discuss the theory of OFDM-OQAM, followed by derivation of
Hilbert transform of the pulse corresponding to root-raised cosine spectrum.
The discrete-time implementation issues are discussed next, motivating the
need for a modified Hilbert transform. The discrete-time system model used for
computer simulations is presented, followed by results and conclusions.

## THEORY

At the outset, we note that multicarrier communication is equivalent to
frequency division multiplexing. The time-frequency representation of a
multicarrier communication system is shown in Figure 1 [4]. The symbol-rate is
$1/T$ baud and the subcarrier spacing is $\mathscr{B}$. The red colour dots
denote symbols. The subcarrier frequency can be positive or negative, as will
be apparent later.

0$-2\mathscr{B}$$-\mathscr{B}$$2T$$-T$$-2T$$T$$t$$2\mathscr{B}$$\mathscr{B}$$F$

Figure 1: Symbol density of multicarrier communication system in time-
frequency space.

The complex envelope of a linearly modulated digital signal is given by [16]

$\displaystyle\tilde{s}(t)$
$\displaystyle=\sum_{k=-\infty}^{\infty}S_{k}\,\tilde{p}(t-kT)$
$\displaystyle=s_{I}(t)+\mathrm{j}\,s_{Q}(t)\qquad\mbox{(say)}$ (1)

where $S_{k}$ denotes complex-valued symbols drawn from an $M$-ary
constellation, $\tilde{p}(t)$ denotes the (possibly complex-valued) impulse
response of the transmit filter, the subscripts “$I,\,Q$” denote in-phase
(real) and quadrature (imaginary) components respectively. When the symbols
$S_{k}$ are uncorrelated, the power spectral density of $\tilde{s}(t)$ in
(THEORY) is [16]

$S_{\tilde{s}}(F)=\frac{P_{\mathrm{av}}}{2T}\left|\tilde{P}(F)\right|^{2}$ (2)

where $\tilde{P}(F)$ is the Fourier transform of $\tilde{p}(t)$ and
$P_{\mathrm{av}}$ denotes the average power of the $M$-ary constellation. If
the transmit filter $\tilde{p}(t)=p(t)$ is real-valued [16] having a root
raised cosine (RRC) spectrum with roll-off factor $\rho$, $0<\rho\leq 1$, then
the minimum spacing between subcarriers for no aliasing would be

$\mathscr{B}=\frac{2(1+\rho)}{2T}$ (3)

which is essentially the two-sided bandwidth of $\tilde{P}(F)$. Therefore, the
symbol density in time-frequency space is the inverse of the area of each
rectangle in Figure 1 [4]:

$\frac{1}{\mathscr{B}T}=\frac{1}{(1+\rho)}<1.$ (4)

In this article, we propose a complex-valued transmit filter given by

$\tilde{p}(t)=p(t)+\mathrm{j}\,\hat{p}(t)$ (5)

where $p(t)$ has an RRC spectrum and $\hat{p}(t)$ is the Hilbert transform of
$p(t)$. The Fourier transform of $\tilde{p}(t)$ in (5) is

$\displaystyle\tilde{P}(F)$
$\displaystyle=P(F)+\mathrm{j}\,(-\mathrm{j}\mathrm{sgn}(F))P(F)$
$\displaystyle=\left\\{\begin{array}[]{ll}2P(F)&\mbox{for $F>0$}\\\
P(0)&\mbox{for $F=0$}\\\ 0&\mbox{for $F<0$}\end{array}\right.$ (9)

where $P(F)$ is the Fourier transform of $p(t)$ and $\mathrm{sgn}(\cdot)$ is
the signum function [17, 18]. The minimum spacing between subcarriers in this
case is

$\mathscr{B}=\frac{1+\rho}{2T}$ (10)

resulting in symbol density in time-frequency space equal to

$\frac{1}{\mathscr{B}T}=\frac{2}{(1+\rho)}\geq 1.$ (11)

It is emphasized here that when $\tilde{p}(t)$ is given by (5), the symbols
$S_{k}$ have to be real-valued. The reason is as follows. The complex envelope
in (THEORY) can be written as

$\tilde{s}(t)=\tilde{s}_{1}(t)\star\tilde{p}(t)$ (12)

where “$\star$” denotes convolution and

$\displaystyle\tilde{s}_{1}(t)$
$\displaystyle=\sum_{k=-\infty}^{\infty}S_{k}\,\delta_{D}(t-kT)$
$\displaystyle=s_{1,\,I}(t)+\mathrm{j}\,s_{1,\,Q}(t)\qquad\mbox{(say)}$ (13)

where $\delta_{D}(\cdot)$ denotes the Dirac-delta function [17, 18]. At the
receiver, we use a matched filter given by $\tilde{p}^{*}(-t)$. The matched
filter output would be given by [16]

$\tilde{y}(t)=\tilde{s}_{1}(t)\star\tilde{p}(t)\star\tilde{p}^{*}(-t).$ (14)

Now

$\displaystyle\tilde{p}(t)\star\tilde{p}^{*}(-t)$
$\displaystyle=\left[p(t)+\mathrm{j}\,\hat{p}(t)\right]\star\left[p(-t)-\mathrm{j}\,\hat{p}(-t)\right]$
$\displaystyle=p(t)\star
p(-t)+\hat{p}(t)\star\hat{p}(-t)+\mathrm{j}\,\left[\hat{p}(t)\star
p(-t)-p(t)\star\hat{p}(-t)\right].$ (15)

It can be shown that for real-valued $p(t)$ [17, 18]

$\displaystyle\hat{p}(t)\star\hat{p}(-t)$ $\displaystyle=p(t)\star p(-t)$
$\displaystyle=R_{pp}(t)$ $\displaystyle\hat{p}(t)\star p(-t)$
$\displaystyle=R_{\hat{p}p}(t)$ $\displaystyle=-p(t)\star\hat{p}(-t)$
$\displaystyle=-R_{p\hat{p}}(t).$ (16)

Substituting (THEORY) and (THEORY) in (14) we obtain the matched filter output
as

$\tilde{y}(t)=\sum_{k=-\infty}^{\infty}2S_{k}\left[R_{pp}(t-kT)+\mathrm{j}\,R_{\hat{p}p}(t-kT)\right].$
(17)

The condition for zero ISI is

$R_{pp}(mT)=\delta_{K}(mT)$ (18)

where $\delta_{K}(\cdot)$ is the Kronecker delta function [16]. However,
$R_{\hat{p}p}(t)$ does not satisfy the zero ISI condition. Hence using (18),
the symbol-rate sampler at the matched filter output would yield

$\displaystyle\tilde{y}(nT)$
$\displaystyle=\sum_{k=-\infty}^{\infty}2S_{k}\left(R_{pp}(nT-
kT)+\mathrm{j}\,R_{\hat{p}p}(nT-kT)\right)$
$\displaystyle=2S_{n}+2\mathrm{j}\,\sum_{k=-\infty}^{\infty}S_{k}R_{\hat{p}p}(nT-
kT).$ (19)

It is clear from (THEORY) that implementing the matched filter as given in
(14) and (THEORY) with complex-valued symbols $S_{k}$ is not possible, due to
crosstalk (interference between in-phase and quadrature components).
Therefore, the symbols $S_{k}$ have to be real-valued. One possible
implementation of the proposed OFDM-OQAM/FBMC/UFMC transmitter is shown in
Figure 2.

$p(t)$$S_{k}$$\hat{p}(t)$$-\sin(2\pi F_{c}t)$$\cos(2\pi F_{c}t)$I-armQ-
arm$\tilde{s}(t)$$s(t)$

Figure 2: Proposed OFDM-OQAM transmitter for each subcarrier.

$-2\sin(2\pi F_{c}t)$$2\cos(2\pi
F_{c}t)$$\hat{p}(-t)$$p(-t)$$t=nT$$t=nT$$S_{k}$$S_{k}$I-armQ-arm$s(t)$

Figure 3: Proposed OFDM-OQAM receiver for each subcarrier.

The corresponding receiver is shown in Figure 3. In the next section, we
derive $\hat{p}(t)$ when $p(t)$ has an RRC spectrum.

## HILBERT TRANSFORM OF RRC SPECTRUM

The RRC spectrum which is the Fourier transform of $p(t)$ is given by [16]

$P(F)=\left\\{\begin{array}[]{ll}\frac{1}{\sqrt{2B}}&\mbox{for $-F_{1}\leq
F\leq F_{1}$}\\\
\frac{1}{\sqrt{2B}}\cos\left(\frac{\pi(|F|-F_{1})}{4B-4F_{1}}\right)&\mbox{for
$F_{1}\leq|F|\leq 2B-F_{1}$}\\\ 0&\mbox{elsewhere}\end{array}\right.$ (20)

where

$\displaystyle 2B$
$\displaystyle\stackrel{{\scriptstyle\Delta}}{{=}}\frac{1}{T}$
$\displaystyle\rho$
$\displaystyle\stackrel{{\scriptstyle\Delta}}{{=}}1-\frac{F_{1}}{B}.$ (21)

Therefore

$\hat{p}(t)=\int_{F=-\infty}^{\infty}-\mathrm{j}\,\mathrm{sgn}(F)P(F)\mathrm{e}^{\mathrm{j}\,2\pi
Ft}\,dF$ (22)

where $P(F)$ is given by (20) and (HILBERT TRANSFORM OF RRC SPECTRUM). We have

$\displaystyle I_{1}$
$\displaystyle=\int_{F=-F_{1}}^{F_{1}}-\mathrm{j}\,\mathrm{sgn}(F)\frac{1}{\sqrt{2B}}\mathrm{e}^{\mathrm{j}\,2\pi
Ft}\,dF$ $\displaystyle=\frac{1}{\pi t\sqrt{2B}}\left[1-\cos(2\pi
F_{1}t)\right].$ (23)

Similarly

$\displaystyle I_{2}$
$\displaystyle=\int_{F=F_{1}}^{2B-F_{1}}-\mathrm{j}\,\frac{1}{\sqrt{2B}}\cos\left(\frac{\pi(F-F_{1})}{4B-4F_{1}}\right)\mathrm{e}^{\mathrm{j}\,2\pi
Ft}\,dF$
$\displaystyle\qquad+\int_{F=-(2B-F_{1})}^{-F_{1}}\mathrm{j}\,\frac{1}{\sqrt{2B}}\cos\left(\frac{\pi(-F-F_{1})}{4B-4F_{1}}\right)\mathrm{e}^{\mathrm{j}\,2\pi
Ft}\,dF$
$\displaystyle=\frac{1}{\sqrt{2B}}\int_{F=B(1-\rho)}^{B(1+\rho)}\left\\{\sin\left[2\pi
Ft+\frac{\pi(F-F_{1})}{4B-4F_{1}}\right]+\sin\left[2\pi
Ft-\frac{\pi(F-F_{1})}{4B-4F_{1}}\right]\right\\}\,dF$
$\displaystyle=\frac{1}{\sqrt{2B}}\int_{F=B(1-\rho)}^{B(1+\rho)}\left\\{\sin\left[\alpha
F-\beta\right]+\sin\left[\beta-\gamma F\right]\right\\}\,dF$
$\displaystyle=\frac{1}{\gamma\sqrt{2B}}\left\\{\cos\left[\beta-\gamma
B(1+\rho)\right]-\cos\left[\beta-\gamma B(1-\rho)\right]\right\\}$
$\displaystyle\qquad-\frac{1}{\alpha\sqrt{2B}}\left\\{\cos\left[\alpha
B(1+\rho)-\beta\right]-\cos\left[\alpha B(1-\rho)-\beta\right]\right\\}$ (24)

where

$\displaystyle F_{1}$ $\displaystyle=B(1-\rho)$ $\displaystyle 2B-F_{1}$
$\displaystyle=B(1+\rho)$ $\displaystyle 4B-4F_{1}$ $\displaystyle=4B\rho$
$\displaystyle\alpha$ $\displaystyle=\frac{\pi(1+8Bt\rho)}{4B\rho}$
$\displaystyle\beta$ $\displaystyle=\frac{\pi F_{1}}{4B\rho}$
$\displaystyle\gamma$ $\displaystyle=\frac{\pi(1-8Bt\rho)}{4B\rho}.$ (25)

Now from (HILBERT TRANSFORM OF RRC SPECTRUM)

$\displaystyle\beta-\gamma B$ $\displaystyle=\frac{-\pi}{4}+2\pi Bt$
$\displaystyle\gamma B\rho$ $\displaystyle=\frac{\pi}{4}-2\pi Bt\rho$
$\displaystyle\alpha B-\beta$ $\displaystyle=\frac{\pi}{4}+2\pi Bt$
$\displaystyle\alpha B\rho$ $\displaystyle=\frac{\pi}{4}+2\pi Bt\rho.$ (26)

Substituting (HILBERT TRANSFORM OF RRC SPECTRUM) in (HILBERT TRANSFORM OF RRC
SPECTRUM) we obtain

$\displaystyle I_{2}$ $\displaystyle=\frac{1}{\sqrt{2B}}\sin(2\pi
Bt(1+\rho))\left\\{\frac{1}{\gamma}+\frac{1}{\alpha}\right\\}$
$\displaystyle\qquad-\frac{1}{\sqrt{2B}}\cos(2\pi
Bt(1-\rho))\left\\{\frac{1}{\gamma}-\frac{1}{\alpha}\right\\}.$ (27)

Now

$\displaystyle\frac{1}{\gamma}-\frac{1}{\alpha}$
$\displaystyle=\frac{64B^{2}\rho^{2}t}{\pi(1-64B^{2}t^{2}\rho^{2})}$
$\displaystyle\frac{1}{\gamma}+\frac{1}{\alpha}$
$\displaystyle=\frac{8B\rho}{\pi(1-64B^{2}t^{2}\rho^{2})}.$ (28)

Substituting (HILBERT TRANSFORM OF RRC SPECTRUM) in (HILBERT TRANSFORM OF RRC
SPECTRUM) we get

$\displaystyle I_{2}$ $\displaystyle=\frac{1}{\sqrt{2B}}\sin(2\pi
Bt(1+\rho))\left\\{\frac{8B\rho}{\pi(1-64B^{2}t^{2}\rho^{2})}\right\\}$
$\displaystyle\qquad-\frac{1}{\sqrt{2B}}\cos(2\pi
Bt(1-\rho))\left\\{\frac{64B^{2}\rho^{2}t}{\pi(1-64B^{2}t^{2}\rho^{2})}\right\\}.$
(29)

Finally $\hat{p}(t)$ in (22) is given by

$\hat{p}(t)=I_{1}+I_{2}$ (30)

where $I_{1},\,I_{2}$ are given by (HILBERT TRANSFORM OF RRC SPECTRUM) and
(HILBERT TRANSFORM OF RRC SPECTRUM) respectively.

## DISCRETE TIME IMPLEMENTATION

Theoretically when $p(t)$ has an RRC spectrum, both $p(t),\,\hat{p}(t)$ have
an infinite time span. In practice they have to be truncated, in which case
(18) is only approximately valid. Moreover, the transmitter and receiver in
Figures 2 and 3 have to be implemented in discrete time. In this section, we
explore these issues.

Magnitude

Frequency (Hz)

Figure 4: Magnitude response of $p(t)$ and $\tilde{p}(t)$. $|P(0)|=1$ for RRC,
$\left|\tilde{P}(0)\right|=1$ for HT-RRC.

The magnitude response of $p(mT_{s})$ (RRC) and $\tilde{p}(mT_{s})$ (HT-RRC)
given by

$\tilde{p}(mT_{s})=p(mT_{s})+\mathrm{j}\,\hat{p}(mT_{s})$ (31)

is shown in Figure 4 for $T=1$ sec, $\rho=0.161$ and sampling frequency
$F_{s}=1/T_{s}=5$ Hz. Both $p(mT_{s})$ and $\hat{p}(mT_{s})$ lie in the range
$-M\leq m\leq M$ for $M=100$. The parameter $M$ is referred to as the one-
sided window length. Note that in Figure 4, $\tilde{P}(\cdot)$ is the discrete
Fourier transform of $\tilde{p}(\cdot)$ given in (31).

The ratio of signal-to-interference (SIR) power is defined as

$\mbox{SIR}=10\log_{10}\left[\frac{R_{gg}^{2}(0)}{\sum_{\begin{subarray}{c}n\\\
n\neq 0\end{subarray}}R_{gg}^{2}(nT)}\right]\quad\mbox{db.}$ (32)

where $g(\cdot)$ is $p(\cdot)$ or $\hat{p}(\cdot)$. Note that

$\displaystyle R_{gg}(mT_{s})$ $\displaystyle=g(mT_{s})\star g(-mT_{s})$
$\displaystyle R_{gg}(nT)$ $\displaystyle=R_{gg}(nIT_{s})$ $\displaystyle I$
$\displaystyle=\frac{T}{T_{s}}$ (33)

where “$\star$” denotes (discrete-time) linear convolution and $I$ is the
interpolation factor.

Table 1: SIR of $R_{\hat{p}\hat{p}}(nT)$ and $R_{pp}(nT)$.

10080402016.93115.93412.9759.36356.92149.42640.60225.212$M$SIR
(db)$R_{\hat{p}\hat{p}}(nT)$$R_{pp}(nT)$

The SIR in decibels is shown in Table 1 for different values of the one-sided
window length $M$ when $T=1$ sec, $\rho=0.161$, $F_{s}=5=1/T_{s}$ Hz. We find
from Table 1 that the SIR of $R_{\hat{p}\hat{p}}(t)$ is much lower than
$R_{pp}(t)$ for the same values of $M$. This is probably because the signum
function in the Hilbert transform (see (22)) has a discontinuity at $F=0$. In
the next section, we discuss the modified Hilbert transform that avoids this
discontinuity.

## MODIFIED HILBERT TRANSFORM

Consider the modified Hilbert transform given by [15]

$\tilde{H}(F)=\left\\{\begin{array}[]{ll}\mathrm{e}^{\,\mathrm{j}[\pi(F+aF_{1})/(2aF_{1})+\pi/2]}&\mbox{for
$|F|\leq aF_{1}$}\\\ -\mathrm{j}&\mbox{for $F\geq aF_{1}$}\\\
\mathrm{j}&\mbox{for $F\leq-aF_{1}$}\end{array}\right.$ (34)

for $0<a\leq 1$, which is plotted in Figure 5.

Freq (Hz)$\Im\\{\tilde{H}(F)\\}$$\Re\\{\tilde{H}(F)\\}$

Figure 5: Frequency response of the modified Hilbert transformer for $a=0.25$,
$\rho=0.161$, $T=1$ sec.

Hence the modified Hilbert transform of $p(t)$ can be written as

$\displaystyle\hat{p}_{\mathrm{m}}(t)$
$\displaystyle=\int_{F=-\infty}^{\infty}\tilde{H}(F)P(F)\mathrm{e}^{\,\mathrm{j}\,2\pi
Ft}\,dF$ $\displaystyle=I_{11}+I_{12}+I_{2}$ (35)

where $I_{2}$ is given by (HILBERT TRANSFORM OF RRC SPECTRUM) and

$\displaystyle I_{11}$
$\displaystyle=\int_{F=-aF_{1}}^{aF_{1}}\tilde{H}(F)P(F)\mathrm{e}^{\,\mathrm{j}\,2\pi
Ft}\,dF$
$\displaystyle=\frac{-1}{\sqrt{2B}}\int_{F=-aF_{1}}^{aF_{1}}\mathrm{e}^{\,\mathrm{j}\,\pi
F/(2aF_{1})}\mathrm{e}^{\,\mathrm{j}\,2\pi Ft}\,dF$
$\displaystyle=\frac{-2aF_{1}}{\sqrt{2B}}\mbox{sinc}\left(aF_{1}A_{1}\right)$
(36)

where

$\displaystyle A_{1}$ $\displaystyle=2t+\frac{1}{2aF_{1}}$
$\displaystyle\mbox{sinc}(x)$ $\displaystyle=\frac{\sin(\pi x)}{\pi x}.$ (37)

Similarly $I_{12}$ in (MODIFIED HILBERT TRANSFORM) is equal to

$\displaystyle I_{12}$
$\displaystyle=\frac{-\mathrm{j}}{\sqrt{2B}}\int_{aF_{1}}^{F_{1}}\mathrm{e}^{\,\mathrm{j}2\pi
Ft}\,dF+\frac{\mathrm{j}}{\sqrt{2B}}\int_{-F_{1}}^{-aF_{1}}\mathrm{e}^{\,\mathrm{j}2\pi
Ft}\,dF$
$\displaystyle=\frac{2F_{1}(1+a)}{\sqrt{2B}}\mbox{sinc}(F_{1}t(1+a))\sin(\pi
F_{1}t(1-a)).$ (38)

Magnitude

Frequency (Hz)

Figure 6: Magnitude response of $p(t)$ and $\tilde{p}_{\mathrm{m}}(t)$.
$|P(0)|=1$ for RRC, $\left|\tilde{P}_{\mathrm{m}}(0)\right|=1$ for HT-RRC.

The magnitude response of $p(mT_{s})$ (RRC) and
$\tilde{p}_{\mathrm{m}}(mT_{s})$ (mHT-RRC) given by

$\tilde{p}_{\mathrm{m}}(mT_{s})=p(mT_{s})+\mathrm{j}\,\hat{p}_{\mathrm{m}}(mT_{s})$
(39)

is shown in Figure 6 for $T=1$ sec, $\rho=0.161$ and sampling frequency
$F_{s}=1/T_{s}=5$ Hz. Both $p(mT_{s})$ and $\hat{p}_{\mathrm{m}}(mT_{s})$ lie
in the range $-M\leq m\leq M$ for $M=100$. Note that in Figure 6,
$\tilde{P}_{\mathrm{m}}(\cdot)$ is the discrete Fourier transform of
$\tilde{p}_{\mathrm{m}}(\cdot)$ given in (39).

Table 2: SIR of $R_{\hat{p}_{\mathrm{m}}\hat{p}_{\mathrm{m}}}(nT)$ and
$R_{pp}(nT)$.

56.92149.42640.60225.212$R_{pp}(nT)$$M$10080402052.78745.16833.29817.93SIR
(db)$R_{\hat{p}_{\mathrm{m}}\hat{p}_{\mathrm{m}}}(nT)$

We find from Table 2 that the SIR of
$R_{\hat{p}_{\mathrm{m}}\hat{p}_{\mathrm{m}}}(nT)$ is comparable to
$R_{pp}(nT)$.

## DISCRETE TIME SYSTEM MODEL

$p(mT_{s})$$\hat{p}_{\mathrm{m}}(mT_{s})$$\tilde{r}(mT_{s})$AWGN$\tilde{w}(mT_{s})$I-armFromsubcarrier
0Fromsubcarrier $N-1$turbo codeRate-$1/2$anddemuxsubcarrier 0ToTosubcarrier
$N-1$Transmitter for $i^{th}$
subcarrier$p(-mT_{s})$$\hat{p}_{\mathrm{m}}(-mT_{s})$Receiver for $i^{th}$
subcarrier$b_{k}$$\Re\\{\cdot\\}$$\Im\\{\cdot\\}$$S_{i,\,k}$Muxandturbodecode$\hat{b}_{k}$$\mathrm{e}^{-\mathrm{j}\,\omega_{i}m}$$\mathrm{e}^{\,\mathrm{j}\,\omega_{i}m}$Q-arm$\tilde{s}_{i}(mT_{s})$$\tilde{s}_{o}(mT_{s})$$x_{i,\,k,\,I}$Fromsubcarrier
0Fromsubcarrier
$N-1$$t=kT$$t=kT$$\frac{x_{i,\,k,\,I}+x_{i,\,k,\,Q}}{2}$$x_{i,\,k}$$x_{i,\,k,\,Q}$Tosubcarrier
0$\tilde{r}(mT_{s})$subcarrier $N-1$To

Figure 7: Discrete time system model for OFDM-OQAM.

The discrete time system model used for computer simulations is shown in
Figure 7. The input $b_{k}$ is arranged into frames of length $L_{d1}$ bits
and given to the rate-$1/2$ turbo code [1, 2, 3]. The output of the turbo code
of length $L_{d}=2L_{d1}$ bits is mapped to binary phase shift keyed (BPSK)
symbols $S_{i,\,k}=\pm 1$, demultiplexed and transmitted simultaneously over
$N$ subcarriers. The frequency of the $i^{th}$ subcarrier is given by

$\omega_{i}=2\pi i/N\quad\mbox{radians}\quad\mbox{for $0\leq i\leq N-1$}$ (40)

where $N=I$ is the total number of subcarriers and $I$ is given by (DISCRETE
TIME IMPLEMENTATION). The overall OFDM-OQAM signal is given by

$\tilde{s}_{o}(mT_{s})=\sum_{i=0}^{N-1}\tilde{s}_{i}(mT_{s})\mathrm{e}^{\,\mathrm{j}\,\omega_{i}m}$
(41)

where

$\tilde{s}_{i}(mT_{s})=\sum_{k}S_{i,\,k}\tilde{p}_{\mathrm{m}}(mT_{s}-kT)$
(42)

where $\tilde{p}_{\mathrm{m}}(\cdot)$ is given by (39).

0$\omega_{1}$$\omega_{N-1}$$2\pi$$\omega$$S_{o}(\omega)$

Figure 8: Spectrum of the overall OFDM-OQAM signal $\tilde{s}_{o}(mT_{s})$.

The spectrum of the complex-valued overall OFDM-OQAM signal
$\tilde{s}_{o}(mT_{s})$ is shown in Figure 8, where

$\omega=2\pi FT_{s}\quad\mbox{radians}$ (43)

where $F$ is the frequency in Hz. Recall that the sampling frequency $1/T_{s}$
Hz maps to $2\pi$ in the digital frequency domain. The variance per dimension
of complex-valued additive white Gaussian noise (AWGN) is

$\frac{1}{2}E\left[\left|\tilde{w}(mT_{s})\right|^{2}\right]=\sigma_{w}^{2}.$
(44)

The in-phase and quadrature components of $\tilde{w}(mT_{s})$ are assumed to
be independent. At the receiver we have for the $i^{th}$ subcarrier

$x_{i,\,k}=S_{i,\,k}+z_{i,\,k}$ (45)

where $z_{i,\,k}$ denotes real-valued samples of AWGN with variance
$\sigma_{w}^{2}/2$ [16]. We assume that both $p(\cdot)$ and
$\hat{p}_{\mathrm{m}}(\cdot)$ have unit energy, that is

$\displaystyle\sum_{m=-M}^{M}p^{2}(mT_{s})$ $\displaystyle=1$
$\displaystyle\sum_{m=-M}^{M}\hat{p}^{2}_{\mathrm{m}}(mT_{s})$
$\displaystyle=1.$ (46)

Note that from (THEORY), (THEORY) and (THEORY),
$x_{i,\,k,\,I},\,x_{i,\,k,\,Q}$ in Figure 7 have to be summed (or averaged).
Since $S_{i,\,k}$ carries half a bit of information, the average signal-to-
noise ratio (SNR) per bit is defined as [16]

$\displaystyle\mathrm{SNR}_{\mathrm{av},\,b}$
$\displaystyle=\frac{2E\left[S_{i,\,k}^{2}\right]}{\mbox{2D noise variance}}$
$\displaystyle=\frac{2\times 1}{2\times\sigma^{2}_{w}/2}$
$\displaystyle=\frac{2}{\sigma^{2}_{w}}.$ (47)

## SIMULATION RESULTS

Table 3: Simulation parameters.

ParameterValue$N=I$interpolationfactor)$L_{d1}$1024$L_{d}$2048$a$0.25$\rho$0.161$M$$8N,\,16N$$T$1
sec$T_{s}$$T/N$sec(Number ofsubcarriers $=$256

The discrete-time simulation parameters are given in Table 3. The transmit
filters are given by
$p(mT_{s}-0.5T_{s}),\,\hat{p}_{\mathrm{m}}(mT_{s}-0.5T_{s})$, for $-M\leq
m\leq M$, for integer $m$ and $M=8N,\,16N$. This is because, we require the
filter length to be an integer multiple of $N$, for the sake of implementation
simplicity.

Average SNR per bit

BER

Figure 9: Simulation results.

The computer simulation results for the bit-error-rate (BER) vs the average
SNR per bit ($\mathrm{SNR}_{\mathrm{av},\,b}$) are presented in Figure 9. The
theoretical BER is obtained from [19]. The BER results for $M=8N$ are denoted
by “sim8” and “theory8”. The BER results for $M=16N$ are denoted by “sim16”
and “theory16”. Observe the close match between theory and simulations.

## CONCLUSIONS

This article discusses the implementation of an OFDM-OQAM/FBMC/UFMC system in
discrete-time, using Hilbert transform. A simple matched filter receiver is
sufficient for detecting the symbols. In the present work, an AWGN channel is
considered. Frequency selective fading channels along with carrier frequency
offsets can be considered in future works.

## References

  * [1] K. Vasudevan, “Coherent detection of turbo coded OFDM signals transmitted through frequency selective Rayleigh fading channels,” in _Signal Processing, Computing and Control (ISPCC), 2013 IEEE International Conference on_ , Sept. 2013, pp. 1–6.
  * [2] ——, “Coherent detection of turbo-coded OFDM signals transmitted through frequency selective Rayleigh fading channels with receiver diversity and increased throughput,” _Wireless Personal Communications_ , vol. 82, no. 3, pp. 1623–1642, 2015. [Online]. Available: http://dx.doi.org/10.1007/s11277-015-2303-8
  * [3] ——, “Near capacity signaling over fading channels using coherent turbo coded OFDM and massive MIMO,” _International Journal On Advances in Telecommunications_ , vol. 10, no. 1 & 2, pp. 22–37, 2017, [Online].
  * [4] B. Farhang-Boroujeny, “OFDM versus filter bank multicarrier,” _IEEE Signal Processing Magazine_ , vol. 28, no. 3, pp. 92–112, May 2011.
  * [5] T. Jiang, C. Ni, D. Qu, and C. Wang, “Energy-efficient NC-OFDM/OQAM-based cognitive radio networks,” _IEEE Communications Magazine_ , vol. 52, no. 7, pp. 54–60, 2014.
  * [6] C. Kim, Y. H. Yun, K. Kim, and J.-Y. Seol, “Introduction to QAM-FBMC: From waveform optimization to system design,” _IEEE Communications Magazine_ , vol. 54, no. 11, pp. 66–73, 2016.
  * [7] C. Jin, S. Hu, Y. Huang, F. Li, J. Zhang, and S. Ma, “On design of conjugated transmission scheme for FBMC/OQAM systems with interference cancellation,” _China Communications_ , vol. 14, no. 8, pp. 166–175, 2017.
  * [8] F. Yang, Y. Wang, L. Ding, and L. Qian, “An improved equalization with real interference prediction scheme of the FBMC/OQAM system,” _China Communications_ , vol. 18, no. 1, pp. 120–129, 2021.
  * [9] M. T. Guneser, A. S. Sahab, and C. Seker, “Performance analysis of modulation techniques in 5G communication system,” _China Communications_ , vol. 19, no. 8, pp. 100–114, 2022.
  * [10] Y. Tao, L. Liu, S. Liu, and Z. Zhang, “A survey: Several technologies of non-orthogonal transmission for 5G,” _China Communications_ , vol. 12, no. 10, pp. 1–15, 2015.
  * [11] L. Zhang, A. Ijaz, P. Xiao, and R. Tafazolli, “Multi-service system: An enabler of flexible 5G air interface,” _IEEE Communications Magazine_ , vol. 55, no. 10, pp. 152–159, 2017.
  * [12] Y. Yang and L. Zhu, “Non-orthogonal multi-carrier transmission for internet via satellite,” _China Communications_ , vol. 14, no. 3, pp. 31–42, 2017\.
  * [13] A. Nimr, M. Chafii, and G. P. Fettweis, “Unified low complexity radix-2 architectures for time and frequency-domain GFDM modem,” _IEEE Circuits and Systems Magazine_ , vol. 18, no. 4, pp. 18–31, 2018.
  * [14] Y. Yang, L. Zhu, X. Mao, Q. Tan, and Z. He, “The spread spectrum GFDM schemes for integrated satellite-terrestrial communication system,” _China Communications_ , vol. 16, no. 12, pp. 165–175, 2019.
  * [15] K. Vasudevan, G. K. Pathak, S. Kota, and L. Kumar, “OFDM-OQAM using Hilbert transform,” 2023, Invited Talk, World Congress on Advanced Materials, 8 - 10 May 2023, Tokyo, Japan. [Online]. Available: https://www.bitcongress.com/galatechbook3/
  * [16] K. Vasudevan, _Digital Communications and Signal Processing, Second edition (CDROM included)_. Universities Press (India), Hyderabad, www.universitiespress.com, 2010.
  * [17] S. Haykin, _Communication Systems_ , 2nd ed. Wiley Eastern, 1983.
  * [18] K. Vasudevan, _Analog Communications: Problems & Solutions_. Ane Books, Springer, 2018.
  * [19] K. Vasudevan, S. Kota, L. Kumar, and H. B. Mishra, “New results on single user massive MIMO,” in _MIMO Communications - Fundamental Theory, Propagation Channels, and Antenna Systems_ , D. A. Kishk and D. X. Chen, Eds. Rijeka: IntechOpen, 2023, ch. 17. [Online]. Available: https://doi.org/10.5772/intechopen.112469