# Multithreshold multipartite graphs with small parts

Teeradej Kittipassorn  Department of Mathematics and Computer Science, Faculty
of Science, Chulalongkorn University, Bangkok 10330, Thailand;
<EMAIL_ADDRESS>Thanaporn Sumalroj  Department of Mathematics and
Computer Science, Faculty of Science, Chulalongkorn University, Bangkok 10330,
Thailand<EMAIL_ADDRESS>
###### Abstract

A graph is a _$k$ -threshold_ graph with _thresholds_
$\theta_{1},\theta_{2},\dots,\theta_{k}$ if we can assign a real number
$r_{v}$ to each vertex $v$ such that for any two distinct vertices $u$ and
$v$, $uv$ is an edge if and only if the number of thresholds not exceeding
$r_{u}+r_{v}$ is odd. The _threshold number_ of a graph is the smallest $k$
for which it is a $k$-threshold graph. Multithreshold graphs were introduced
by Jamison and Sprague as a generalization of classical threshold graphs. They
asked for the exact threshold numbers of complete multipartite graphs.
Recently, Chen and Hao solved the problem for complete multipartite graphs
where each part is not too small, and they asked for the case when each part
has size $3$. We determine the exact threshold numbers of $K_{3,3,\dots,3}$,
$K_{4,4,\dots,4}$ and their complements $nK_{3}$, $nK_{4}$. This improves a
result of Puleo.

##  1 Introduction

A graph $G$ is said to be a _threshold graph_ if we can assign a real number
$r_{v}$ to each vertex $v$ and there is a real number $\theta$ such that for
any vertex subset $U$ of $G$, $\sum_{v\in U}r_{v}\leq\theta$ if and only if
$U$ is independent in $G$. The class of threshold graphs was first introduced
by Chvátal and Hammer [3] in 1977 to answer a question in integer linear
programming. As one of the fundamental classes of graphs, properties of
threshold graphs have been extensively studied (see [7, 9, 10, 14, 16]), and
since then many applications of these graphs have been found in various areas
(see [1, 6, 13, 15, 17]).

Threshold graphs can be characterized in a number of equivalent ways. For
example, $G$ is a threshold graph if and only if $G$ has no induced subgraph
isomorphic to $2K_{2},P_{4}$ or $C_{4}$ (see [3, 14]). Equivalently, a
threshold graph is a graph that can be obtained from the single-vertex graph
by repeatedly adding an isolated vertex or a universal vertex (see [3, 14]).
Moreover, $G$ is a threshold graph if and only if we can assign a real number
$r_{v}$ to each vertex $v$ and there is a real number $\theta$ such that for
any two distinct vertices $u$ and $v$, $uv$ is an edge if and only if
$r_{u}+r_{v}\geq\theta$ (see [14]).

Recently, Jamison and Sprague [12] introduced _multithreshold graphs_ as a
generalization of the well-studied threshold graphs as follows. A graph $G$ is
a _$k$ -threshold_ graph with _thresholds_
$\theta_{1},\theta_{2},\dots,\theta_{k}$ if we can assign a real number
$r_{v}$, called a _rank_ , to each vertex $v$ such that for any two distinct
vertices $u$ and $v$, $uv$ is an edge if and only if the number of thresholds
not exceeding $r_{u}+r_{v}$ is odd. Equivalently,

$\displaystyle uv\in E(G)\iff
r_{u}+r_{v}\in\left[\theta_{2i-1},\theta_{2i}\right)\hskip 2.84544pt\text{for
some}\hskip
2.84544pti\in\left\\{1,2,\dots,\left\lceil{\frac{k}{2}}\right\rceil\right\\}$

provided $\theta_{1}<\theta_{2}<\cdots<\theta_{k}$ and $\theta_{k+1}=\infty$.
We call such an assignment $r$ of ranks a
$\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-_representation of $G$_.
By a _rank sum of an edge/nonedge_ $uv$, we mean $r_{u}+r_{v}$. Note that the
case of one threshold agrees with the classical threshold graphs introduced by
Chvátal and Hammer [3].

Jamison and Sprague [12] showed that any graph of order $n$ is a $k$-threshold
graph for some $k\leq\binom{n}{2}$. The smallest $k$ for which a graph $G$ is
a $k$-threshold graph is said to be the _threshold number_ of $G$, denoted by
$\Theta(G)$. Observe that $\Theta(H)\leq\Theta(G)$ for any induced subgraph
$H$ of $G$. In addition, they found a relationship between the threshold
numbers of a graph and its complement. We give a proof for completeness.

######  Proposition 1 (Jamison and Sprague [12]).

For any graph $G$, either

$\displaystyle\Theta(G^{c})=\Theta(G)\ \text{or}\
\left\\{\Theta(G),\displaystyle\Theta(G^{c})\right\\}=\left\\{2k,2k+1\right\\}\
\text{for some}\ k\in\mathbb{N}.$

###### Proof.

Let $k$ and $k^{\prime}$ be such that $\Theta(G)\in\left\\{2k,2k+1\right\\}$
and $\displaystyle\Theta(G^{c})\in\left\\{2k^{\prime},2k^{\prime}+1\right\\}$.
Take a
$\left(\theta_{1},\theta_{2},\dots,\theta_{\Theta(G)}\right)$-representation
$r$ of $G$. We may assume that no rank sum equals a threshold by perturbing
each threshold to the left. We may further assume that $r$ has $2k+1$
thresholds by adding a sufficiently large threshold $\theta_{2k+1}$ if
neccesary. We then obtain a
$\left(-\theta_{2k+1},-\theta_{2k},\dots,-\theta_{1}\right)$-representation of
$\displaystyle G^{c}$ from $r$ by reversing the values of the ranks and the
thresholds. Thus $\displaystyle\Theta(G^{c})\leq 2k+1$, and so $k^{\prime}\leq
k$. Similarly, $\Theta(G)\leq 2k^{\prime}+1$, and so $k\leq k^{\prime}$. Now,
we have $k=k^{\prime}$, and hence
$\Theta(G),\displaystyle\Theta(G^{c})\in\left\\{2k,2k+1\right\\}$. ∎

This inspired Jamison and Sprague [12] to put forward the following
conjecture.

######  Conjecture 2 (Jamison and Sprague [12]).

For all $k\geq 1$, there is a graph $G$ with $\Theta(G)=2k$ and
$\displaystyle\Theta(G^{c})=2k+1$.

We denote by $K_{m_{1},m_{2},\dots,m_{n}}$ the complete $n$-partite graph with
$m_{i}$ vertices in the $i^{th}$ part for $1\leq i\leq n$, and by $K_{n\times
m}$ the complete $n$-partite graph with $m$ vertices in each part. Jamison and
Sprague [12] observed that, by assigning the rank $3^{i}$ to each vertex of
the $i^{th}$ part of $K_{m_{1},m_{2},\dots,m_{n}}$, the threshold number is at
most $2n$, and they left the following problem.

######  Problem 3 (Jamison and Sprague [12]).

Determine the exact threshold number of $K_{m_{1},m_{2},\dots,m_{n}}$.

Chen and Hao [2] recently gave a partial solution of Problem 3 which also
confirmed Conjecture 2.

######  Theorem 4 (Chen and Hao [2]).

Let $m_{1},m_{2},\dots,m_{n}$ be $n\geq 2$ positive integers. If $m_{i}\geq
n+1$ for $i=1,2,\dots,n$, then

$\Theta(K_{m_{1},m_{2},\dots,m_{n}})=2n-2\ \ \text{and}\ \
\displaystyle\Theta(K_{m_{1},m_{2},\dots,m_{n}}^{c})=2n-1.$

However, their result is far from the truth when $m_{i}$ are small. For
instance, it is readily seen that the threshold number of $K_{n\times 1}$ is
$1$. Jamison and Sprague [12] observed that the threshold number of
$K_{n\times 2}$ is at most $3$ by making the nonedge rank sum in each part
equal. Chen and Hao [2] mentioned that it would be interesting to know the
value of $\Theta(K_{n\times 3})$. As a tool for answering a question of
Jamison, Puleo [18] proved that $\Theta(nK_{3})\geq n^{1/3}$, which in turn
provides a lower bound for $K_{n\times 3}$ by Proposition 1.

In this paper, our main results determine the exact threshold numbers of
$K_{n\times 3}$, $K_{n\times 4}$ and their complements $nK_{3}$, $nK_{4}$. The
theorems also give more examples satisfying Conjecture 2.

######  Theorem 5.

Let $p_{m}=m+\binom{m}{3}+2$ and $q_{m}=m+\binom{m}{3}+1$.

  1. (i)

For $n\geq 2$,

$\Theta(K_{n\times 3})=\left\\{\begin{array}[]{l}2m\hskip
22.76228pt\text{if}\hskip 5.69046ptn=p_{m-1},\\\ 2m+1\hskip
5.69046pt\text{if}\hskip 5.69046ptp_{m-1}<n<p_{m}.\end{array}\right.$

  2. (ii)

For $n\geq 1$,

$\Theta(nK_{3})=\left\\{\begin{array}[]{l}2m-1\hskip 5.69046pt\text{if}\hskip
5.69046ptn=q_{m-1},\\\ 2m\hskip 22.76228pt\text{if}\hskip
5.69046ptq_{m-1}<n<q_{m}.\end{array}\right.$

######  Theorem 6.

Let
$s_{m}=m+\binom{\left\lfloor{m/2}\right\rfloor}{3}+\binom{\left\lceil{m/2}\right\rceil}{3}+2$
and
$t_{m}=m+\binom{\left\lfloor{m/2}\right\rfloor}{3}+\binom{\left\lceil{m/2}\right\rceil}{3}+1$.

  1. (i)

For $n\geq 2$,

$\Theta(K_{n\times 4})=\left\\{\begin{array}[]{l}2m\hskip
22.76228pt\text{if}\hskip 5.69046ptn=s_{m-1},\\\ 2m+1\hskip
5.69046pt\text{if}\hskip 5.69046pts_{m-1}<n<s_{m}.\end{array}\right.$

  2. (ii)

For $n\geq 1$,

$\Theta(nK_{4})=\left\\{\begin{array}[]{l}2m-1\hskip 5.69046pt\text{if}\hskip
5.69046ptn=t_{m-1},\\\ 2m\hskip 22.76228pt\text{if}\hskip
5.69046ptt_{m-1}<n<t_{m}.\end{array}\right.$

The proofs of the lower bounds for the threshold numbers are based on an idea
of Puleo [18]. We assign a color to each edge of $nK_{3}$ and $nK_{4}$
according to the location of its rank sum with respect to the thresholds. For
$nK_{3}$, we show that colors $ijj$ and $i\ell\ell$ cannot appear on two
triangles simultaneously. For $nK_{4}$, we prove that each $K_{4}$ must
contain a particular kind of $K_{3}$. These help us find the maximum value of
$n$ in terms of the number of colors.

The rest of this paper is organized as follows. In Section 2, we prove Theorem
5, and Section 3 is devoted to proving Theorem 6. Finally, we give some
concluding remarks in Section 4.

##  2 Threshold numbers of $K_{n\times 3}$ and $nK_{3}$

In this section, we determine the values of $\Theta(K_{n\times 3})$ and
$\Theta(nK_{3})$. To outline the proofs, we will need five lemmas. Lemmas 7 to
10 are for the lower bounds where the key idea is in Lemma 8. We apply Lemmas
7 and 8 to prove Lemma 9, which determines the maximum number of triangles and
parts in terms of the number of colors. Lemma 10 helps improve the lower
bounds obtained from Lemma 9. On the other hand, Lemma 11 is a tool to prove
the upper bounds.

We start by assigning a color to each edge of $nK_{3}$ and each nonedge of
$K_{n\times 3}$ as follows. In a
$\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-representation of
$nK_{3}$ where $\theta_{1}<\theta_{2}<\cdots<\theta_{k}$, we color an edge
$uv$ with _color $i$_, for
$i\in\left\\{1,2,\dots,\left\lceil{\frac{k}{2}}\right\rceil\right\\}$, if
$r_{u}+r_{v}\in\left[\theta_{2i-1},\theta_{2i}\right)$. We say that a triangle
has a _color_ $ij\ell$ if the colors appearing on its edges are $i,j$ and
$\ell$.

Similarly, in a
$\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-representation of
$K_{n\times 3}$ where $\theta_{1}<\theta_{2}<\cdots<\theta_{k}$, we color a
nonedge $xy$ with _color $i$_, for
$i\in\left\\{1,2,\dots,\left\lceil{\frac{k+1}{2}}\right\rceil\right\\}$, if
$r_{x}+r_{y}\in\left[\theta_{2i-2},\theta_{2i-1}\right)$ where
$\theta_{0}=-\infty$. We say that a part has a _color_ $ij\ell$ if the colors
appearing on its nonedges are $i,j$ and $\ell$.

First, we need a result of Puleo [18] which says that no two triangles in
$nK_{3}$ have the same color. Interchanging edges and nonedges, no two parts
in $K_{n\times 3}$ have the same color. We include a proof for completeness.

######  Lemma 7 (Puleo [18]).

  1. (i)

In a $\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-representation of
$nK_{3}$, no two triangles have the same color.

  2. (ii)

In a $\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-representation of
$K_{n\times 3}$, no two parts have the same color.

###### Proof.

We will only prove $(i)$ as the proof of $(ii)$ is similar. Let $r$ be a
$\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-representation of
$nK_{3}$ where $\theta_{1}<\theta_{2}<\cdots<\theta_{k}$. Suppose to the
contrary that there are two triangles $T_{x}$ and $T_{y}$ in $nK_{3}$ having
the same color $ij\ell$. Thus if $V(T_{x})=\\{x_{1},x_{2},x_{3}\\}$ and
$V(T_{y})=\\{y_{1},y_{2},y_{3}\\}$, then their edge rank sums are as follows:

$\displaystyle r_{x_{1}}+r_{x_{2}},r_{y_{1}}+r_{y_{2}}$
$\displaystyle\in\left[\theta_{2i-1},\theta_{2i}\right),$ $\displaystyle
r_{x_{1}}+r_{x_{3}},r_{y_{1}}+r_{y_{3}}$
$\displaystyle\in\left[\theta_{2j-1},\theta_{2j}\right),$ $\displaystyle
r_{x_{2}}+r_{x_{3}},r_{y_{2}}+r_{y_{3}}$
$\displaystyle\in\left[\theta_{2\ell-1},\theta_{2\ell}\right).$

Note that at least two ranks out of
$\max\left\\{r_{x_{1}},r_{y_{1}}\right\\},\max\left\\{r_{x_{2}},r_{y_{2}}\right\\},\max\left\\{r_{x_{3}},r_{y_{3}}\right\\}$
are from the same triangle. Without loss of generality, let $r_{x_{1}}\leq
r_{y_{1}}$ and $r_{x_{2}}\leq r_{y_{2}}$. Write
$r_{x_{p}}=\min\left\\{r_{x_{1}},r_{x_{2}}\right\\}$ and
$r_{y_{q}}=\max\left\\{r_{y_{1}},r_{y_{2}}\right\\}$. Then $\theta_{2i-1}\leq
r_{x_{1}}+r_{x_{2}}\leq r_{x_{p}}+r_{y_{q}}\leq
r_{y_{1}}+r_{y_{2}}<\theta_{2i}$. By the definition of thresholds,
$x_{p}y_{q}$ is an edge of color $i$, which contradicts the fact that
$x_{p}y_{q}$ is a nonedge in $nK_{3}$. ∎

The next lemma is the key idea for obtaining the lower bounds for the
threshold numbers.

######  Lemma 8.

  1. (i)

In a $\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-representation of
$nK_{3}$ and colors
$i,j,\ell\in\left\\{1,2,\dots,\left\lceil{\frac{k}{2}}\right\rceil\right\\}$,
colors $ijj$ and $i\ell\ell$ cannot appear on two triangles simultaneously.

  2. (ii)

In a $\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-representation of
$K_{n\times 3}$ and colors
$i,j,\ell\in\left\\{1,2,\dots,\left\lceil{\frac{k+1}{2}}\right\rceil\right\\}$,
colors $ijj$ and $i\ell\ell$ cannot appear on two parts simultaneously.

###### Proof.

We will only prove $(i)$ as the proof of $(ii)$ is similar. Let $r$ be a
$\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-representation of
$nK_{3}$ where $\theta_{1}<\theta_{2}<\cdots<\theta_{k}$. Suppose to the
contrary that there are two triangles $T_{x}$ and $T_{y}$ in $nK_{3}$ of
colors $ijj$ and $i\ell\ell$ respectively. Thus if
$V(T_{x})=\\{x_{1},x_{2},x_{3}\\}$ and $V(T_{y})=\\{y_{1},y_{2},y_{3}\\}$,
then their edge rank sums are as follows:

$\displaystyle a_{1}$
$\displaystyle=r_{x_{1}}+r_{x_{3}}\in\left[\theta_{2i-1},\theta_{2i}\right),$
$\displaystyle b_{1}$
$\displaystyle=r_{x_{1}}+r_{x_{2}}\in\left[\theta_{2j-1},\theta_{2j}\right),$
$\displaystyle b_{2}$
$\displaystyle=r_{x_{2}}+r_{x_{3}}\in\left[\theta_{2j-1},\theta_{2j}\right),$
$\displaystyle a_{2}$
$\displaystyle=r_{y_{1}}+r_{y_{3}}\in\left[\theta_{2i-1},\theta_{2i}\right),$
$\displaystyle c_{1}$
$\displaystyle=r_{y_{1}}+r_{y_{2}}\in\left[\theta_{2\ell-1},\theta_{2\ell}\right),$
$\displaystyle c_{2}$
$\displaystyle=r_{y_{2}}+r_{y_{3}}\in\left[\theta_{2\ell-1},\theta_{2\ell}\right).$

From these rank sums, we can compute the ranks as follows:

$\displaystyle r_{x_{1}}$ $\displaystyle=\frac{a_{1}+b_{1}-b_{2}}{2},\ $
$\displaystyle r_{x_{2}}$ $\displaystyle=\frac{b_{1}+b_{2}-a_{1}}{2},\ $
$\displaystyle r_{x_{3}}$ $\displaystyle=\frac{a_{1}+b_{2}-b_{1}}{2},$
$\displaystyle r_{y_{1}}$ $\displaystyle=\frac{a_{2}+c_{1}-c_{2}}{2},\ $
$\displaystyle r_{y_{2}}$ $\displaystyle=\frac{c_{1}+c_{2}-a_{2}}{2},\ $
$\displaystyle r_{y_{3}}$ $\displaystyle=\frac{a_{2}+c_{2}-c_{1}}{2}.$

Without loss of generality, let $a_{1}\leq a_{2}$, $b_{1}\leq b_{2}$ and
$c_{1}\leq c_{2}$. Let $D=a_{2}-a_{1}\geq 0$ and let

$\displaystyle A$ $\displaystyle=b_{1}-b_{2}+c_{1}-c_{2},$ $\displaystyle B$
$\displaystyle=-b_{1}+b_{2}+c_{1}-c_{2},$ $\displaystyle C$
$\displaystyle=-b_{1}+b_{2}-c_{1}+c_{2}.$

Note that $A\leq B\leq C$ and $A\leq 0$. Since $D\geq 0\geq A$, either
$D\in[A,B]$, $D\in[B,C]$ or $D\in[C,\infty)$. We obtain a contradiction by the
following three claims.

######  Claim.

$D\notin[A,B]$.

Since $x_{2}y_{3}$ is a nonedge, we cannot have $b_{1}\leq
r_{x_{2}}+r_{y_{3}}\leq b_{2}$; otherwise,
$r_{x_{2}}+r_{y_{3}}\in\left[\theta_{2j-1},\theta_{2j}\right)$. Observe that

$\displaystyle b_{1}\leq r_{x_{2}}+r_{y_{3}}\leq b_{2}$ $\displaystyle\iff
b_{1}\leq\frac{b_{1}+b_{2}-a_{1}}{2}+\frac{a_{2}+c_{2}-c_{1}}{2}\leq b_{2}$
$\displaystyle\iff b_{1}-b_{2}+c_{1}-c_{2}\leq a_{2}-a_{1}\leq-
b_{1}+b_{2}+c_{1}-c_{2}$ $\displaystyle\iff A\leq D\leq B.$

######  Claim.

$D\notin[B,C]$.

Since $x_{3}y_{2}$ is a nonedge, we cannot have $c_{1}\leq
r_{x_{3}}+r_{y_{2}}\leq c_{2}$; otherwise,
$r_{x_{3}}+r_{y_{2}}\in\left[\theta_{2\ell-1},\theta_{2\ell}\right)$. Note
that

$\displaystyle c_{1}\leq r_{x_{3}}+r_{y_{2}}\leq c_{2}$ $\displaystyle\iff
c_{1}\leq\frac{a_{1}+b_{2}-b_{1}}{2}+\frac{c_{1}+c_{2}-a_{2}}{2}\leq c_{2}$
$\displaystyle\iff-b_{1}+b_{2}+c_{1}-c_{2}\leq a_{2}-a_{1}\leq-
b_{1}+b_{2}-c_{1}+c_{2}$ $\displaystyle\iff B\leq D\leq C.$

######  Claim.

$D\notin[C,\infty)$.

Since $x_{3}y_{3}$ is a nonedge, we cannot have $a_{1}\leq
r_{x_{3}}+r_{y_{3}}\leq a_{2}$; otherwise,
$r_{x_{3}}+r_{y_{3}}\in\left[\theta_{2i-1},\theta_{2i}\right)$. Observe that

$\displaystyle a_{1}\leq r_{x_{3}}+r_{y_{3}}\leq a_{2}$ $\displaystyle\iff
a_{1}\leq\frac{a_{1}+b_{2}-b_{1}}{2}+\frac{a_{2}+c_{2}-c_{1}}{2}\leq a_{2}$
$\displaystyle\iff a_{1}-a_{2}\leq-b_{1}+b_{2}-c_{1}+c_{2}\leq a_{2}-a_{1}$
$\displaystyle\iff-D\leq C\leq D.\qed$

We apply Lemmas 7 and 8 to determine the maximum number of triangles and parts
in terms of the number of colors, which in turn gives lower bounds for the
threshold numbers.

######  Lemma 9.

  1. (i)

If there are at most $m$ colors of edges in $nK_{3}$, then $n\leq
m+\binom{m}{3}$. In particular, if $nK_{3}$ is a $k$-threshold graph, then
$n\leq\left\lceil{\frac{k}{2}}\right\rceil+\binom{\left\lceil
k/2\right\rceil}{3}$.

  2. (ii)

If there are at most $m$ colors of nonedges in $K_{n\times 3}$, then $n\leq
m+\binom{m}{3}$. In particular, if $K_{n\times 3}$ is a $k$-threshold graph,
then
$n\leq\left\lceil{\frac{k+1}{2}}\right\rceil+\binom{\left\lceil(k+1)/2\right\rceil}{3}$.

###### Proof.

We will only prove $(i)$ as the proof of $(ii)$ is similar. Suppose that there
are at most $m$ colors of edges in $nK_{3}$. By Lemma 7, there are at most
$\binom{m}{3}$ triangles in $nK_{3}$ whose edges are colored with $3$ colors.
It is sufficient to show that there are at most $m$ triangles in $nK_{3}$
whose edges are colored with $1$ or $2$ colors. Indeed, for each color $i$,
there is at most one triangle of color of the form $ijj$ where $j\in[m]$ by
Lemma 8. Thus $n\leq m+\binom{m}{3}$. Note that if $nK_{3}$ is a $k$-threshold
graph, then there are at most $\left\lceil\frac{k}{2}\right\rceil$ colors of
edges in $nK_{3}$, and hence,
$n\leq\left\lceil{\frac{k}{2}}\right\rceil+\binom{\left\lceil
k/2\right\rceil}{3}$. ∎

The lower bounds for the threshold numbers obtained from Lemma 9 are not
sharp. We require another observation which states roughly that the first and
last colors appear in at most one triangle or part.

######  Lemma 10.

  1. (i)

In a $\left(\theta_{1},\theta_{2},\dots,\theta_{2m-1}\right)$-representation
of $nK_{3}$, an edge of color $m$ appears in at most one triangle.

  2. (ii)

In a $\left(\theta_{1},\theta_{2},\dots,\theta_{m}\right)$-representation of
$K_{n\times 3}$, a nonedge of color $1$ appears in at most one part.

  3. (iii)

In a $\left(\theta_{1},\theta_{2},\dots,\theta_{2m}\right)$-representation of
$K_{n\times 3}$, a nonedge of color $m+1$ appears in at most one part.

###### Proof.

We only prove $(i)$ as the proofs of $(ii)$ and $(iii)$ are similar. Let $r$
be a $\left(\theta_{1},\theta_{2},\dots,\theta_{2m-1}\right)$-representation
of $nK_{3}$. Suppose to the contrary that there are two triangles $T_{x}$ and
$T_{y}$ in $nK_{3}$ with an edge of color $m$. Let $x_{1},x_{2},x_{3}$ and
$y_{1},y_{2},y_{3}$ be vertices of $T_{x}$ and $T_{y}$ respectively where
$x_{1}x_{2}$ and $y_{1}y_{2}$ are edges of color $m$, that is
$r_{x_{1}}+r_{x_{2}}$, $r_{y_{1}}+r_{y_{2}}\geq\theta_{2m-1}$. Assume without
loss of generality that $r_{x_{1}},r_{y_{1}}\geq\frac{\theta_{2m-1}}{2}$. Thus
$r_{x_{1}}+r_{y_{1}}\geq\theta_{2m-1}$, which implies that $x_{1}y_{1}$ is an
edge in $nK_{3}$, a contradiction. ∎

The upper bounds for the threshold numbers will be obtained by rank
assignments of the following forms. A rank assignment $r$ of $nK_{3}$ is said
to be an _$\left\\{a_{1},a_{2},\dots,a_{m}\right\\}$ -assignment_ if each
triangle has edge rank sums of the form $a_{i},a_{i},a_{i}$ or
$a_{i},a_{j},a_{k}$ for distinct $i,j,k\in[m]$, and no two triangles have the
same multiset of edge rank sums. Note that if $n\leq m+\binom{m}{3}$, then an
$\left\\{a_{1},a_{2},\dots,a_{m}\right\\}$-assignment of $nK_{3}$ exists since
we can assign any edge rank sums for each triangle as a triangle has edge rank
sums $a_{i},a_{j},a_{k}$ if and only if its ranks are
$\frac{a_{i}+a_{j}-a_{k}}{2},\frac{a_{i}+a_{k}-a_{j}}{2},\frac{a_{j}+a_{k}-a_{i}}{2}$.

In the same fasion, a rank assignment $r$ of $K_{n\times 3}$ is said to be an
_$\left\\{a_{1},a_{2},\dots,a_{m}\right\\}$ -assignment_ if each part has
nonedge rank sums of the form $a_{i},a_{i},a_{i}$ or $a_{i},a_{j},a_{k}$ for
distinct $i,j,k\in[m]$, and no two parts have the same multiset of nonedge
rank sums. Observe that an
$\left\\{a_{1},a_{2},\dots,a_{m}\right\\}$-assignment of $K_{n\times 3}$
exists whenever $n\leq m+\binom{m}{3}$.

The linear independence of $\left\\{a_{1},a_{2},\dots,a_{m}\right\\}$ over
$\mathbb{Q}$ is a sufficient condition for the edge and nonedge rank sums in
an $\left\\{a_{1},a_{2},\dots,a_{m}\right\\}$-assignment not to coincide.

######  Lemma 11.

Let $\left\\{a_{1},a_{2},\dots,a_{m}\right\\}\subset\mathbb{R}$ be a linearly
independent set over $\mathbb{Q}$.

  1. (i)

In an $\left\\{a_{1},a_{2},\dots,a_{m}\right\\}$-assignment of $nK_{3}$, the
edge and nonedge rank sums do not coincide.

  2. (ii)

In an $\left\\{a_{1},a_{2},\dots,a_{m}\right\\}$-assignment of $K_{n\times
3}$, the edge and nonedge rank sums do not coincide.

###### Proof.

$(i)$ Let $\left\\{a_{1},a_{2},\dots,a_{m}\right\\}\subset\mathbb{R}$ be a
linearly independent set over $\mathbb{Q}$ and let $r$ be the
$\left\\{a_{1},a_{2},\dots,a_{m}\right\\}$-assignment of $nK_{3}$. Suppose to
the contrary that there exists a nonedge $xy$ in $nK_{3}$ such that
$r_{x}+r_{y}=a_{\ell}$ for some $\ell\in[m]$. Since each triangle has edge
rank sums of the form $a_{i},a_{j},a_{k}$ where $i,j,k\in[m]$ are all equal or
all distinct, the rank of each vertex is of the form
$\frac{a_{i}+a_{j}-a_{k}}{2}$. Thus we suppose that
$r_{x}=\frac{a_{i}+a_{j}-a_{k}}{2}$ and $r_{y}=\frac{a_{r}+a_{s}-a_{t}}{2}$
where $i,j,k\in[m]$ are all equal or all distinct, $r,s,t\in[m]$ are all equal
or all distinct, and $\left\\{i,j,k\right\\}\neq\left\\{r,s,t\right\\}$.
Hence, $r_{x}+r_{y}=a_{\ell}$ becomes

$a_{i}+a_{j}-a_{k}+a_{r}+a_{s}-a_{t}=2a_{\ell}.$

Since
$\left\\{a_{i},a_{j},a_{k}\right\\}\neq\left\\{a_{r},a_{s},a_{t}\right\\}$,
there exists an element in one set not appearing in the other set, say
$a_{i}\notin\left\\{a_{r},a_{s},a_{t}\right\\}$. Since $i,j,k$ are all equal
or all distinct, the coefficient of $a_{i}$ after simplifying the left hand
side of the equation is $1$. Thus the left hand side cannot equal $2a_{\ell}$,
a contradiction.

The proof of $(ii)$ is similar. ∎

We are now ready to prove Theorem 5$(i)$.

###### Proof of Theorem 5$(i)$.

Let $m$ be such that $q_{m-1}\leq n<q_{m}$. Suppose to the contrary that
$\Theta(nK_{3})\leq 2m-2$. By Lemma 9$(i)$,

$n\leq\left\lceil{\frac{\Theta(nK_{3})}{2}}\right\rceil+\binom{\left\lceil\frac{\Theta(nK_{3})}{2}\right\rceil}{3}\leq\left\lceil{\frac{2m-2}{2}}\right\rceil+\binom{\left\lceil\frac{2m-2}{2}\right\rceil}{3}=(m-1)+\binom{m-1}{3}=q_{m-1}-1$

contradicting the definition of $m$. Thus $\Theta(nK_{3})\geq 2m-1$.

To prove that $\Theta(nK_{3})\leq 2m$, let
$A=\left\\{a_{1},a_{2},\dots,a_{m}\right\\}\subset\mathbb{R^{+}}$ be a
linearly independent set over $\mathbb{Q}$, for example, let
$a_{i}=\sqrt{p_{i}}$ where $p_{i}$ is the $i^{\text{th}}$ prime number. Since
$n\leq q_{m}-1=m+\binom{m}{3}$, we can pick an $A$-assignment for $nK_{3}$. By
Lemma 11$(i)$, the edge and nonedge rank sums do not coincide. We separate the
edge and nonedge rank sums by putting two thresholds around each edge rank
sum. For $i=1,2,\dots,m$, let $\theta_{2i-1}=a_{i}$ and
$\theta_{2i}=a_{i}+\varepsilon$ be thresholds of $nK_{3}$ where $\varepsilon$
is a sufficiently small positive real number, for example, take $\varepsilon$
smaller than any distance between two distinct rank sums of $nK_{3}$. Thus the
above rank assignment is a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m}\right)$-representation of
$nK_{3}$. Hence, $nK_{3}$ is a $2m$-threshold graph, that is
$\Theta(nK_{3})\leq 2m$ as desired.

Suppose that $n=q_{m-1}$. To prove that $\Theta(nK_{3})\leq 2m-1$, let
$A=\left\\{a_{1},a_{2},\dots,a_{m}\right\\}\subset\mathbb{R^{+}}$ be a
linearly independent set over $\mathbb{Q}$ such that
$a_{1}<a_{2}<\dots<a_{m-1}\leq\frac{a_{m}}{2}$. We then pick an
$A\setminus\left\\{a_{m}\right\\}$-assignment for the first
$(m-1)+\binom{m-1}{3}$ triangles in $nK_{3}$, and let the last triangle have
edge rank sums $a_{m},a_{m},a_{m}$. Note that this is an $A$-assignment of
$nK_{3}$. By Lemma 11$(i)$, the edge and nonedge rank sums do not coincide. We
separate the edge and nonedge rank sums by putting two thresholds around each
edge rank sum. For $i=1,2,\dots,m$, let $\theta_{2i-1}=a_{i}$ and
$\theta_{2i}=a_{i}+\varepsilon$ be thresholds of $nK_{3}$ where $\varepsilon$
is a sufficiently small positive real number. Thus the above rank assignment
is a $\left(\theta_{1},\theta_{2},\dots,\theta_{2m}\right)$-representation of
$nK_{3}$. In fact, we will show that we do not need the last threshold
$\theta_{2m}$ by proving that no rank sum exceeds $\theta_{2m-1}$. It is
sufficient to show that the rank of each vertex is at most
$\frac{\theta_{2m-1}}{2}=\frac{a_{m}}{2}$. This is clear for the last triangle
with edge rank sums $a_{m},a_{m},a_{m}$. For the other triangles, the rank of
each vertex is of the form $\frac{a_{i}+a_{j}-a_{k}}{2}$ for some
$i,j,k\in[m-1]$, which is at most $\frac{a_{m}}{2}$ since
$a_{i},a_{j}\leq\frac{a_{m}}{2}$ and $a_{k}>0$. Thus the above rank assignment
is a $\left(\theta_{1},\theta_{2},\dots,\theta_{2m-1}\right)$-representation
of $nK_{3}$. Therefore, $nK_{3}$ is a $(2m-1)$-threshold graph, that is
$\Theta(nK_{3})\leq 2m-1$ as desired.

Suppose that $n>q_{m-1}$. To prove that $\Theta(nK_{3})\geq 2m$, we suppose
that $\Theta(nK_{3})\leq 2m-1$. Let $r$ be a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m-1}\right)$-representation of
$nK_{3}$. Then there are at most $m$ colors of edges in $nK_{3}$. By Lemma
9$(i)$, there are at most $q_{m-1}-1$ triangles without color $m$. By Lemma
10$(i)$, an edge of color $m$ appears in at most one triangle. Thus
$n\leq\left(q_{m-1}-1\right)+1$, a contradiction. Therefore,
$\Theta(nK_{3})\geq 2m$. ∎

By applying Theorem 5$(i)$ together with Proposition 1, we can narrow down the
possible values of $\Theta(K_{n\times 3})$ to just two numbers.

###### Proof of Theorem 5$(ii)$.

Let $m$ be such that $p_{m-1}\leq n<p_{m}$. By Theorem 5$(i)$,
$\Theta(nK_{3})\in\left\\{2m,2m+1\right\\}$, and hence $\Theta(K_{n\times
3})\in\left\\{2m,2m+1\right\\}$ by Proposition 1.

Suppose that $n=p_{m-1}$. To prove that $\Theta(K_{n\times 3})\leq 2m$, let
$A=\left\\{a_{1},a_{2},\dots,a_{m+1}\right\\}\subset\mathbb{R}$ be a linearly
independent set over $\mathbb{Q}$ such that $a_{1}<a_{2}<\dots<a_{m+1}$,
$-\left|a_{i}\right|\geq\frac{a_{1}}{3}$ and
$\left|a_{i}\right|\leq\frac{a_{m+1}}{3}$ for all
$i\in[m]\setminus\left\\{1\right\\}$. We pick an
$A\setminus\left\\{a_{1},a_{m+1}\right\\}$-assignment for the first
$(m-1)+\binom{m-1}{3}$ parts in $K_{n\times 3}$, and let the last two parts
have nonedge rank sums $a_{1},a_{1},a_{1}$ and $a_{m+1},a_{m+1},a_{m+1}$. Note
that this is an $A$-assignment of $K_{n\times 3}$. By Lemma 11$(ii)$, the edge
and nonedge rank sums do not coincide. Let $\theta_{1}$ be smaller than all
rank sums. We then separate the edge and nonedge rank sums by putting two
thresholds around each interval of nonedge rank sums. For $i=1,2,\dots,m+1$,
let $\theta_{2i}=a_{i}$ and $\theta_{2i+1}=a_{i}+\varepsilon$ where
$\varepsilon$ is a sufficiently small positive real number. Thus the above
rank assignment is a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m+3}\right)$-representation of
$K_{n\times 3}$. In fact, we will show that we do not need the thresholds
$\theta_{1},\theta_{2}$ and $\theta_{2m+3}$ by proving that no rank sum is
smaller than $\theta_{2}$ or larger than $\theta_{2m+2}$. It is sufficient to
show that the rank of each vertex is at least
$\frac{\theta_{2}}{2}=\frac{a_{1}}{2}$ and at most
$\frac{\theta_{2m+2}}{2}=\frac{a_{m+1}}{2}$. This is clear for the last two
parts with nonedge rank sums $a_{1},a_{1},a_{1}$ and
$a_{m+1},a_{m+1},a_{m+1}$. For the other parts, the rank of each vertex is of
the form $\frac{a_{i}+a_{j}-a_{k}}{2}$ for some
$i,j,k\in[m]\setminus\left\\{1\right\\}$, which is at least $\frac{a_{1}}{2}$
and at most $\frac{a_{m+1}}{2}$ since $\frac{a_{1}}{3}\leq
a_{i},a_{j},-a_{k}\leq\frac{a_{m+1}}{3}$. Thus the above rank assignment is a
$\left(\theta_{3},\theta_{4},\dots,\theta_{2m+2}\right)$-representation of
$K_{n\times 3}$. Therefore, $K_{n\times 3}$ is a $2m$-threshold graph, that is
$\Theta(K_{n\times 3})\leq 2m$ as desired.

Suppose that $n>p_{m-1}$. To prove that $\Theta(K_{n\times 3})\geq 2m+1$, we
suppose that $\Theta(K_{n\times 3})\leq 2m$. Let $r$ be a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m}\right)$-representation of
$K_{n\times 3}$. Then there are at most $m+1$ colors of nonedges in
$K_{n\times 3}$. By Lemma 9$(ii)$, there are at most $p_{m-1}-2$ parts without
colors $1$ and $m+1$. By Lemma 10$(ii)$ and 10$(iii)$, a nonedge of color $1$
appears in at most one part and a nonedge of color $m+1$ also appears in at
most one part. Therefore, $n\leq\left(p_{m-1}-2\right)+1+1$, a contradiction.
∎

##  3 Threshold numbers of $K_{n\times 4}$ and $nK_{4}$

In this section, we focus on the threshold numbers of $K_{n\times 4}$ and
$nK_{4}$. We will need Lemmas 7 and 8 as well as five new lemmas. Lemma 12
identifies all sets of edge rank sums that can appear in a $K_{4}$. Lemmas 13
and 14 are for the lower bounds where the key idea is in Lemma 13. We apply
Lemmas 7 and 8 to prove Lemma 13, which provide the maximum number of
$K_{4}$’s and parts in terms of the number of colors. Lemma 14 improves the
lower bounds obtained from Lemma 13. On the other hand, Lemma 16 which is a
tool to prove the upper bounds utilizes Lemma 15 in its proof.

We start by assigning a color to each edge of $nK_{4}$ and each nonedge of
$K_{n\times 4}$ as follows. In a
$\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-representation of
$nK_{4}$ where $\theta_{1}<\theta_{2}<\cdots<\theta_{k}$, we color an edge
$uv$ with _color $i$_, for
$i\in\left\\{1,2,\dots,\left\lceil{\frac{k}{2}}\right\rceil\right\\}$, if
$r_{u}+r_{v}\in\left[\theta_{2i-1},\theta_{2i}\right)$. Similarly, in a
$\left(\theta_{1},\theta_{2},\dots,\theta_{k}\right)$-representation of
$K_{n\times 4}$ where $\theta_{1}<\theta_{2}<\cdots<\theta_{k}$, we color a
nonedge $xy$ with _color $i$_, for
$i\in\left\\{1,2,\dots,\left\lceil{\frac{k+1}{2}}\right\rceil\right\\}$, if
$r_{x}+r_{y}\in\left[\theta_{2i-2},\theta_{2i-1}\right)$ where
$\theta_{0}=-\infty$.

$a_{1}$$a_{3}$$a_{2}$$b_{2}$$b_{3}$$b_{1}$ Figure 1:
$K_{4}\left(a_{1},b_{1},a_{2},b_{2},a_{3},b_{3}\right)$

We denote by $K_{4}\left(a_{1},b_{1},a_{2},b_{2},a_{3},b_{3}\right)$ a $K_{4}$
each of whose vertices is assigned a rank so that the edge rank sums are
$a_{1}$, $b_{1}$, $a_{2}$, $b_{2}$, $a_{3}$, $b_{3}$ where $a_{i}$ and $b_{i}$
belong to a perfect matching for each $i$ as shown in Figure 1. Observe that
$K_{4}\left(a_{1},b_{1},a_{2},b_{2},a_{3},b_{3}\right)$ and
$K_{4}\left(a_{1},b_{1},a_{2},b_{2},b_{3},a_{3}\right)$ are not isomorphic,
while $K_{4}\left(b_{1},a_{1},a_{2},b_{2},a_{3},b_{3}\right)$,
$K_{4}\left(a_{1},b_{1},b_{2},a_{2},a_{3},b_{3}\right)$ and
$K_{4}\left(a_{1},b_{1},a_{2},b_{2},b_{3},a_{3}\right)$ are isomorphic. For
convenience, we write $K_{4}\left(c\right)$ for
$K_{4}\left(c,c,c,c,c,c\right)$.

In the same fasion, we denote by
$E_{4}\left(a_{1},b_{1},a_{2},b_{2},a_{3},b_{3}\right)$ an empty graph on four
vertices having nonedge rank sums $a_{1},b_{1},a_{2},b_{2},a_{3}$ and $b_{3}$
where $a_{i}$ and $b_{i}$ belong to an independent nonedges for each $i$.

It is easy to determine which edge rank sums
$a_{1},b_{1},a_{2},b_{2},a_{3},b_{3}$ can appear in a $K_{4}$.

######  Proposition 12.

The following statements are equivalent:

  1. (i)

$K_{4}\left(a_{1},b_{1},a_{2},b_{2},a_{3},b_{3}\right)$ exists.

  2. (ii)

$E_{4}\left(a_{1},b_{1},a_{2},b_{2},a_{3},b_{3}\right)$ exists.

  3. (iii)

$a_{1}+b_{1}=a_{2}+b_{2}=a_{3}+b_{3}$.

###### Proof.

$(i)\Rightarrow(iii)$: Suppose that
$K_{4}\left(a_{1},b_{1},a_{2},b_{2},a_{3},b_{3}\right)$ exists, that is we can
assign a rank to each vertex so that the edge rank sums are $a_{1}$, $b_{1}$,
$a_{2}$, $b_{2}$, $a_{3}$, $b_{3}$ where $a_{i}$ and $b_{i}$ belong to a
perfect matching for each $i$. Since each perfect matching spans all vertices
of the graph, the summation of all ranks is equal to $a_{i}+b_{i}$ for each
$i$. Thus $a_{1}+b_{1}=a_{2}+b_{2}=a_{3}+b_{3}$ as desired.

$w$$x$$z$$y$$a_{1}$$a_{3}$$a_{2}$$b_{2}$$b_{3}$$b_{1}$ Figure 2:

$(iii)\Rightarrow(i)$: Let $\left\\{w,x,y,z\right\\}$ be the vertex set of
$K_{4}$. We will provide an assignment $r$ of ranks so that the graph is
$K_{4}\left(a_{1},b_{1},a_{2},b_{2},a_{3},b_{3}\right)$ as shown in Figure 2.
To obtain edge rank sums $b_{1},b_{2},b_{3}$ for the triangle $xyz$, we let

$\displaystyle r(x)=\frac{b_{2}+b_{3}-b_{1}}{2},\
r(y)=\frac{b_{1}+b_{3}-b_{2}}{2},\ r(z)=\frac{b_{1}+b_{2}-b_{3}}{2}.$

We immediately obtain $r(y)+r(z)=b_{1}$, $r(x)+r(z)=b_{2}$ and
$r(x)+r(y)=b_{3}$. Now, let $r(w)=\frac{a_{1}+a_{2}-b_{3}}{2}$. Thus

$\displaystyle
r(w)+r(x)=\frac{a_{1}+a_{2}-b_{3}}{2}+\frac{b_{2}+b_{3}-b_{1}}{2}=a_{1}\ \
\text{since $a_{1}+b_{1}=a_{2}+b_{2}$},$ $\displaystyle
r(w)+r(y)=\frac{a_{1}+a_{2}-b_{3}}{2}+\frac{b_{1}+b_{3}-b_{2}}{2}=a_{2}\ \
\text{since $a_{1}+b_{1}=a_{2}+b_{2}$},$ $\displaystyle
r(w)+r(z)=\frac{a_{1}+a_{2}-b_{3}}{2}+\frac{b_{1}+b_{2}-b_{3}}{2}=a_{3}\ \
\text{since $a_{1}+b_{1}=a_{2}+b_{2}=a_{3}+b_{3}$}.$

For $(ii)\Leftrightarrow(iii)$, the proof is similar. ∎

The following key lemma for the lower bounds for the threshold number,
determines the maximum numbers of $K_{4}$’s and parts in terms of the number
of colors. The crux of the proof is an observation that each $K_{4}$ must
contain a particular kind of $K_{3}$.

######  Lemma 13.

  1. (i)

If there are at most $m$ colors of edges in $nK_{4}$, then $n\leq
m+\binom{\left\lfloor m/2\right\rfloor}{3}+\binom{\left\lceil
m/2\right\rceil}{3}$. In particular, if $nK_{4}$ is a $k$-threshold graph,
then
$n\leq\left\lceil{\frac{k}{2}}\right\rceil+\binom{\left\lfloor(k+1)/4\right\rfloor}{3}+\binom{\left\lceil
k/4\right\rceil}{3}$.

  2. (ii)

If there are at most $m$ colors of nonedges in $K_{n\times 4}$, then $n\leq
m+\binom{\left\lfloor m/2\right\rfloor}{3}+\binom{\left\lceil
m/2\right\rceil}{3}$. In particular, if $K_{n\times 4}$ is a $k$-threshold
graph, then
$n\leq\left\lceil{\frac{k+1}{2}}\right\rceil+\binom{\left\lfloor(k+2)/4\right\rfloor}{3}+\binom{\left\lceil(k+1)/4\right\rceil}{3}$.

###### Proof.

We will only prove $(i)$ as the proof of $(ii)$ is similar. Let $r$ be a
representation of $nK_{4}$ such that there are at most $m$ colors of edges. We
decompose $nK_{4}$ into two subgraphs $G_{1}=n_{1}K_{4}$ and
$G_{2}=n_{2}K_{4}$ with $n=n_{1}+n_{2}$ such that $G_{1}$ consists of all
$K_{4}$’s containing a triangle whose edges are colored with $1$ or $2$ colors
and $G_{2}$ consists of all $K_{4}$’s with four triangles whose edges are
colored with $3$ colors. First, we show that $n_{1}\leq m$. Consider a
subgraph $n_{1}K_{3}$ of $G_{1}$ consisting of triangles whose edges are
colored with $1$ or $2$ colors. Applying Lemma 8 with the representation $r$
of $n_{1}K_{3}$, for each color $i\in[m]$, there is at most one triangle in
$n_{1}K_{3}$ of color of the form $ijj$ where $j\in[m]$. Thus $n_{1}\leq m$.

It remains to show that $n_{2}\leq\binom{\left\lfloor
m/2\right\rfloor}{3}+\binom{\left\lceil m/2\right\rceil}{3}$. Let
$\mathcal{L}$ be the set of triangles in $nK_{4}$ of colors $ij\ell$ where
$i,j,\ell\in\left\\{1,2,\dots,\left\lfloor\frac{m}{2}\right\rfloor\right\\}$
are all distinct and let $\mathcal{U}$ be the set of triangles in $nK_{4}$ of
colors $ij\ell$ where
$i,j,\ell\in\left\\{\left\lfloor\frac{m}{2}\right\rfloor+1,\left\lfloor\frac{m}{2}\right\rfloor+2,\dots,m\right\\}$
are all distinct.

######  Claim.

Each $K_{4}$ in $G_{2}$ contains at least one triangle in
$\mathcal{L}\cup\mathcal{U}$.

###### Proof of Claim.

Let $\left\\{v_{1},v_{2},v_{3},v_{4}\right\\}$ be the vertex set of $K_{4}$.
Suppose without loss of generality that $r_{v_{1}}\leq r_{v_{2}}\leq
r_{v_{3}}\leq r_{v_{4}}$. Then

$r_{v_{1}}+r_{v_{2}}\leq r_{v_{1}}+r_{v_{3}}\leq r_{v_{2}}+r_{v_{3}}\leq
r_{v_{2}}+r_{v_{4}}\leq r_{v_{3}}+r_{v_{4}}.$

Let $v_{2}v_{3}$ have color $i$. Thus $i$ is in either
$\left\\{1,2,\dots,\left\lfloor\frac{m}{2}\right\rfloor\right\\}$ or
$\left\\{\left\lfloor\frac{m}{2}\right\rfloor+1,\left\lfloor\frac{m}{2}\right\rfloor+2,\dots,m\right\\}$,
and hence either $v_{1}v_{2}v_{3}$ is in $\mathcal{L}$ or $v_{2}v_{3}v_{4}$ is
in $\mathcal{U}$. ∎

Consider a subgraph $n_{2}K_{3}$ of $G_{2}$ consisting of triangles in
$\mathcal{L}\cup\mathcal{U}$ which exists by Claim. Applying Lemma 7 with the
representation $r$ of $n_{2}K_{3}$, no two triangles in $n_{2}K_{3}$ have the
same color. Thus

$n_{2}\leq\left|\mathcal{L}\cup\mathcal{U}\right|\leq\binom{\left\lfloor\frac{m}{2}\right\rfloor}{3}+\binom{\left\lceil\frac{m}{2}\right\rceil}{3}.$

Observe that if $nK_{4}$ is a $k$-threshold graph, then there are at most
$\left\lceil\frac{k}{2}\right\rceil$ colors of edges in $nK_{4}$, and hence

$n\leq\left\lceil{\frac{k}{2}}\right\rceil+\binom{\left\lfloor\frac{\left\lceil
k/2\right\rceil}{2}\right\rfloor}{3}+\binom{\left\lceil\frac{\left\lceil
k/2\right\rceil}{2}\right\rceil}{3}=\left\lceil{\frac{k}{2}}\right\rceil+\binom{\left\lfloor\frac{k+1}{4}\right\rfloor}{3}+\binom{\left\lceil\frac{k}{4}\right\rceil}{3}.\qed$

Similarly to the case of $K_{3}$, the lower bounds for the threshold numbers
obtained from Lemma 13 are not sharp. We again need another observation which
says roughly that the first and last colors appear in at most one $K_{4}$ or
part.

######  Lemma 14.

  1. (i)

In a $\left(\theta_{1},\theta_{2},\dots,\theta_{2m-1}\right)$-representation
of $nK_{4}$, an edge of color $m$ appears in at most one $K_{4}$.

  2. (ii)

In a $\left(\theta_{1},\theta_{2},\dots,\theta_{m}\right)$-representation of
$K_{n\times 4}$, a nonedge of color $1$ appears in at most one part.

  3. (iii)

In a $\left(\theta_{1},\theta_{2},\dots,\theta_{2m}\right)$-representation of
$K_{n\times 4}$, a nonedge of color $m+1$ appears in at most one part.

###### Proof.

The proof is similar to that of Lemma 10. ∎

The upper bounds for the threshold numbers will be obtained from rank
assignments of the following forms. Let
$A=\left\\{a_{1},a_{2},\dots,a_{M}\right\\}$ and
$B=\left\\{b_{1},b_{2},\dots,b_{M}\right\\}$ be such that $a_{i}+b_{i}=N$ for
all $i\in[M]$. For $n=2M+2\binom{M}{3}$, the _$\left(A,B\right)$ -assignment_
is the rank assignment of $nK_{4}$ consisting of the following $K_{4}$’s:

$\displaystyle K_{4}\left(a_{i}\right)\ \text{for each}\ i\in[M],$
$\displaystyle K_{4}\left(b_{i}\right)\ \text{for each}\ i\in[M],$
$\displaystyle K_{4}\left(a_{i},b_{i},a_{j},b_{j},a_{k},b_{k}\right)\
\text{for each subset}\left\\{i,j,k\right\\}\subset[M]\ \text{of size}\ 3,$
$\displaystyle K_{4}\left(a_{i},b_{i},a_{j},b_{j},b_{k},a_{k}\right)\
\text{for each subset}\left\\{i,j,k\right\\}\subset[M]\ \text{of size}\ 3$

where each of them appears exactly once. Note that the numbers of $K_{4}$’s in
each line are $M$, $M$, $\binom{M}{3}$, $\binom{M}{3}$ respectively, and they
exist by Proposition 12.

Let $\varepsilon>0$. For $n=2M+1+\binom{M}{3}+\binom{M+1}{3}$, the
_$\left(A,B,\varepsilon\right)$ -assignment_ is the rank assignment of
$nK_{4}$ consisting of the following $K_{4}$’s:

$\displaystyle K_{4}\left(a_{i}\right)\ \text{for each}\ i\in[M],$
$\displaystyle K_{4}\left(b_{i}\right)\ \text{for each}\ i\in[M],$
$\displaystyle K_{4}\left(a_{i},b_{i},a_{j},b_{j},a_{k},b_{k}\right)\
\text{for each subset}\left\\{i,j,k\right\\}\subset[M]\ \text{of size}\ 3,$
$\displaystyle K_{4}\left(a_{i},b_{i},a_{j},b_{j},b_{k},a_{k}\right)\
\text{for each subset}\left\\{i,j,k\right\\}\subset[M]\ \text{of size}\ 3,$
$\displaystyle K_{4}\left(\frac{N}{2}+\varepsilon\right),$ $\displaystyle
K_{4}\left(a_{i}+\varepsilon,b_{i}+\varepsilon,a_{j}+\varepsilon,b_{j}+\varepsilon,\frac{N}{2}+\varepsilon,\frac{N}{2}+\varepsilon\right)\
\text{for each subset}\left\\{i,j\right\\}\subset[M]\ \text{of size}\ 2$

where each of them appears exactly once. Note that the numbers of $K_{4}$’s in
each line are $M$, $M$, $\binom{M}{3}$, $\binom{M}{3}$, $1$, $\binom{M}{2}$
respectively, and they exist by Proposition 12.

Occasionally, we say that a $K_{4}$ is of _type I_ if it is a
$K_{4}\left(a_{i}\right)$ or $K_{4}\left(b_{i}\right)$ for some $i\in[M]$,
_type II_ if it is a $K_{4}\left(a_{i},b_{i},a_{j},b_{j},a_{k},b_{k}\right)$
or $K_{4}\left(a_{i},b_{i},a_{j},b_{j},b_{k},a_{k}\right)$ for some subset
$\left\\{i,j,k\right\\}\subset[M]$ of size $3$, _type III_ if it is a
$K_{4}\left(\frac{N}{2}+\varepsilon\right)$, _type IV_ if it is a
$K_{4}\left(a_{i}+\varepsilon,b_{i}+\varepsilon,a_{j}+\varepsilon,b_{j}+\varepsilon,\frac{N}{2}+\varepsilon,\frac{N}{2}+\varepsilon\right)$
for some distinct $i,j\in[M]$. In the same fasion, we can define the
_$\left(A,B\right)$ -assignment_ and the _$\left(A,B,\varepsilon\right)$
-assignment_ of $K_{n\times 4}$ by replacing $K_{4}$ with $E_{4}$.

The following lemma will be used repeatedly in the proof of Lemma 16.

######  Lemma 15.

Let $\left\\{N,a_{1},a_{2},\dots,a_{M}\right\\}\subset\mathbb{R}$ be a
linearly independent set over $\mathbb{Q}$ and $b_{i}=N-a_{i}$ for
$i=1,2,\dots,M$. Let $A=\left\\{a_{1},a_{2},\dots,a_{M}\right\\}$ and
$B=\left\\{b_{1},b_{2},\dots,b_{M}\right\\}$. If

$\sum_{i=1}^{S}\alpha_{i}x_{i}+\beta N=0$

where $\alpha_{i}\in\mathbb{Z}$, $x_{i}\in A\cup B$ for all $i\in[S]$ and
$\beta\in\mathbb{Q}$, then $\sum_{i=1}^{S}\alpha_{i}$ is even.

###### Proof.

Suppose that $\sum_{i=1}^{S}\alpha_{i}x_{i}+\beta N=0$ where
$\alpha_{i}\in\mathbb{Z}$, $x_{i}\in A\cup B$ for all $i\in[S]$ and
$\beta\in\mathbb{Q}$. Observe that $x_{i}$ is either $a_{j_{i}}$ or
$b_{j_{i}}=N-a_{j_{i}}$ where $j_{i}\in[M]$. Then we can write
$x_{i}=\delta_{i}a_{j_{i}}+\beta_{i}N$ where
$\delta_{i}\in\left\\{-1,1\right\\}$ and $\beta_{i}\in\left\\{0,1\right\\}$.
The equation becomes

$\sum_{i=1}^{S}\delta_{i}\alpha_{i}a_{j_{i}}+\sum_{i=1}^{S}\beta_{i}\alpha_{i}N+\beta
N=0.$

Since $\left\\{N,a_{1},a_{2},\dots,a_{M}\right\\}$ is linearly independent
over $\mathbb{Q}$, we have $\sum_{i=1}^{S}\delta_{i}\alpha_{i}=0$. Hence,

$\sum_{i=1}^{S}\alpha_{i}=\sum_{i=1}^{S}\delta_{i}\alpha_{i}+2\sum_{\delta_{i}=-1}\alpha_{i}=2\sum_{\delta_{i}=-1}\alpha_{i}$

is even. ∎

The linear independence of $\left\\{N,a_{1},a_{2},\dots,a_{M}\right\\}$ over
$\mathbb{Q}$ is a sufficient condition for the edge and nonedge rank sums in
the $\left(A,B\right)$-assignment and in the
$\left(A,B,\varepsilon\right)$-assignment not to coincide. For the
$\left(A,B,\varepsilon\right)$-assignment, we prove further that there are
small intervals without nonedge rank sums that cover all edge rank sums.

######  Lemma 16.

Let $\left\\{N,a_{1},a_{2},\dots,a_{M}\right\\}\subset\mathbb{R}$ be a
linearly independent set over $\mathbb{Q}$ and $b_{i}=N-a_{i}$ for
$i=1,2,\dots,M$. Let $A=\left\\{a_{1},a_{2},\dots,a_{M}\right\\}$ and
$B=\left\\{b_{1},b_{2},\dots,b_{M}\right\\}$.

  1. (i)

Let $n=2M+2\binom{M}{3}$. In the $\left(A,B\right)$-assignment of $nK_{4}$,
the edge and nonedge rank sums do not coincide.

  2. (ii)

Let $n=2M+1+\binom{M}{3}+\binom{M+1}{3}$. Then there exists a positive real
number $\varepsilon$ such that, in the
$\left(A,B,\varepsilon\right)$-assignment of $nK_{4}$, no nonedge rank sum
lies in either $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ or
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all $i\in[M]$. Moreover, the
sets of the form $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ and
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all $i\in[M]$ are pairwise
disjoint.

  3. (iii)

Let $n=2M+2\binom{M}{3}$. In the $\left(A,B\right)$-assignment of $K_{n\times
4}$, the edge and nonedge rank sums do not coincide.

  4. (iv)

Let $n=2M+1+\binom{M}{3}+\binom{M+1}{3}$. Then there exists a positive real
number $\varepsilon$ such that, in the
$\left(A,B,\varepsilon\right)$-assignment of $K_{n\times 4}$, no edge rank sum
lies in either $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ or
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all $i\in[M]$. Moreover, the
sets of the form $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ and
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all $i\in[M]$ are pairwise
disjoint.

###### Proof.

For $(i)$ and $(ii)$, it is sufficient to prove $(ii)$ since every $K_{4}$ in
the $\left(A,B\right)$-assignment appears in the
$\left(A,B,\varepsilon\right)$-assignment and each edge rank sum in the
$\left(A,B\right)$-assignment is either $a_{i}$ or $b_{i}$. The proofs of
$(iii)$ and $(iv)$ are similar to those of $(i)$ and $(ii)$.

To prove $(ii)$, let $n=2M+1+\binom{M}{3}+\binom{M+1}{3}$. We first consider
the $\left(A,B,\varepsilon\right)$-assignment of $nK_{4}$ in the case when
$\varepsilon=0$.

######  Claim.

For the $\left(A,B,0\right)$-assignment $r^{\prime}$ of $nK_{4}$, no nonedge
rank sum lies in $A\cup B$.

###### Proof of Claim.

$x$ $y$ | I $K_{4}$ | II $K_{4}$ | III $K_{4}$ | IV $K_{4}$
---|---|---|---|---
I $K_{4}$ | Case 1 | Case 2 | Case 4 | Case 5
II $K_{4}$ |  | Case 3 | Case 6 | Case 7
III $K_{4}$ |  |  | Case 8 | Case 9
IV $K_{4}$ |  |  |  | Case 10
Table 1: Ten cases according to the four possible types of $K_{4}$ that $x$
and $y$ are in.

Suppose to the contrary that there exists a nonedge $xy$ in $nK_{4}$ such that
$r^{\prime}_{x}+r^{\prime}_{y}$ lies in $A\cup B$, say
$r^{\prime}_{x}+r^{\prime}_{y}=e_{t}\in\left\\{a_{t},b_{t}\right\\}$ for some
$t\in[M]$. We divide into cases according to the four possible types of
$K_{4}$ that $x$ and $y$ are in as shown in Table 1.

Observe that the rank of each vertex in a type I $K_{4}$ is of the form
$\frac{c_{i}}{2}$ where $i\in[M]$ and $c_{i}\in\left\\{a_{i},b_{i}\right\\}$,
that in a type II $K_{4}$ is of the form $\frac{c_{i}+c_{j}-c_{k}}{2}$ where
$i,j,k\in[M]$ are all distinct and
$c_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{i,j,k\right\\}$, that in a type III $K_{4}$ is of the form
$\frac{N}{4}$, and that in a type IV $K_{4}$ is of the form
$\frac{c_{i}+c_{j}-N/2}{2}$ where $i,j\in[M]$ are distinct and
$c_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{i,j\right\\}$.

Case 1. $x,y\in\text{type I}\ K_{4}$.

Then $x\in K_{4}\left(c_{i}\right)$ and $y\in K_{4}\left(d_{j}\right)$ where
$i,j\in[M]$ and $c_{i}\in\left\\{a_{i},b_{i}\right\\}$,
$d_{j}\in\left\\{a_{j},b_{j}\right\\}$. Thus $r^{\prime}_{x}=\frac{c_{i}}{2}$
and $r^{\prime}_{y}=\frac{d_{j}}{2}$. The equation
$r^{\prime}_{x}+r^{\prime}_{y}=e_{t}$ becomes

$c_{i}+d_{j}=2e_{t}.$

First, suppose that $i\neq j$. One of $i$ or $j$ cannot equal to $t$, say
$i\neq t$. By writing the equation in terms of the basis
$\left\\{N,a_{1},a_{2},\dots,a_{M}\right\\}$, we can see that the equality
cannot occur since $c_{i}$ is the only term in the equation involving $a_{i}$,
a contradiction. Now, suppose that $i=j$. Since $x$ and $y$ are in different
$K_{4}$’s, we have
$\left\\{c_{i},d_{j}\right\\}=\left\\{a_{i},b_{i}\right\\}$, and hence the
equation becomes $N=2e_{t}$, a contradiction.

Case 2. $x\in\text{type I}\ K_{4}$ and $y\in\text{type II}\ K_{4}$.

Then $x\in K_{4}\left(c_{i}\right)$ where $i\in[M]$ and
$c_{i}\in\left\\{a_{i},b_{i}\right\\}$, and $y$ is in either
$K_{4}\left(a_{p},b_{p},a_{q},b_{q},a_{s},b_{s}\right)$ or
$K_{4}\left(a_{p},b_{p},a_{q},b_{q},b_{s},a_{s}\right)$ where $p,q,s\in[M]$
are all distinct. Thus $r^{\prime}_{x}=\frac{c_{i}}{2}$ and
$r^{\prime}_{y}=\frac{d_{p}+d_{q}-d_{s}}{2}$ where
$d_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{p,q,s\right\\}$. The equation
$r^{\prime}_{x}+r^{\prime}_{y}=e_{t}$ becomes

$c_{i}+d_{p}+d_{q}-d_{s}=2e_{t}.$

Since $p,q,s$ are all distinct, there is an index in $\left\\{p,q,s\right\\}$
not appearing in $\left\\{i,t\right\\}$, say $p\notin\left\\{i,t\right\\}$.
Thus the equality cannot occur since $d_{p}$ is the only term in the equation
involving $a_{p}$, a contradiction.

Case 3. $x,y\in\text{type II}\ K_{4}$.

Then $x$ is in either $K_{4}\left(a_{i},b_{i},a_{j},b_{j},a_{k},b_{k}\right)$
or $K_{4}\left(a_{i},b_{i},a_{j},b_{j},b_{k},a_{k}\right)$ where $i,j,k\in[M]$
are all distinct, and $y$ is in either
$K_{4}\left(a_{p},b_{p},a_{q},b_{q},a_{s},b_{s}\right)$ or
$K_{4}\left(a_{p},b_{p},a_{q},b_{q},b_{s},a_{s}\right)$ where $p,q,s\in[M]$
are all distinct. Thus $r^{\prime}_{x}=\frac{c_{i}+c_{j}-c_{k}}{2}$ where
$c_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{i,j,k\right\\}$ and
$r^{\prime}_{y}=\frac{d_{p}+d_{q}-d_{s}}{2}$ where
$d_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{p,q,s\right\\}$. The equation
$r^{\prime}_{x}+r^{\prime}_{y}=e_{t}$ becomes

$c_{i}+c_{j}-c_{k}+d_{p}+d_{q}-d_{s}=2e_{t}.$

Case 3.1. $\left\\{i,j,k\right\\}\neq\left\\{p,q,s\right\\}$.

Then there is an index in $\left\\{i,j,k\right\\}$ not appearing in
$\left\\{p,q,s\right\\}$, say $i\notin\left\\{p,q,s\right\\}$. Similarly,
there is an index in $\left\\{p,q,s\right\\}$ not appearing in
$\left\\{i,j,k\right\\}$, say $p\notin\left\\{i,j,k\right\\}$. One of $i$ or
$p$ cannot equal to $t$, say $i\neq t$. Thus the equality cannot occur since
$c_{i}$ is the only term in the equation involving $a_{i}$, a contradiction.

$c_{i}$ | $c_{j}$ | $c_{k}$
---|---|---
$a_{i}$ | $b_{j}$ | $a_{k}$
$b_{i}$ | $b_{j}$ | $b_{k}$
$b_{i}$ | $a_{j}$ | $a_{k}$
$a_{i}$ | $a_{j}$ | $b_{k}$
(a) $K_{4}\left(a_{i},b_{i},a_{j},b_{j},a_{k},b_{k}\right)$

$d_{i}$ | $d_{j}$ | $d_{k}$
---|---|---
$a_{i}$ | $b_{j}$ | $b_{k}$
$b_{i}$ | $b_{j}$ | $a_{k}$
$b_{i}$ | $a_{j}$ | $b_{k}$
$a_{i}$ | $a_{j}$ | $a_{k}$
(b) $K_{4}\left(a_{i},b_{i},a_{j},b_{j},b_{k},a_{k}\right)$

Table 2: The possible values of $c_{i},c_{j},c_{k}$ and $d_{i},d_{j},d_{k}$.

Case 3.2. $\left\\{i,j,k\right\\}=\left\\{p,q,s\right\\}$.

Without loss of generality, let $i=p$, $j=q$ and $k=s$. Since $x$, $y$ are in
different $K_{4}$’s, we can assume without loss of generality that $x\in
K_{4}\left(a_{i},b_{i},a_{j},b_{j},a_{k},b_{k}\right)$ and $y\in
K_{4}\left(a_{i},b_{i},a_{j},b_{j},b_{k},a_{k}\right)$. By considering the
edge rank sum of each triangle in
$K_{4}\left(a_{i},b_{i},a_{j},b_{j},a_{k},b_{k}\right)$, each row in Table
2(a) shows the possible values of $c_{i},c_{j},c_{k}$, and by considering the
edge rank sum of each triangle in
$K_{4}\left(a_{i},b_{i},a_{j},b_{j},b_{k},a_{k}\right)$, each row in Table
2(b) shows the possible values of $d_{i},d_{j},d_{k}$.

By comparing a row in Table 2(a) with a row in Table 2(b), we observe that
either none or two of $c_{i}=d_{i},c_{j}=d_{j},c_{k}=d_{k}$ hold. If none
holds, then
$\left\\{c_{i},d_{i}\right\\}=\left\\{a_{i},b_{i}\right\\},\left\\{c_{j},d_{j}\right\\}=\left\\{a_{j},b_{j}\right\\}$
and $\left\\{c_{k},d_{k}\right\\}=\left\\{a_{k},b_{k}\right\\}$. Thus the
above equation becomes

$N+N-N=2e_{t}$

which is a contradiction. If two of $c_{i}=d_{i},c_{j}=d_{j},c_{k}=d_{k}$
hold, then we assume without loss of generality that
$\left\\{c_{i},d_{i}\right\\}=\left\\{a_{i},b_{i}\right\\}$ and $c_{j}=d_{j}$,
$c_{k}=d_{k}$. Thus the original equation becomes

$N+2c_{j}-2c_{k}=2e_{t}.$

Since $j\neq k$, one of $j$ or $k$ cannot equal to $t$, say $j\neq t$. Hence,
the equality cannot occur since $c_{j}$ is the only term in the equation
involving $a_{j}$, a contradiction.

Case 4. $x\in\text{type I}\ K_{4}$ and $y\in\text{type III}\ K_{4}$.

Then $x\in K_{4}\left(c_{i}\right)$ where $i\in[M]$ and
$c_{i}\in\left\\{a_{i},b_{i}\right\\}$, and $y\in
K_{4}\left(\frac{N}{2}\right)$. Thus $r^{\prime}_{x}=\frac{c_{i}}{2}$ and
$r^{\prime}_{y}=\frac{N}{4}$. The equation
$r^{\prime}_{x}+r^{\prime}_{y}=e_{t}$ becomes

$\displaystyle c_{i}-2e_{t}+\frac{N}{2}$ $\displaystyle=0$

By Lemma 15, the sum of the coefficients of $c_{i}$ and $e_{t}$ must be even,
a contradiction.

Case 5. $x\in\text{type I}\ K_{4}$ and $y\in\text{type IV}\ K_{4}$.

Then $x\in K_{4}\left(c_{i}\right)$ where $i\in[M]$ and
$c_{i}\in\left\\{a_{i},b_{i}\right\\}$, and $y\in
K_{4}\left(a_{p},b_{p},a_{q},b_{q},\frac{N}{2},\frac{N}{2}\right)$ where
$p,q\in[M]$ are distinct. Thus $r^{\prime}_{x}=\frac{c_{i}}{2}$ and
$r^{\prime}_{y}=\frac{d_{p}+d_{q}-N/2}{2}$ where
$d_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{p,s\right\\}$. The equation
$r^{\prime}_{x}+r^{\prime}_{y}=e_{t}$ becomes

$\displaystyle c_{i}+d_{p}+d_{q}-2e_{t}-\frac{N}{2}=0$

By Lemma 15, the sum of the coefficients of $c_{i}$, $d_{p}$, $d_{q}$ and
$e_{t}$ must be even, a contradiction.

Case 6. $x\in\text{type II}\ K_{4}$ and $y\in\text{type III}\ K_{4}$.

Then $x$ is in either $K_{4}\left(a_{i},b_{i},a_{j},b_{j},a_{k},b_{k}\right)$
or $K_{4}\left(a_{i},b_{i},a_{j},b_{j},b_{k},a_{k}\right)$ where $i,j,k\in[M]$
are all distinct, and $y\in K_{4}\left(\frac{N}{2}\right)$. Thus
$r^{\prime}_{x}=\frac{c_{i}+c_{j}-c_{k}}{2}$ where
$c_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{i,j,k\right\\}$, and $r^{\prime}_{y}=\frac{N}{4}$. The
equation $r^{\prime}_{x}+r^{\prime}_{y}=e_{t}$ becomes

$\displaystyle c_{i}+c_{j}-c_{k}+\frac{N}{2}-2e_{t}=0$

By Lemma 15, the sum of the coefficients of $c_{i}$, $c_{j}$, $c_{k}$ and
$e_{t}$ must be even, a contradiction.

Case 7. $x\in\text{type II}\ K_{4}$ and $y\in\text{type IV}\ K_{4}$.

Then $x$ is in either $K_{4}\left(a_{i},b_{i},a_{j},b_{j},a_{k},b_{k}\right)$
or $K_{4}\left(a_{i},b_{i},a_{j},b_{j},b_{k},a_{k}\right)$ where $i,j,k\in[M]$
are all distinct, and $y\in
K_{4}\left(a_{p},b_{p},a_{q},b_{q},\frac{N}{2},\frac{N}{2}\right)$ where
$p,q\in[M]$ are distinct. Thus $r^{\prime}_{x}=\frac{c_{i}+c_{j}-c_{k}}{2}$
where $c_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{i,j,k\right\\}$, and
$r^{\prime}_{y}=\frac{d_{p}+d_{q}-N/2}{2}$ where
$d_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{p,q\right\\}$. The equation
$r^{\prime}_{x}+r^{\prime}_{y}=e_{t}$ becomes

$\displaystyle c_{i}+c_{j}-c_{k}+d_{p}+d_{q}-2e_{t}-\frac{N}{2}=0$

By Lemma 15, the sum of the coefficients of $c_{i}$, $c_{j}$, $c_{k}$,
$d_{p}$, $d_{q}$ and $e_{t}$ must be even, a contradiction.

Case 8. $x,y\in\text{type III}\ K_{4}$.

This case cannot occur since $x$ and $y$ are in different $K_{4}$’s, but there
is only one $K_{4}\left(\frac{N}{2}\right)$.

Case 9. $x\in\text{type III}\ K_{4}$ and $y\in\text{type IV}\ K_{4}$.

Then $x\in K_{4}\left(\frac{N}{2}\right)$ and $y\in
K_{4}\left(a_{i},b_{i},a_{j},b_{j},\frac{N}{2},\frac{N}{2}\right)$ where
$i,j\in[M]$ are distinct. Thus $r^{\prime}_{x}=\frac{N}{4}$ and
$r^{\prime}_{y}=\frac{c_{i}+c_{j}-N/2}{2}$ where
$c_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{i,j\right\\}$. The equation
$r^{\prime}_{x}+r^{\prime}_{y}=e_{t}$ becomes

$\displaystyle c_{i}+c_{j}=2e_{t}.$

We obtain a contradiction similar to Case 1.

Case 10. $x,y\in\text{type IV}\ K_{4}$.

Then $x\in K_{4}\left(a_{i},b_{i},a_{j},b_{j},\frac{N}{2},\frac{N}{2}\right)$
where $i,j\in[M]$ are distinct, and $y\in
K_{4}\left(a_{p},b_{p},a_{q},b_{q},\frac{N}{2},\frac{N}{2}\right)$ where
$p,q\in[M]$ are distinct. Thus $r^{\prime}_{x}=\frac{c_{i}+c_{j}-N/2}{2}$
where $c_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{i,j\right\\}$, and $r^{\prime}_{y}=\frac{d_{p}+d_{q}-N/2}{2}$
where $d_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{p,q\right\\}$. The equation
$r^{\prime}_{x}+r^{\prime}_{y}=e_{t}$ becomes

$\displaystyle c_{i}+c_{j}+d_{p}+d_{q}-N=2e_{t}.$

Since $x$ and $y$ are in different $K_{4}$’s, we have
$\left\\{i,j\right\\}\neq\left\\{p,q\right\\}$. Thus there is an index in one
set not appearing in the other set, say $i\notin\left\\{p,q\right\\}$ and
$p\notin\left\\{i,j\right\\}$. One of $i$ or $p$ cannot equal to $t$, say
$i\neq t$. Therefore, the equality cannot occur since $c_{i}$ is the only term
in the equation involving $a_{i}$, a contradiction. ∎

Let $\varepsilon$ be a positive real number smaller than any distance between
two distinct rank sums in the $\left(A,B,0\right)$-assignment of $nK_{4}$.
Note that the set of edge rank sums in the $\left(A,B,0\right)$-assignment of
$nK_{4}$ is $A\cup B\cup\left\\{\frac{N}{2}\right\\}$. By the definition of
$\varepsilon$, the sets of the form $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ and
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all $i\in[M]$ are pairwise
disjoint. Let $r$ be the $\left(A,B,\varepsilon\right)$-assignment of
$nK_{4}$. Then, for any vertex $u\in nK_{4}$,

$r_{u}=\left\\{\begin{array}[]{l}r^{\prime}_{u}\hskip
24.18501pt\emph{if}\hskip 5.69046ptu\ \text{is in a type I or II}\ K_{4},\\\
r^{\prime}_{u}+\frac{\varepsilon}{2}\hskip 5.69046pt\emph{if}\hskip
5.69046ptu\ \text{is in a type III or IV}\ K_{4}.\end{array}\right.$

Let $xy$ be a nonedge in $nK_{4}$ and consider $a_{i}\in A$. Observe that

$r_{x}+r_{y}\in\left\\{r^{\prime}_{x}+r^{\prime}_{y},r^{\prime}_{x}+r^{\prime}_{y}+\frac{\varepsilon}{2},r^{\prime}_{x}+r^{\prime}_{y}+\varepsilon\right\\}.$

By Claim, $r^{\prime}_{x}+r^{\prime}_{y}\neq a_{i}$. Since $a_{i}$ is a rank
sum in the $\left(A,B,0\right)$-assignment, the distance between
$r^{\prime}_{x}+r^{\prime}_{y}$ and $a_{i}$ exceeds $\varepsilon$ by the
definition of $\varepsilon$. If $r^{\prime}_{x}+r^{\prime}_{y}>a_{i}$, then
$a_{i}+\varepsilon<r^{\prime}_{x}+r^{\prime}_{y}\leq r_{x}+r_{y}$. If
$r^{\prime}_{x}+r^{\prime}_{y}<a_{i}$, then $r_{x}+r_{y}\leq
r^{\prime}_{x}+r^{\prime}_{y}+\varepsilon<a_{i}$. Thus
$r_{x}+r_{y}\notin\left[a_{i},a_{i}+\varepsilon\right]$. Similarly,
$r_{x}+r_{y}\notin\left[b_{i},b_{i}+\varepsilon\right]$.

It remains to show that $r_{x}+r_{y}\neq\frac{N}{2}+\varepsilon$. Note that
$\frac{N}{2}$ is a rank sum in the $\left(A,B,0\right)$-assignment. Thus the
distance between $r^{\prime}_{x}+r^{\prime}_{y}$ and $\frac{N}{2}$ is either
$0$ or more than $\varepsilon$ by the definition of $\varepsilon$. If $x$ or
$y$ is in a type I or II $K_{4}$, then
$r_{x}+r_{y}\in\left\\{r^{\prime}_{x}+r^{\prime}_{y},r^{\prime}_{x}+r^{\prime}_{y}+\frac{\varepsilon}{2}\right\\}$.
If $r_{x}+r_{y}=\frac{N}{2}+\varepsilon$, then the distance between
$r^{\prime}_{x}+r^{\prime}_{y}$ and $\frac{N}{2}$ is either $\varepsilon$ or
$\frac{\varepsilon}{2}$, a contradiction. Thus we may suppose that both $x$
and $y$ are in a a type III or IV $K_{4}$. Since there is only one $K_{4}$ of
type III, we may suppose further that $x$ is in a type IV $K_{4}$. Then $x\in
K_{4}\left(a_{i}+\varepsilon,b_{i}+\varepsilon,a_{j}+\varepsilon,b_{j}+\varepsilon,\frac{N}{2}+\varepsilon,\frac{N}{2}+\varepsilon\right)$
for some distinct $i,j\in[M]$. Thus
$r_{x}=\frac{c_{i}+c_{j}-N/2+\varepsilon}{2}$ where
$c_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{i,j\right\\}$.

If $y$ is in a type III $K_{4}$, then $y\in
K_{4}\left(\frac{N}{2}+\varepsilon\right)$. Thus
$r_{y}=\frac{N}{4}+\frac{\varepsilon}{2}$. Hence,

$r_{x}+r_{y}=\left(\frac{c_{i}+c_{j}-N/2+\varepsilon}{2}\right)+\left(\frac{N}{4}+\frac{\varepsilon}{2}\right)=\frac{c_{i}+c_{j}}{2}+\varepsilon.$

Suppose to the contrary that $r_{x}+r_{y}=\frac{N}{2}+\varepsilon$, that is
$c_{i}+c_{j}=N$. Since $i\neq j$, we have $c_{i}$ is the only term in the
equation involving $a_{i}$. Thus the equality cannot occur, a contradiction.

If $y$ is in a type IV $K_{4}$, then $y\in
K_{4}\left(a_{p}+\varepsilon,b_{p}+\varepsilon,a_{q}+\varepsilon,b_{q}+\varepsilon,\frac{N}{2}+\varepsilon,\frac{N}{2}+\varepsilon\right)$
for some distinct $p,q\in[M]$. Thus
$r_{y}=\frac{d_{p}+d_{q}-N/2+\varepsilon}{2}$ where
$d_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{p,q\right\\}$. Suppose to the contrary that
$r_{x}+r_{y}=\frac{N}{2}+\varepsilon$, i.e.

$c_{i}+c_{j}+d_{p}+d_{q}-2N=0.$

Since $x$ and $y$ are in different $K_{4}$’s, we have
$\left\\{i,j\right\\}\neq\left\\{p,q\right\\}$. Thus there exists an index in
one set not appearing in the other set, say $i\notin\left\\{p,q\right\\}$.
Recall that $i\neq j$. Hence, the equality cannot occur since $c_{i}$ is the
only term in the equation involving $a_{i}$, a contradiction. ∎

Now, we are ready to prove Theorem 6. Its proof follows the same line of
argument as in the proof of Theorem 5, nevertheless, that of Theorem 6 is
significantly more complicated.

###### Proof of Theorem 6$(i)$.

Let $m$ be such that $t_{m-1}\leq n<t_{m}$. Suppose to the contrary that
$\Theta(nK_{4})\leq 2m-2$. By Lemma 13$(i)$,

$\begin{split}n&\leq\left\lceil{\frac{\Theta(nK_{4})}{2}}\right\rceil+\binom{\left\lfloor\frac{\Theta(nK_{4})+1}{4}\right\rfloor}{3}+\binom{\left\lceil\frac{\Theta(nK_{4})}{4}\right\rceil}{3}\\\
&\leq\left\lceil{\frac{2m-2}{2}}\right\rceil+\binom{\left\lfloor\frac{2m-2+1}{4}\right\rfloor}{3}+\binom{\left\lceil\frac{2m-2}{4}\right\rceil}{3}\\\
&=(m-1)+\binom{\left\lfloor\frac{m-1}{2}\right\rfloor}{3}+\binom{\left\lceil\frac{m-1}{2}\right\rceil}{3}\\\
&=t_{m-1}-1\end{split}$

contradicting the definition of $m$. Hence, $\Theta(nK_{4})\geq 2m-1$.

To prove that $\Theta(nK_{4})\leq 2m$, let
$\left\\{N,a_{1},a_{2},\dots,a_{\left\lfloor{m/2}\right\rfloor}\right\\}\subset\mathbb{R^{+}}$
be a linearly independent set over $\mathbb{Q}$ such that $a_{i}<N$ for all
$i\in\left\\{1,2,\dots,\left\lfloor{\frac{m}{2}}\right\rfloor\right\\}$ and
let $b_{i}=N-a_{i}$ for $i=1,2,\dots,\left\lfloor{\frac{m}{2}}\right\rfloor$.
Write
$A=\left\\{a_{1},a_{2},\dots,a_{\left\lfloor{m/2}\right\rfloor}\right\\}$ and
$B=\left\\{b_{1},b_{2},\dots,b_{\left\lfloor{m/2}\right\rfloor}\right\\}$.

Case 1. $m$ is even.

Let $n^{\prime}=t_{m}-1=m+2\binom{m/2}{3}$. It is sufficient to show that
$\Theta(n^{\prime}K_{4})\leq 2m$ since
$\Theta(nK_{4})\leq\Theta(n^{\prime}K_{4})$ as $nK_{4}$ is an induced subgraph
of $n^{\prime}K_{4}$. Consider the $\left(A,B\right)$-assignment of
$n^{\prime}K_{4}$. By Lemma 16$(i)$, the edge and nonedge rank sums do not
coincide. Note that the set of edge rank sums of $n^{\prime}K_{4}$ is $A\cup
B$. Let $A\cup B=\left\\{c_{1},c_{2},\dots,c_{m}\right\\}$. We separate the
edge and nonedge rank sums by putting two thresholds around each edge rank
sum. For $i=1,2,\dots,m$, let $\theta_{2i-1}=c_{i}$ and
$\theta_{2i}=c_{i}+\varepsilon^{\prime}$ be thresholds of $n^{\prime}K_{4}$
where $\varepsilon^{\prime}$ is a sufficiently small positive real number, for
example, take $\varepsilon^{\prime}$ smaller than any distance between two
distinct rank sums of $n^{\prime}K_{4}$. Thus the above rank assignment is a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m}\right)$-representation of
$n^{\prime}K_{4}$, and hence $n^{\prime}K_{4}$ is a $2m$-threshold graph, that
is $\Theta(n^{\prime}K_{4})\leq 2m$.

Case 2. $m$ is odd.

Let
$n^{\prime}=t_{m}-1=m+\binom{\left\lfloor{m/2}\right\rfloor}{3}+\binom{\left\lceil{m/2}\right\rceil}{3}$.
It is sufficient to show that $\Theta(n^{\prime}K_{4})\leq 2m$ since $nK_{4}$
is an induced subgraph of $n^{\prime}K_{4}$. By Lemma 16$(ii)$, there is a
positive real number $\varepsilon$ such that, in the
$\left(A,B,\varepsilon\right)$-assignment of $n^{\prime}K_{4}$, no nonedge
rank sum lies in either $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ or
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all
$i\in\left\\{1,2,\dots,\left\lfloor{\frac{m}{2}}\right\rfloor\right\\}$, and
moreover, the sets of the form $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ and
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all
$i\in\left\\{1,2,\dots,\left\lfloor{\frac{m}{2}}\right\rfloor\right\\}$ are
pairwise disjoint. Let $A\cup
B\cup\left\\{\frac{N}{2}+\varepsilon\right\\}=\left\\{c_{1},c_{2},\dots,c_{m}\right\\}$.
We separate the edge and nonedge rank sums by putting two thresholds around
each interval of edge rank sums of the form
$\left[c_{i},c_{i}+\varepsilon\right]$ and
$\left\\{\frac{N}{2}+\varepsilon\right\\}$. For $i=1,2,\dots,m$, let
$\theta_{2i-1}=c_{i}$ and

$\theta_{2i}=\left\\{\begin{array}[]{l}c_{i}+\varepsilon+\varepsilon^{\prime}\hskip
5.69046pt\text{if}\hskip 5.69046ptc_{i}\in A\cup B,\vspace{.25cm}\\\
c_{i}+\varepsilon^{\prime}\hskip 22.76228pt\text{if}\hskip
5.69046ptc_{i}=\frac{N}{2}+\varepsilon\end{array}\right.$

be thresholds of $n^{\prime}K_{4}$ where $\varepsilon^{\prime}$ is a
sufficiently small positive real number. Thus the above rank assignment is a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m}\right)$-representation of
$n^{\prime}K_{4}$, and hence $n^{\prime}K_{4}$ is a $2m$-threshold graph, that
is $\Theta(n^{\prime}K_{4})\leq 2m$.

Suppose that $n=t_{m-1}$. To prove that $\Theta(nK_{4})\leq 2m-1$, we write
$M=\left\lfloor{\frac{m+1}{2}}\right\rfloor$ and let
$\left\\{N,a_{1},a_{2},\dots,a_{M}\right\\}\subset\mathbb{R^{+}}$ be a
linearly independent set over $\mathbb{Q}$ such that
$a_{i}<N\leq\frac{a_{M}}{2}$ for all $i\in[M-1]$. Let $b_{i}=N-a_{i}$ for
$i=1,2,\dots,M-1$. Write $A=\left\\{a_{1},a_{2},\dots,a_{M-1}\right\\}$ and
$B=\left\\{b_{1},b_{2},\dots,b_{M-1}\right\\}$.

Case 1. $m-1$ is even.

We take the $\left(A,B\right)$-assignment for the first
$(m-1)+2\binom{(m-1)/2}{3}$ $K_{4}$’s in $nK_{4}$, and let every edge in the
last $K_{4}$ have edge rank sum $a_{M}$. Note that these $K_{4}$’s appear in
the
$\left(A\cup\left\\{a_{M}\right\\},B\cup\left\\{b_{M}\right\\}\right)$-assignment
of $\left(t_{m+1}-1\right)K_{4}$. By Lemma 16$(i)$, the edge and nonedge rank
sums do not coincide. Observe that the set of edge rank sums of $nK_{4}$ is
$A\cup B\cup\left\\{a_{M}\right\\}$. Let $A\cup
B\cup\left\\{a_{M}\right\\}=\left\\{c_{1},c_{2},\dots,c_{m}\right\\}$ where
$c_{1}<c_{2}<\dots<c_{m}$. We separate the edge and nonedge rank sums by
putting two thresholds around each edge rank sum. For $i=1,2,\dots,m$, let
$\theta_{2i-1}=c_{i}$ and $\theta_{2i}=c_{i}+\varepsilon^{\prime}$ be
thresholds of $nK_{4}$ where $\varepsilon^{\prime}$ is a sufficiently small
positive real number. Thus the above rank assignment is a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m}\right)$-representation of
$nK_{4}$. In fact, we will show that we do not need the last threshold
$\theta_{2m}$ by proving that no rank sum exceeds $\theta_{2m-1}$. It is
sufficient to show that the rank of each vertex is at most
$\frac{\theta_{2m-1}}{2}=\frac{c_{m}}{2}=\frac{a_{M}}{2}$. This is clear for
the last $K_{4}$ with the set of edge rank sums $\left\\{a_{M}\right\\}$. For
the other $K_{4}$’s, the rank of each vertex is of the form
$\frac{c_{i}+c_{j}-c_{k}}{2}$ for some $i,j,k\in[m-1]$, which is at most
$\frac{a_{M}}{2}$ since $c_{i},c_{j}\leq\frac{a_{M}}{2}$ and $c_{k}>0$. Thus
the above rank assignment is a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m-1}\right)$-representation of
$nK_{4}$, and hence $nK_{4}$ is a $(2m-1)$-threshold graph, that is
$\Theta(nK_{4})\leq 2m-1$.

Case 2. $m-1$ is odd.

We choose $\varepsilon$ such that the
$\left(A\cup\left\\{a_{M}\right\\},B\cup\left\\{b_{M}\right\\},\varepsilon\right)$-assignment
of $\left(t_{m+1}-1\right)K_{4}$ satisfies the properties in Lemma 16$(ii)$.
We then take the $\left(A,B,\varepsilon\right)$-assignment for the first
$(m-1)+\binom{\left\lfloor(m-1)/2\right\rfloor}{3}+\binom{\left\lceil(m-1)/2\right\rceil}{3}$
$K_{4}$’s in $nK_{4}$, and let every edge in the last $K_{4}$ have edge rank
sum $a_{M}$. Note that these $K_{4}$’s appear in the
$\left(A\cup\left\\{a_{M}\right\\},B\cup\left\\{b_{M}\right\\},\varepsilon\right)$-assignment
of $\left(t_{m+1}-1\right)K_{4}$. By the choice of $\varepsilon$, no nonedge
rank sum lies in either $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ or
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all $i\in[M-1]$, and moreover,
the sets of the form $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ and
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all $i\in[M-1]$ are pairwise
disjoint. Let $A\cup
B\cup\left\\{a_{M},\frac{N}{2}+\varepsilon\right\\}=\left\\{c_{1},c_{2},\dots,c_{m}\right\\}$
where $c_{1}<c_{2}<\dots<c_{m}$. We claim that $c_{m}=a_{M}$. Indeed, it is
clear that $a_{M}>a_{i},b_{i}$ for all $i\in[M-1]$. Since
$\frac{N}{2}+\varepsilon$ lies between the intervals
$\left[a_{1},a_{1}+\varepsilon\right]$ and
$\left[b_{1},b_{1}+\varepsilon\right]$ by the choice of $\varepsilon$, we have
$\frac{N}{2}+\varepsilon<\max\left\\{a_{1},b_{1}\right\\}<a_{M}$. We separate
the edge and nonedge rank sums by putting two thresholds around each interval
of edge rank sums. For $i=1,2,\dots,m$, let $\theta_{2i-1}=c_{i}$ and

$\theta_{2i}=\left\\{\begin{array}[]{l}c_{i}+\varepsilon+\varepsilon^{\prime}\hskip
5.69046pt\text{if}\hskip 5.69046ptc_{i}\in A\cup
B\cup\left\\{a_{M}\right\\},\vspace{.25cm}\\\ c_{i}+\varepsilon^{\prime}\hskip
22.76228pt\text{if}\hskip
5.69046ptc_{i}=\frac{N}{2}+\varepsilon\end{array}\right.$

be thresholds of $nK_{4}$ where $\varepsilon^{\prime}$ is a sufficiently small
positive real number. Thus the above rank assignment is a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m}\right)$-representation of
$nK_{4}$. In fact, we will show that we do not need the last threshold
$\theta_{2m}$ by proving that no rank sum is greater than or equal to
$\theta_{2m}=a_{M}+\varepsilon+\varepsilon^{\prime}$. It is sufficient to show
that the rank of each vertex is at most $\frac{a_{M}+\varepsilon}{2}$. This is
clear for the last $K_{4}$ with the set of edge rank sums
$\left\\{a_{M}\right\\}$. For the other $K_{4}$’s, the rank of each vertex is
of the form $\frac{d_{i}+d_{j}-d_{k}}{2},\frac{N}{4}+\frac{\varepsilon}{2}$ or
$\frac{d_{i}+d_{j}-N/2+\varepsilon}{2}$ where $i,j,k\in[M-1]$ and
$d_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{i,j,k\right\\}$, which is at most
$\frac{a_{M}+\varepsilon}{2}$ since
$0<d_{i},d_{j},d_{k},\frac{N}{2}\leq\frac{a_{M}}{2}$. Thus the above rank
assignment is a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m-1}\right)$-representation of
$nK_{4}$, and hence $nK_{4}$ is a $(2m-1)$-threshold graph, that is
$\Theta(nK_{4})\leq 2m-1$.

Suppose that $n>t_{m-1}$. To prove that $\Theta(nK_{4})\geq 2m$, we suppose
that $\Theta(nK_{4})\leq 2m-1$. Let $r$ be a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m-1}\right)$-representation of
$nK_{4}$. Then there are at most $m$ colors of edges in $nK_{4}$. By Lemma
13$(i)$, there are at most $t_{m-1}-1$ $K_{4}$’s without color $m$. By Lemma
14$(i)$, an edge of color $m$ appears in at most one $K_{4}$. Thus
$n\leq\left(t_{m-1}-1\right)+1$, a contradiction. Therefore,
$\Theta(nK_{4})\geq 2m$. ∎

###### Proof of Theorem 6$(ii)$.

Let $m$ be such that $s_{m-1}\leq n<s_{m}$. By Theorem 6$(i)$,
$\Theta(nK_{4})\in\left\\{2m,2m+1\right\\}$, and hence $\Theta(K_{n\times
4})\in\left\\{2m,2m+1\right\\}$ by Proposition 1.

Suppose that $n=s_{m-1}$. To prove that $\Theta(K_{n\times 4})\leq 2m$, we
write $M=\left\lfloor{\frac{m+1}{2}}\right\rfloor$ and let
$\left\\{N,a_{1},a_{2},\dots,a_{M}\right\\}\subset\mathbb{R}$ be a linearly
independent set over $\mathbb{Q}$ such that $\frac{a_{M}}{3}\leq-N<-a_{i}<0$
for all $i\in[M-1]$. Let $b_{i}=N-a_{i}$ for $i=1,2,\dots,M$. Then
$\frac{a_{M}}{3}\leq a_{i},b_{i},-N,N\leq\frac{b_{M}}{3}$ for all $i\in[M-1]$.
Write $A=\left\\{a_{1},a_{2},\dots,a_{M-1}\right\\}$ and
$B=\left\\{b_{1},b_{2},\dots,b_{M-1}\right\\}$.

Case 1. $m-1$ is even.

We take the $\left(A,B\right)$-assignment for the first
$(m-1)+2\binom{(m-1)/2}{3}$ parts in $K_{n\times 4}$, and let the last two
parts have the sets of nonedge rank sums $\left\\{a_{M}\right\\}$ and
$\left\\{b_{M}\right\\}$. Note that these parts appear in the
$\left(A\cup\left\\{a_{M}\right\\},B\cup\left\\{b_{M}\right\\}\right)$-assignment
of $K_{(s_{m+1}-2)\times 4}$. By Lemma 16$(iii)$, the edge and nonedge rank
sums do not coincide. Observe that the set of nonedge rank sums of $K_{n\times
4}$ is $A\cup B\cup\left\\{a_{M},b_{M}\right\\}$. Let $A\cup
B\cup\left\\{a_{M},b_{M}\right\\}=\left\\{c_{1},c_{2},\dots,c_{m+1}\right\\}$
where $c_{1}<c_{2}<\dots<c_{m+1}$. Let $\theta_{1}$ be smaller than all rank
sums. We then separate the edge and nonedge rank sums by putting two
thresholds around each nonedge rank sum. For $i=1,2,\dots,m+1$, let
$\theta_{2i}=c_{i}$ and $\theta_{2i+1}=c_{i}+\varepsilon^{\prime}$ where
$\varepsilon^{\prime}$ is a sufficiently small positive real number. Thus the
above rank assignment is a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m+3}\right)$-representation of
$K_{n\times 4}$. In fact, we will show that we do not need the thresholds
$\theta_{1},\theta_{2}$ and $\theta_{2m+3}$ by proving that no rank sum is
smaller than $\theta_{2}$ or larger than $\theta_{2m+2}$. It is sufficient to
show that the rank of each vertex is at least
$\frac{\theta_{2}}{2}=\frac{c_{1}}{2}=\frac{a_{M}}{2}$ and at most
$\frac{\theta_{2m+2}}{2}=\frac{c_{m+1}}{2}=\frac{b_{M}}{2}$. This is clear for
the last two parts with the sets of nonedge rank sums $\left\\{a_{M}\right\\}$
and $\left\\{b_{M}\right\\}$. For the other parts, the rank of each vertex is
of the form $\frac{c_{i}+c_{j}-c_{k}}{2}$ for some
$i,j,k\in[m]\setminus\left\\{1\right\\}$, which is at least $\frac{a_{M}}{2}$
and at most $\frac{b_{M}}{2}$ since $\frac{a_{M}}{3}\leq
c_{i},c_{j},-c_{k}\leq\frac{b_{M}}{3}$. Thus the above rank assignment is a
$\left(\theta_{3},\theta_{4},\dots,\theta_{2m+2}\right)$-representation of
$K_{n\times 4}$, and hence $K_{n\times 4}$ is a $2m$-threshold graph, that is
$\Theta(K_{n\times 4})\leq 2m$.

Case 2. $m-1$ is odd.

We choose $\varepsilon$ such that the
$\left(A\cup\left\\{a_{M}\right\\},B\cup\left\\{b_{M}\right\\},\varepsilon\right)$-assignment
of $K_{(s_{m+1}-2)\times 4}$ satisfies the properties in Lemma 16$(iv)$. We
then take the $\left(A,B,\varepsilon\right)$-assignment for the first
$(m-1)+\binom{\left\lfloor(m-1)/2\right\rfloor}{3}+\binom{\left\lceil(m-1)/2\right\rceil}{3}$
parts in $K_{n\times 4}$, and let the last two parts have the sets of nonedge
rank sums $\left\\{a_{M}\right\\}$ and $\left\\{b_{M}\right\\}$. Note that
these parts appear in the
$\left(A\cup\left\\{a_{M}\right\\},B\cup\left\\{b_{M}\right\\},\varepsilon\right)$-assignment
of $K_{(s_{m+1}-2)\times 4}$. By the choice of $\varepsilon$, no edge rank sum
lies in either $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ or
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all $i\in[M-1]$, and moreover,
the sets of the form $\left[a_{i},a_{i}+\varepsilon\right]$,
$\left[b_{i},b_{i}+\varepsilon\right]$ and
$\left\\{\frac{N}{2}+\varepsilon\right\\}$ for all $i\in[M-1]$ are pairwise
disjoint. Let $A\cup
B\cup\left\\{a_{M},b_{M},\frac{N}{2}+\varepsilon\right\\}=\left\\{c_{1},c_{2},\dots,c_{m+1}\right\\}$
where $c_{1}<c_{2}<\dots<c_{m+1}$. We claim that $c_{1}=a_{M}$ and
$c_{m+1}=b_{M}$. Indeed, it is clear that $a_{M}<a_{i},b_{i}<b_{M}$ for all
$i\in[M-1]$. Since $\frac{N}{2}+\varepsilon$ lies between the intervals
$\left[a_{1},a_{1}+\varepsilon\right]$ and
$\left[b_{1},b_{1}+\varepsilon\right]$ by the choice of $\varepsilon$, we have
$a_{M}<\min\left\\{a_{1},b_{1}\right\\}<\frac{N}{2}+\varepsilon<\max\left\\{a_{1},b_{1}\right\\}<b_{M}$.
Let $\theta_{1}$ be smaller than all rank sums. We then separate the edge and
nonedge rank sums by putting two thresholds around each interval of nonedge
rank sums. For $i=1,2,\dots,m+1$, let $\theta_{2i}=c_{i}$ and

$\theta_{2i+1}=\left\\{\begin{array}[]{l}c_{i}+\varepsilon+\varepsilon^{\prime}\hskip
5.69046pt\text{if}\hskip 5.69046ptc_{i}\in A\cup
B\cup\left\\{a_{M},b_{M}\right\\},\vspace{.25cm}\\\
c_{i}+\varepsilon^{\prime}\hskip 22.76228pt\text{if}\hskip
5.69046ptc_{i}=\frac{N}{2}+\varepsilon\end{array}\right.$

be thresholds of $K_{n\times 4}$ where $\varepsilon^{\prime}$ is a
sufficiently small positive real number. Thus the above rank assignment is a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m+3}\right)$-representation of
$K_{n\times 4}$. In fact, we will show that we do not need the thresholds
$\theta_{1},\theta_{2}$ and $\theta_{2m+3}$ by proving that no rank sum is
smaller than $\theta_{2}$, or larger than or equal to $\theta_{2m+3}$. It is
sufficient to show that the rank of each vertex is at least
$\frac{\theta_{2}}{2}=\frac{c_{1}}{2}=\frac{a_{M}}{2}$ and at most
$\frac{\theta_{2m+3}-\varepsilon^{\prime}}{2}=\frac{c_{m+1}+\varepsilon}{2}=\frac{b_{M}+\varepsilon}{2}$.
This is clear for the last two parts with the sets of nonedge rank sums
$\left\\{a_{M}\right\\}$ and $\left\\{b_{M}\right\\}$. For the other parts,
the rank of each vertex is of the form
$\frac{d_{i}+d_{j}-d_{k}}{2},\frac{N}{4}+\frac{\varepsilon}{2}$ or
$\frac{d_{i}+d_{j}-N/2+\varepsilon}{2}$ where $i,j,k\in[M-1]$ are all distinct
and $d_{\ell}\in\left\\{a_{\ell},b_{\ell}\right\\}$ for
$\ell\in\left\\{i,j,k\right\\}$, which is at least $\frac{a_{M}}{2}$ and at
most $\frac{b_{M}+\varepsilon}{2}$ since $\frac{a_{M}}{3}\leq
d_{i},d_{j},-d_{k},-N,N\leq\frac{b_{M}}{3}$. Thus the above rank assignment is
a $\left(\theta_{3},\theta_{4},\dots,\theta_{2m+2}\right)$-representation of
$K_{n\times 4}$, and hence, $K_{n\times 4}$ is a $2m$-threshold graph, that is
$\Theta(K_{n\times 4})\leq 2m$.

Suppose that $n>s_{m-1}$. To prove that $\Theta(K_{n\times 4})\geq 2m+1$, we
suppose that $\Theta(K_{n\times 4})\leq 2m$. Let $r$ be a
$\left(\theta_{1},\theta_{2},\dots,\theta_{2m}\right)$-representation of
$K_{n\times 4}$. Then there are at most $m+1$ colors of nonedges in
$K_{n\times 4}$. By Lemma 13$(ii)$, there are at most $s_{m-1}-2$ parts
without colors $1$ and $m+1$. By Lemma 14$(ii)$ and 14$(iii)$, a nonedge of
color $1$ appears in at most one part and a nonedge of color $m+1$ also
appears in at most one part. Therefore, $n\leq(s_{m-1}-2)+1+1$, a
contradiction. ∎

##  4 Concluding Remarks

We find the threshold numbers of $K_{n\times 3}$ and $K_{n\times 4}$, while
Chen and Hao [2] determined that of $K_{m_{1},m_{2},\dots,m_{n}}$ for
$m_{i}>n\geq 2$. Problem 3 remains unsolved for other complete multipartite
graphs. The following could be the next goal.

######  Problem 17.

Determine the exact threshold number of $K_{n\times m}$ for $m\geq 5$.

The method we used can be generalized to give some bounds for
$\Theta(K_{n\times m})$, but new ideas seem to be required in order to find
the exact value.

## References

  * [1] Calamoneri, T., Monti, A., Petreschi, R.: On dynamic threshold graphs and related classes, Theoret. Comput. Sci. 718, 46–57 (2018).
  * [2] Chen, G., Hao, Y.: Multithreshold multipartite graphs, J. Graph Theory. 100, 727–732 (2022).
  * [3] Chvátal, V., Hammer, P. L.: Aggregation of inequalities in integer programming, Ann. Discrete Math. 1, 145–162 (1977).
  * [4] Erdös, P., Goodman, A. W., Posa, L.: The representation of a graph by set intersections, Canad. J. Math. 18, 106–112 (1966).
  * [5] Gavril, F.: The intersection graphs of subtrees of a tree are exactly the chordal graphs, J. Combin. Theory Ser. B. 16, 47–56 (1974).
  * [6] Golumbic, M. C.: Algorithmic graph theory and perfect graphs, Academic Press, New York, NY. 2nd ed., 1980.
  * [7] Golumbic, M. C., Jamison, R. E.: Rank tolerance graph classes, J. Graph Theory. 52, 317–340 (2006).
  * [8] Golumbic, M. C., Monma, C. L.: A generalization of interval graphs with tolerances, Congressus Numer. 35, 321–331 (1982).
  * [9] Hammer, P. L., Mahadev, N. V. R., Peled, U. N.: Some properties of 2-threshold graphs, Networks. 19, 17–23 (1989).
  * [10] Henderson, P.B., Zalcstein, Y.: A graph-theoretic characterization of the pv chunk class of synchronizing primitives, SIAM J. Comput. 6(1), 88–108 (1977).
  * [11] Jacobson, M. S., McMorris, F. R., Scheinerman, E. R.: General results on tolerance intersection graphs, J. Graph Theory. 15, 573–577 (1991).
  * [12] Jamison, R. E., Sprague, A. P.: Multithreshold graphs, J. Graph Theory. 94, 518–530 (2020).
  * [13] Koop, G.J.: Cyclic scheduling of offweekends, Oper. Res. Lett. 4, 259–263 (1986).
  * [14] Mahadev, N. V. R., Peled, U. N.: Threshold graphs and related topics, Ann. Discrete Math. 56 (1995).
  * [15] Ordman, E. T.: Threshold coverings and resource allocation, 16th Southeastern Conference on Combinatorics, Graph Theory and Computing. 99–113 (1986).
  * [16] Orlin, J.: The minimal integral separator of a threshold graph, Ann. Discrete Math. 1, 415–419 (1977).
  * [17] Petreschi, R., Sterbini, A.: Recognizing strict 2-threshold graphs in O(m) time, Inform. Process. Lett. 54, 193–198 (1995).
  * [18] Puleo, G.J.: Some results on multithreshold graphs, Graphs Combin. 36(3), 913–919 (2020).