Complementary Ramsey numbers
Akihiro Munemasa
Masashi Shinohara
In this paper, we propose a new generalization of Ramsey numbers which seems to be untreated in the literature. Instead of requiring the existence of a monochromatic clique, we consider the existence of a clique which avoids one of the colors in an edge coloring. These numbers are called complementary Ramsey numbers, and we derive their basic properties. We also establish their connections to graph factorizations.
1406.2050.tex
% 2014-06-08 by A.M.
% 2014-04-01 by A.M.
% 2014-03-31 by M.S.
% 2013-11-25 by M.S. 3rd line of Table 3 is corrected (form m_2 to m_1)
% 2013-11-24 by A.M.
% 2013-11-14 by M.S. Lemma~\ref{memo} is corrected (1to 8:two parts)
% 2013-11-14 by A.M.
%
\documentclass{amsart}
\usepackage{amsmath,amsfonts}
\DeclareMathOperator{\CURD}{CURD}
\newcommand{\nexteqv}{\displaybreak[0]\\ &\iff}
\newcommand{\nexteq}{\displaybreak[0]\\ &=}
\newcommand{\N}{\mathbb{N}}
\newcommand{\bR}{\bar{R}}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}

\begin{document}

\title{Complementary Ramsey numbers}
\author{Akihiro Munemasa
\and Masashi Shinohara}
\address{Tohoku University, Sendai, 980-8579, Japan}
\email{munemasa@math.is.tohoku.ac.jp}
\address{Shiga University, Shiga, 520-0862, Japan}
\email{shino@edu.shiga-u.ac.jp}
\maketitle

\begin{abstract}
In this paper, we propose a new generalization of Ramsey
numbers which seems to be untreated in the literature.
Instead of requiring the existence of a monochromatic
clique, we consider the existence of a clique which avoids
one of the colors in an edge coloring. These numbers
are called complementary Ramsey numbers, and we derive
their basic properties. We also establish their connections
to graph factorizations.
\end{abstract}
%\keywords{Ramsey number, Ramsey graph, resolvable design, graph factorization}

\section{Introduction}\label{sec:1}
For any given positive integers \(n_1,\ldots,n_c\), 
there is a number, \(\bar{R}(n_1,\ldots,n_c)\), such that if the edges of a 
complete graph of order \(\bar{R}(n_1,\ldots,n_c)\) are colored with 
\(c\) different colors, then for some \(i\) between \(1\) and \(c\), 
there exists a complete subgraph of order \(n_i\) 
all of whose edges have colors different from \(i\).
Note that \(\bar{R}(n_1,n_2)=R(n_2,n_1)\), an ordinary Ramsey number.

Since \(K_4\) admits a 1-factorization, that is, a partition of the edge-set into
matchings, we see
$\bar{R}(3,3,3)\geq5$.
More generally, the existence of $l$ mutually orthogonal Latin squares
of order $n$ implies that $\bar{R}(n+1,n+1,\dots,n+1)$ (repeated $l+2$ times)
is at least $n^2+1$.
In this paper,
we generalize and strengthen these arguments to establish basic properties
of complementary Ramsey numbers. The main tools are the concept of
graph factorizations and resolvable designs.
In particular, we point out that the existence of complete set of mutually
orthogonal Latin squares can be stated in terms of complementary Ramsey numbers.

If we could show $\bar{R}(5,5,5)=12$, then
this would have contributed to the proof of a conjecture of Einhorn--Schoenberg
\cite{Shino}.
Although this was not the case, the approach uses the same idea as
the definition of complementary Ramsey numbers, so we believe it is
worthwhile to formulate it as a formal definition.

This paper is organized as follows. In Sect.~\ref{sec:2},
we give definitions and derive immediate consequences. 
In Sect.~\ref{sec:3}, we derive some inequalities for
complementary Ramsey numbers. 
In Sect.~\ref{sec:4}, we point out connections to
graph factorizations. 
In Sect.~\ref{sec:5}, we list some consequences 
obtained from the connections to graph factorizations.
Finally, in Sect.~\ref{sec:6}, we tabulate complementary Ramsey
numbers with small parameters.

\section{Definitions and notation}\label{sec:2}
For a positive integer $n$, we denote the set $\{1,\dots,n\}$ by $[n]$,
and the set of all $n$-element subsets of a set $X$ by
$\binom{X}{n}$.
For positive integers $k,n$, we denote the set of all edge-coloring
of the complete graph $K_n$ by $k$ colors, by $C(n,k)$:
\[
C(n,k)=\{f\mid f:\binom{[n]}{2}\to[k]\}.
\]
If $G$ is a graph, then we denote by $\alpha(G)$ the independence
number of $G$, and by $\omega(G)$ the clique number of $G$.
We identify a graph whose vertex set is $[n]$, with its set
of edges. In particular, for $f\in C(n,k)$ and $i\in[k]$,
$f^{-1}(i)$ is regarded as the graph $([n],f^{-1}(i))$. 
We use the abbreviations
$\alpha_i(f)=\alpha(f^{-1}(i))$,
$\omega_i(f)=\omega(f^{-1}(i))$.
The Ramsey number can be defined as follows:
\[
R(m_1,\dots,m_k)=\min\{n\in\N\mid
\forall f\in C(n,k),\;\exists i\in[k],\;\omega_i(f)\geq m_i\},
\]
where $m_1,\dots,m_k$ are positive integers.
The finiteness of Ramsey numbers are well known \cite{Ramsey}.
The complementary Ramsey number is defined by replacing $\omega$
by $\alpha$ in the above definition of the Ramsey number:
\[
\bR(m_1,\dots,m_k)=\min\{n\in\N\mid
\forall f\in C(n,k),\;\exists i\in[k],\;\alpha_i(f)\geq m_i\}.
\]
Clearly,
\[
\bR(m_1,\dots,m_k)=\bR(m_{\sigma(1)},\dots,m_{\sigma(k)})
\]
for any permutation $\sigma$ on $[k]$.
The finiteness of the complementary Ramsey number will follow
from Lemmas~\ref{lem:1} and \ref{lem:4} below.

\begin{lemma}\label{lem:1}
For positive integers $m_1,m_2$, we have
$R(m_1,m_2)=\bR(m_2,m_1)$.
\end{lemma}
\begin{proof}
This follows immediately from 
$\alpha_1(f)=\omega_2(f)$, $\alpha_2(f)=\omega_1(f)$
for any $f\in C(n,2)$.
\end{proof}

\begin{lemma}\label{lem:2}
For positive integers $m_1,\dots,m_k$ and $m'_1,\dots,m'_k$
with $m_i\leq m'_i$ for all $i\in[k]$, we have
$\bR(m_1,\dots,m_k)\leq \bR(m'_1,\dots,m'_k)$.
\end{lemma}
\begin{proof}
Immediate from the definition.
\end{proof}

\begin{lemma}\label{lem:4}
For positive integers $m_1,\dots,m_k,m_{k+1}$, we have 
\[
\bR(m_1,\dots,m_k,m_{k+1})\leq\bR(m_1,\dots,m_k).
\]
Moreover, equality holds if $m_{k+1}\geq\bR(m_1,\dots,m_k)$.
\end{lemma}
\begin{proof}
Let $n=\bR(m_1,\dots,m_k)$ and $g\in C(n,k+1)$.
Define $\sigma:[k+1]\to [k]$ by 
\[
\sigma(i)=\begin{cases}
k&\text{if $i=k+1$,}\\
i&\text{otherwise.}
\end{cases}
\]
Set $f=\sigma\circ g\in C(n,k)$. Then there exists 
$i\in[k]$ such that $\alpha_i(f)\geq m_i$.
Since $g^{-1}(i)\subset f^{-1}(i)$, we have
$\alpha_i(g)\geq\alpha_i(f)\geq m_i$.
Since $g\in C(n,k)$ was arbitrary, we conclude
$\bar{R}(m_1,\dots,m_{k+1})\leq n$.

Since $n=\bR(m_1,\dots,m_k)$, there exists $f\in C(n-1,k)$
such that $\alpha_i(f)<m_i$ for any $i\in [k]$. 
Define a coloring $g\in C(n-1,k+1)$ by 
\[
g^{-1}(i) =
\begin{cases}
f^{-1}(i)&\text{ if } i\in [k],\\
\emptyset  &\text{ if } i=k+1.
\end{cases}
\]
Then 
$\alpha _i(g) =\alpha _i(f)<m_i$ for $i\in[k]$, and
$\alpha _{k+1}(g)= n-1$. Therefore,
$\bR(m_1,\dots,m_k,n)>n-1$. If $m_{k+1}\geq n$, then
Lemma~\ref{lem:2} implies
\[
\bR(m_1,\dots,m_k,m_{k+1})\geq\bR(m_1,\dots,m_k,n)\geq n,
\]
and hence equality is forced.
\end{proof}

By Lemmas~\ref{lem:1} and \ref{lem:4},
we obtain $\bR(m_1,\dots,m_k)\leq R(m_1,m_2)$. In particular,
$\bR(m_1,\dots,m_k)$ is finite.

\begin{lemma}\label{lem:5}
For positive integers $m_1,\dots,m_k$, 
\[
\bR(m_1,\dots,m_k,2)=\min\{m_1,\dots,m_k\}.
\]
\end{lemma}
\begin{proof}
Immediate from the definition.
\end{proof}

We abbreviate
\[
\bar{R}(\underbrace{m,m,\dots,m}_k)
\]
as $\bar{R}(m;k)$.
For a graph $H$ and a positive integer $k$, 
$R(H;k)$ denotes the generalized Ramsey number, which
is the smallest positive integer $n$ such that for any
$f\in C(n,k)$, there exists $i\in[k]$ such that $f^{-1}(i)$
contains a subgraph isomorphic to $H$.

\begin{lemma}\label{lem:RH}
For positive integers $m$ and $k$, let $H$ be any graph
obtained from $K_{m}$ by deleting $k-2$ edges. Then
$\bar{R}(m;k)\leq R(H;k)$.
\end{lemma}
\begin{proof}
Let $n=R(H;k)$ and $f\in C(n,k)$. Then there exists $i\in[n]$ such that
$f^{-1}(i)$ contains $H$ as a subgraph.
By the assumption, $K_m$ can be reconstructed from $H$ by adding $k-2$
edges. Let $\{i_1,\dots,i_{k-2}\}$ be the colors of these $k-2$ edges. Then
there exists $j\in[k]\setminus\{i,i_1,\dots,i_{k-2}\}$, and
the vertex set of $H$ is an independent set in the graph $f^{-1}(j)$.
Thus $\alpha_j(f)\geq m$. Therefore, $\bar{R}(m;k)\leq n$.
\end{proof}

\begin{lemma}\label{lem:lower}
Let $k$ and $m$ be positive integers. Then
$\bR(m;k)\geq m$. Moreover, equality holds if and only if
$k>\binom{m}{2}$.
\end{lemma}
\begin{proof}
If $k\leq\binom{m}{2}$, then
there exists $f\in C(m,k)$ such that $f^{-1}(i)\neq\emptyset$
for all $i\in[k]$. Thus $\alpha_i(f)<m$. This implies $\bR(m;k)>m$.
On the other hand, clearly, $k>\binom{m}{2}$ implies $\bR(m;k)=m$.
\end{proof}

\section{General results}\label{sec:3}

Let $n$ and $k$ be positive integers. For $f\in C(n,k)$ and $x\in [n]$, set
\[
f_i(x)=|\{y\in[n]\mid f(\{x,y\})=i\}|.
\]

\begin{lemma}\label{lem:7}
Let $n,k,m_1,\dots,m_k$ and $t$ be positive integers with $1\leq t\leq k$, and
let $f\in C(n,k)$. If 
\[
\sum_{j=1}^t f_j(x)\geq 
\bar{R}(m_1,m_2,\ldots ,m_t , m_{t+1}-1,\ldots ,m_k-1) 
\]
for some $x\in [n]$, then
$\alpha_i(f)\geq m_i$ for some $i\in [k]$.
\end{lemma}
\begin{proof}
Set
$Y=\{y\in[n]\mid f(\{x,y\})\in[t]\}$,
so that
\[
|Y|=\sum_{j=1}^t f_j(x).
\]
Let $g=f|_{\binom{Y}{2}}$. 
By the assumption, either there exists $i$ with $1\leq i\leq t$
such that $\alpha_i(g)\geq m_i$, or there exists $i$ with
$t<i\leq k$ such that $\alpha_i(g)\geq m_i-1$.

If $1\leq i \leq t$, then $\alpha_i(f)\geq \alpha _i(g)\geq m_i$. 
If $t<i\leq k$, then there exists an independent set
$Z$ in $g^{-1}(i)$ with $|Z|=m_i-1$.
Then $Z\cup \{x\}$ is an independent set in $f^{-1}(i)$. 
This implies $\alpha_i(f)\geq m_i$. 
\end{proof}

\begin{lemma}\label{lem:8}
Let $k,m_1,\dots,m_k$ and $t$ be positive integers. 
Let $[k]=\bigcup_{j=1}^t M_j$ be a nontrivial partition.
For each $i\in[k]$ and $j\in[t]$, define
\[
m_i^{(j)}=\begin{cases}
m_i&\text{if $i \in M_j$,}\\
m_i-1&\text{otherwise.}
\end{cases}
\]
Then
\[
\bR(m_1, \ldots, m_k)\leq 
\sum_{j=1}^t\bR(m_1^{(j)},\dots,m_k^{(j)})-t+2.
\]
\end{lemma}
\begin{proof}
Let $n$ denote the right-hand side of the inequality. 
If $f\in C(n,k)$ and $x\in [n]$, then
\begin{align*} 
\sum_{j=1}^t \sum_{i\in M_j} f_i(x)
&=\sum_{i=1}^k f_i(x)
\nexteq
n-1
\nexteq
\sum_{j=1}^t\bR(m_1^{(j)},\dots,m_k^{(j)})-t+1.
\\&>
\sum_{j=1}^t(\bR(m_1^{(j)},\dots,m_k^{(j)})-1).
\end{align*}
Thus, there exists $j\in[t]$ such that
\[
\sum_{i\in M_j} f_i(x)
\geq\bR(m_1^{(j)},\dots,m_k^{(j)}).
\]
By Lemma~\ref{lem:7}, there exists $i\in[k]$ such that
$\alpha_i(f)\geq m_i$. This implies
$\bar{R}(m_1,\dots,m_k)\leq n$.
\end{proof}

A graph $G$ is said to be a Ramsey $(s,t)$-graph if
$\omega(G)<s$ and $\alpha(G)<t$. 
We write $G\subset H$ if $H$ is a subgraph of $G$. 
For a graph $G$ and its subgraph $H$, 
we denote the graph $(V(G),E(G)\setminus E(H))$ by $G\setminus H$. 

\begin{lemma}\label{lem:RamG}
Let $m_1,m_2,m_3$ and $n$ be positive integers greater than $2$.
Then the following are equivalent.
\begin{enumerate}
\item[{\rm(i)}] $\bR(m_1,m_2,m_3)\leq n$,
\item[{\rm(ii)}] for any two Ramsey $(m_3,m_2)$-graphs $G$ and $H$
on the vertex set $[n]$ 
such that $G\supset H$, one has $\alpha(G\setminus H)\geq m_1$.
\end{enumerate}
\end{lemma}
\begin{proof}
We only prove (ii) implies (i), since a proof of the converse
can be easily constructed by reversing the argument.
Let $f\in C(n,3)$, and assume $\alpha_2(f)<m_2$ and $\alpha_3(f)<m_3$.
Define graphs $G,H$ by $G=f^{-1}(\{1,2\})$ and $H=f^{-1}(2)$. Then
\begin{align*}
\omega(H)&\leq\omega(G)=\alpha_3(f)<m_3,\\
\alpha(G)&\leq\alpha(H)=\alpha_2(f)<m_2.
\end{align*}
Thus both $G$ and $H$ are Ramsey $(m_3,m_2)$-graphs. By (ii), we have
$m_1\leq\alpha(G\setminus H)=\alpha_1(f)$. Therefore (i) holds.
\end{proof}


\section{Factors and complementary Ramsey numbers}\label{sec:4}

A graph $G$ is said to be factorable into spanning subgraphs $H_1,H_2,\dots,H_k$ if 
its edge-set is a disjoint union of those of $H_1,H_2,\dots,H_k$. 
If $H$ is another graph, $G$ is said to be $H$-factorable if 
$G$ is factorable into $H_1,H_2,\dots,H_k$ and $H\cong H_i$
for all $i\in[k]$.

\begin{lemma}\label{lem:4-1}
Let $n$ and $k$ be positive integers. 
Suppose that the complete graph $K_n$ is factorable into 
spanning subgraphs $H_1,H_2,\dots,H_k$. 
Then 
\[
\bR(\alpha(H_1)+1, \alpha(H_2)+1,\ldots ,\alpha (H_k)+1)> n.
\]
\end{lemma}
\begin{proof}
The coloring $f\in C(n,k)$ defined by this 
factorization satisfies $\alpha_i(f)=\alpha(H_i)$,
and this implies the desired inequality.
\end{proof}

For any two integers $m$ and $n\geq 2$, we can write
$m=nq+r$ for unique integers $q,r$ with $0\leq r<n$.
Then 
\[
(\underbrace{q+1,q+1,\ldots ,q+1}_r,
\underbrace{q, q,\ldots ,q}_{n-r})
\]
is a partition of the integer $m$.
We define a graph $\bar{T}_n(m)$ and an integer $\bar{t}_n(m)$  as follows: 
$$\bar{T}_n(m)=rK_{q+1}\cup (n-r)K_q,$$ 
$$\bar{t}_n(m)=|E(\bar{T}_n(m))|=r\binom{q+1}{2}+(n-r)\binom{q}{2}
=\frac12q(m-n+r).$$
Clearly
\begin{equation}\label{eq:q}
\bar{t}_n(m+1)-\bar{t}_n(m)=q.
\end{equation}

\begin{lemma}\label{extremal}
Let $m$ and $n$ be positive integers with $n\geq 2$. 
Let $G$ be a graph of order $m$. If $|E(G)|<\bar{t}_n(m)$, then
$\alpha(G)\geq n+1$. Moreover, if 
$|E(G)|=\bar{t}_n(m)$ and $\alpha (G)=n$, then $G\cong\bar{T}_n(m)$.
\end{lemma}
\begin{proof}
See \cite[Theorem~8 in IV.2]{Bollobas}.
\end{proof}

\begin{lemma}\label{ext}
Let $k,m,n$ be positive integers satisfying
$\bar{t}_{m-1}(n)>\frac{1}{k}\binom{n}{2}$. Then
$\bR(m;k)\leq n$.
\end{lemma}
\begin{proof}
Let $f\in C(n,k)$. Then by the assumption, there exists
$i\in[k]$ such that $\bar{t}_{m-1}(n)>|f^{-1}(i)|$. 
Lemma~\ref{extremal} then implies $\alpha_i(f)\geq m$.
Thus $\bR(m;k)\leq n$.
\end{proof}

\begin{theorem}\label{gen_factorable}
Let $k$ and $N>1$ be integers. Suppose that the complete graph $K_N$ is factorable into 
$H_1$, $H_2$, $\ldots$, $H_k$ where 
$H_i\cong r_iK_{q_i+1}\cup (n_i-r_i)K_{q_i}$
for some non-negative integers $n_i,q_i,r_i$ which satisfy  
$N=n_iq_i+r_i$ and $0\leq r_i< n_i$ for any $i\in [k]$.
Assume further that $(n_i-r_i-1)q_i>0$ for some $i\in[k]$.
Then 
$$\bar{R}(n_1+1, n_2+1, \ldots ,n_k+1)=N+1.$$
\end{theorem}
\begin{proof}
By the assumption, we have 
\begin{align*}
(N-1)\sum_{i=1}^k q_i
&>\sum_{i=1}^k q_i(N-n_i+r_i)
\\&=\sum_{i=1}^k 2\bar{t}_{n_i}(N)
\\&=\sum_{i=1}^k 2|E(H_i)|
\\&=
2|E(K_N)|
\\&=
N(N-1).
\end{align*}
Thus
\begin{equation}\label{eq:N}
\sum_{i=1}^kq_i>N.
\end{equation}
Since
$\bar{t}_{n_i}(N+1)-\bar{t}_{n_i}(N)=q_i  \text{ for any } i\in [k]$,
we have
\begin{align*}
\sum_{i=1}^k \bar{t}_{n_i}(N+1)
&=\sum_{i=1}^k \left( \bar{t}_{n_i}(N)+q_i\right)
\displaybreak[0]\\
&=\sum_{i=1}^k|E(H_i)|+\sum_{i=1}^kq_i
\displaybreak[0]\\
&>\binom{N}{2}+N
&&\text{(by (\ref{eq:N}))}
\displaybreak[0]\\
&=|E(K_{N+1})|.
\end{align*}
Therefore, for any $f\in C(N+1,k)$, there exists some $i\in[k]$ such that 
$\bar{t}_{n_i}(N+1)>|f^{-1}(i)|$.
Then $\alpha _i(f)\geq n_i+1$ by Lemma~\ref{extremal}. This implies 
$$\bar{R}(n_1+1,n_2+1,\ldots ,n_k+1)\leq N+1.$$

The reverse inequality follows from Lemma~\ref{lem:4-1}.
\end{proof}

\begin{corollary}\label{factorable}
Let $m,n$ and $r$ be non-negative integers with $0\leq r<n$. 
If $K_{mn+r}$ is $\left( rK_{m+1}\cup (n-r)K_m\right)$-factorable, 
then 
$$\bar{R}(n+1;N(m,n,r))=
\begin{cases}
mn+r+1 &\text{if $0\leq r\leq n-2$,} \\
mn+n+1 &\text{if $r=n-1$.}
\end{cases}
$$ 
where 
$$
N(m,n,r)=\frac{\binom{mn+r}{2}}{r\binom{m+1}{2}+(n-r)\binom{m}{2}}.
$$
\end{corollary}
\begin{proof}
If $0\leq r\leq n-2$, then the result follows from
Theorem~\ref{gen_factorable}.

Suppose $r=n-1$. Since
$K_{(m+1)n-1}$ is $\left( (n-1)K_{m+1}\cup K_{m}\right)$-factorable
by the assumption,
we see that 
$K_{(m+1)n}$ is $nK_{m+1}$-factorable. Since we have already proved
the statement for the case $r=0$, we find
$\bar{R}(n+1;N(m+1,n,0))=(m+1)n+1$.
Since $N(m+1,n,0)=N(m,n,n-1)$, the result follows in this case as well.
\end{proof}

\section{Examples of factorizations and consequences}\label{sec:5}

In this section, we give consequences of Corollary~\ref{factorable}.
It is well known (\cite{C-L}) that a complete graph of an even order has a
$1$-factorization. In other words, 
$K_{2n}$ is $nK_2$-factorable.
Applying Corollary~\ref{factorable} with $m=2$ and $r=0$,
we obtain the following corollary.

\begin{corollary}\label{cor:1}
For any integer $n\geq2$,
$\bar{R}(n+1;2n-1)=2n+1$.
\end{corollary}

Recall that a Kirkman triple system is a resolvable Steiner triple system,
or equivalently, $nK_3$-factorization of $K_{3n}$. It is known (\cite{S}) that
a Kirkman triple system exists if and only if $3n=6t+3$ for some
non-negative integer $t$.
Applying Corollary~\ref{factorable} with $m=3$ and $r=0$,
we obtain the following corollary.

\begin{corollary}\label{cor:3}
For any non-negative integer $t$,
$\bar{R}(2t+2;3t+1)=6t+4$.
\end{corollary}

A resolvable $2$-$(n,4,1)$ design is an $nK_4$-factorization of $K_{4n}$.
It is known (\cite{S}) that such a design exists if and only if 
$4n=12t+4$ for some non-negative integer $t$.
Applying Corollary~\ref{factorable} with $m=4$ and $r=0$,
we obtain the following corollary.

\begin{corollary}\label{cor:4}
For any non-negative integer $t$,
$\bar{R}(3t+2;4t+1)=12t+5$.
\end{corollary}

In design theory, 
$\left( pK_{m}\cup qK_{m+1}\right)$-factorization of $K_v$ 
is called a class-uniform resolvable design $\CURD(v,k,p,q)$ (of index $1$), 
where 
\[
k=\frac{\binom{v}{2}}{p\binom{m}{2}+q\binom{m+1}{2}}.
\]
Class-uniform resolvable designs are
investigated in several papers (see, for example, \cite{DS}).  

\begin{corollary}\label{cor:5}
If there exists a $\CURD(v,k,p,q)$, then $\bar{R}(p+q+1;k)=v+1$. 
\end{corollary}

A complete set of mutually orthogonal Latin squares (MOLS) of order $n$ 
can be identified with an edge-coloring $f:E(K_{n^2})\to [n+1]$ 
such that $f^{-1}(i)\cong nK_n$ for all $i\in[n+1]$. 

\begin{theorem}\label{thm:MOLS}
There exists a complete set of MOLS of order $n$ if and only if
$\bar{R}(n+1;n+1)=n^2+1$. 
\end{theorem}

\begin{proof}
If there exists a complete set of MOLS of order $n$, then by
Corollary~\ref{factorable}, we have $\bar{R}(n+1;n+1)=n^2+1$.

Conversely, suppose $\bar{R}(n+1;n+1)=n^2+1$. In particular,
$\bar{R}(n+1;n+1)>n^2$. This means that 
there exists $f\in C(n^2;n+1)$ such that $\alpha _i(f)\leq n$ 
for any $i\in [n+1]$. Then by Lemma~\ref{extremal},
we have $|f^{-1}(i)|\geq \bar{t}_n(n^2)$.
Since $$\frac1{n+1}\binom{n^2}{2}=\bar{t}_n(n^2),$$
equality holds in the above inequality, and we have 
$f^{-1}(i)=\bar{T}_n(n^2)=nK_n$
for any $i\in [n+1]$ by the second part of Lemma~\ref{extremal}.
\end{proof}

Table~\ref{table:1} lists the values of $N,n,m,r,k$ such that
$K_N$ is $\left( rK_{m+1}\cup (n-r)K_{m}\right)$-factorable
into $k$ subgraphs.
\begin{table}
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|}
\hline
&$N$ & $n$ & $m$ & $r$ & 
$k$ & $\bar{R}(n+1;k)$ & references\\
\hline 
I&$2t$ & $t$ & $2$ & $0$ &
$2t-1$ & $2t+1$ & $1$-factor\\
II&$6t+3$ & $2t+1$ & $3$ & $0$ &
$3t+1$ & $6t+4$ & \cite{S}\\  
III&$12t+4$ & $3t+1$ & $4$ & $0$ &
$4t+1$ & $12t+5$ & \cite{S}\\
IV&$q^2$ & $q$ & $q$ & $0$
& $q+1$ & $q^2+1$ & affine plane\\
\hline 
V&$12t+9$ & $5t+4$ & $2$ & $3t+3$ &
$8t+6$ & $12t+10$ & \cite{DS}\\
VI&$36t+9$ & $16t+4$ & $2$ & $12t+3$ &
$27t+6$ & $36t+10$ & \cite{DS} \\
\hline
\end{tabular}
\end{center}
\caption{$\bR(n+1;k)$ determined by factorizations}
\label{table:1}
\end{table}
The families I, II, III and IV correspond to Corollaries \ref{cor:1},
\ref{cor:3}, \ref{cor:4} and Theorem~\ref{thm:MOLS}, respectively.
Note that affine planes which give the family IV in Table~\ref{table:1}
are known to exist when $q$ is a prime power (\cite{S}).

Many other factorizations of $K_n$ satisfying
the assumption of Theorem~\ref{gen_factorable} 
are known in terms of designs. 
A nearly Kirkman triple system is a factorization of $K_{6n}$ 
with $H_i\cong 2nK_3$ for $i\in [k-1]$ and $H_k\cong 3nK_2$. 
This exists if and only if $n\geq 3$. 
A uniformly resolvable pairwise balanced design is a factorization of $K_n$ 
satisfying Theorem~\ref{gen_factorable} with $r_i=0$ for any $i\in [k]$. 
For the cases $m_i\in \{1,2\}$, 
these designs exist if and only if $n=6t$ and $3t\leq k \leq 6t-1$ for 
a non-negative integer $t$ with two exceptions, 
corresponding to the non-existence of nearly Kirkman triple systems of 
order $6$ and $12$ (\cite{R}). 
A restricted resolvable design $R_mRP(n,k)$ is a factorization of $K_n$ 
with $H_i=pK_m\cup qK_{m+1}$ for some non-negative integer $p$ and $q$. 
For the case $m=2$, an additional construction of factorizations and
the existence problems of such factorizations are discussed in  \cite{R}, 
\cite{R2}. 
Moreover, a class-uniformly resolvable group divisible design of type 
$g^a$ with partition $s^pt^q$ with $k$ resolution classes 
is a factorization of $K_{g^a}$ with $H_i\cong pK_{s}\cup qK_{t}$ 
for any $i\in [k-1]$ and $H_k\cong aK_{g}$. 
For the case $s=2$ and $t=3$, 
a number of infinite families of factorizations are constructed in 
\cite{DS2}, \cite{DS3}. 

\section{$\bR(m_1,m_2,m_3)$ for small $m_1,m_2,m_3$}\label{sec:6}

\begin{lemma}\label{K-free}
Let $G$ be a $3$-regular graph of order $10$ and assume that
$G$ does not contain $K_4$.
Then $\alpha (G)\geq 4$. 
\end{lemma}
\begin{proof}
By the theorem of Brooks (see \cite[Theorem~3 in V.1]{Bollobas}),
$G$ is $3$-colorable. Then one of the color class has size
greater than $10/3$. This implies that $G$ has an independent
set of size at least $4$.
\end{proof}

We remark that the statement of Lemma~\ref{K-free} does not hold
when $G$ contains $K_4$. This is because the disjoint union of $K_4$
and the $3$-prism is a $3$-regular graph of order $10$ with independence
number $3$.

\begin{lemma}\label{memo}
Let $G$ be a triangle-free graph of order $8$ with a vertex of degree
at most one. 
Then $\alpha (G)\geq 4$. 
\end{lemma}
\begin{proof}
Suppose that $8$ is a vertex of degree at most one. 
Then we may assume $i$ and $8$ are not adjacent for any $i\in [6]$. 
Let $H$ be the graph induced by $[6]$. Since $H$ is triangle-free and $R(3,3)=6$,  
there exists an independent set $W$ of $H$ with $|W|\geq 3$.
Then $W\cup \{8\}$ is an independent set of $G$.  Therefore $\alpha (G)\geq 4$. 
\end{proof}

\begin{theorem}\label{thm:3}
\begin{itemize}
\item[{\rm(i)}] $\bar{R}(3,3,3)=\bar{R}(4,3,3)=\bar{R}(5,3,3)=5$, 
$\bar{R}(6,3,3)=6$. 
\item[{\rm(ii)}] $\bar{R}(4,4,3)=7$, 
$\bar{R}(5,4,3)=\bar{R}(6,4,3)=8$, $\bar{R}(7,4,3)=9$.
\item[{\rm(iii)}] $\bR (4,4,4)=10$. 
\end{itemize}
\end{theorem}
\begin{proof}
(i)  
First we note that $\bar{R}(3,3,3)=5$ follows from
Corollary~\ref{cor:1}.

To show $\bR(4,3,3)=\bR(5,3,3)=5$, it 
is enough to show $\bR(5,3,3)\leq 5$ by Lemma~\ref{lem:2}.
Suppose that $f\in C(5,3)$ satisfies
$\alpha _2(f)\leq 2$ and $\alpha _3(f)\leq 2$. 
Since $C_5$ is a unique simple graph $G$ of order $5$ which 
satisfy $\alpha (G)\leq 2$ and $\omega (G)\leq 2$, 
both $f^{-1}(2)$ and $f^{-1}(3)$ are $C_5$.
This forces $f^{-1}(1)=\emptyset$ and hence $\alpha _1(f)=5$. 
Therefore  $\bar{R}(5,3,3)\leq 5$.

Finally we show $\bR(6,3,3)=6$. Since $\bR(3,3)=R(3,3)=6$,
this follows from Lemma~\ref{lem:4}.

(ii) 
First we show $\bR(4,4,3)=7$.
Since $E(K_6)$ can be partitioned into one $E(\overline{C_6})$
and two $E(3K_2)$'s, $\alpha(\overline{C_6})=2$, and
$\alpha(3K_2)=3$, we obtain $\bR(4,4,3)>6$.
To prove the reverse inequality, 
suppose that there exists $f\in C(7,3)$ satisfying
$\alpha _1(f)\leq 3$, $\alpha _2(f)\leq 3$ and $\alpha _3(f)\leq 2$.
Then by Lemma~\ref{lem:7} and (i), we have
$f_3(x)\leq \bar{R}(3,3,3)-1=4$. On the other hand, 
by Lemmas~\ref{lem:7} and \ref{lem:5}, we have
$f_3(x)=6-(f_1(x) +f_2(x))\geq 6-(\bar{R}(4,4,2)-1)=3$
for any $x\in [7]$.
Since there is no $3$-regular graph on $7$ vertices, we may
assume $f_3(1)=4$.
Then we may assume
$f(\{1,i\})=3$ for  $i\in Y=\{ 2,3,4,5\}$. 
Setting $g=f|_{\binom{Y}{2}}$,
we have $\alpha _i(g)\leq 2$ for any $i\in [3]$. 
This implies that $g$ is a $1$-factorization of $K_4$. 
Without loss of generality, we may assume that $g(\{2,3\})=g(\{4,5\})=1$, 
$g(\{2,4\})=g(\{3,5\})=2$ and  $g(\{2,5\})=g(\{3,4\})=3$. 
Moreover we may assume $f(\{1,6\})=1$.
Since $\{1,2,5,6\}$ cannot be an independent set in $f^{-1}(2)$,
we may assume $f(\{2,6\})=2$. 
Since $\{2,3,6\}$ and $\{2,4,6\}$ cannot be
independence sets in $f^{-1}(3)$,  
we have $f(\{3,6\})=f(\{4,6\})=3$. 
Then $\{1,3,4,6\}$
is an independence set in $f^{-1}(2)$, contradicting $\alpha_2(f)\leq 3$.
Therefore $\bar{R}(4,4,3)\leq 7$. 

Next we show $\bR(5,4,3)=\bR(6,4,3)=8$.
Define  a coloring $f\in C(7,3)$ by
\begin{align*}
f^{-1}(1)&=\left\{ \{ 2, 5\}, \{ 3, 6\}, \{4, 7\}\right\}, \\
f^{-1}(2)&=\left\{ \{ 1,  2\}, \{2,3\}, \ldots ,\{7,1\} \right\}
\cong C_7,\\
f^{-1}(3)&=\binom{[7]}{2}\setminus \left( f^{-1}(1) \cup f^{-1}(2) \right).
\end{align*} 
Then $\alpha _1(f)=4, \alpha _2 (f)=3$ and $\alpha _3(f)=2$. 
Therefore $7< \bR (5,4,3)\leq \bR (6,4,3)$. 
To prove $\bR(5,4,3)=\bR (6,4,3)=8$, we show $\bR (6,4,3) \leq 8$. 
Suppose that there exists $f\in C(8,3)$ such that  
$\alpha _1(f)\leq 5, \alpha _2 (f)\leq 3$ and $\alpha _3(f)\leq 2$. 
By Lemma~\ref{lem:5}, Lemma~\ref{lem:7} and (i),
\begin{align}
f_3(i)&\leq \bar{R}(5,3,3)-1=4,\label{f3}\\
f_1(i)+f_2(i)&\leq \bar{R}(6,4,2)-1=3,\label{f12}
\end{align}
for any $i\in [8]$. Since $f_1(i)+f_2(i)+f_3(i)=7$, equality
holds in (\ref{f3}) and (\ref{f12}).
Since $\alpha_3(f)\leq2$, $f^{-1}(2)$ is triangle-free.
Since $\alpha_2(f)\leq3$, Lemma~\ref{memo} implies $f_2(i)\geq2$
for all $i\in[8]$. 
Since $\alpha_1(f)\leq5$, $f^{-1}(1)\neq\emptyset$, so by (\ref{f12}),
there exists $i\in[8]$ such that $f_2(i)=2$. 
Therefore we may assume $f_2(8)=2$ and $f(\{6,8\})=f(\{7,8\})=2$. 
Since $\alpha_3(f)\leq2$, we have $f(\{6,7\})=3$.
Let $g$ denote the restriction of $f$ to ${\binom{[5]}{2}}$. 
Then by the assumption $\alpha _3(g)\leq \alpha _3(f)\leq2$. 
Moreover, if $Y$ is an independence set of $g^{-1}(2)$, 
then $Y\cup \{8\}$ is an 
independence set of $f^{-1}(2)$. 
Therefore $\alpha _2(g)\leq \alpha _2(f)-1\leq 2$. 
This implies $g^{-1}(2)\cong g^{-1}(3)\cong C_5$ 
and $\binom{[5]}{2}\cap f^{-1}(1)=\emptyset$. 
We may assume $\left\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{1,5\}\right\}\subset f^{-1}(2)$ 
and $\left\{\{1,3\},\{3,5\},\{2,5\},\{2,4\},\{1,4\}\right\}\subset f^{-1}(3)$. 
Since $f_2(i)\geq 2$ and $f_1(i)\leq 1$ 
for each $i\in [8]$ and $\alpha _1(f)\leq 5$, each of $\{6,7,8\}$ is adjacent in $f^{-1}(1)$ to 
a unique vertex in $[5]$. By symmetry, we may assume $f(\{1,8\})=1$. 
Now since $f_1(1)=1$ and $f_2(1)=2$, we can apply the same argument as above, 
using $1$, $\{1,2\}$ and $\{1,5\}$ instead of $8$, $\{6,8\}$ and $\{7,8\}$, respectively. 
Then we obtain $\binom{\{3,4,6,7,8\}}{2}\cap f^{-1}(1)=\emptyset$. 
In particular, neither $6$ nor $7$ is adjacent in $f^{-1}(1)$ to $3$ or $4$. 
Then by symmetry, we may assume $f(\{2,6\})=f(\{5,7\})=1$. 
Since $f(\{1,2\})=f(\{2,3\})=2$, we can again apply the same argument, 
using $2$, $\{1,2\}$ and $\{2,3\}$, and obtain $\binom{\{4,5,6,7,8\}}{2}\cap f^{-1}(1)=\emptyset$. 
However, this contradicts $f(\{5,7\})=1$. 

Finally, we show $\bR(7,4,3)=9$.
Define  a coloring $f\in C(8,3)$ by
\begin{align*}
f^{-1}(1)&=\left\{ \{ 1, 5\}, \{ 2, 6\}\right\},\\
f^{-1}(2)&=\left\{ \{ 1,  2\}, \{2,3\}, \ldots ,\{8,1\} \right\}
\cup \left\{  \{3,7\}, \{ 4,8\}  \right\},\\
f^{-1}(3)&=\binom{[8]}{2}\setminus 
\left( f^{-1}(1) \cup f^{-1}(2) \right).
\end{align*}
Then $\alpha _1(f)=6$, $\alpha _2 (f)=3$ and $\alpha _3(f)=2$.
Therefore $\bar{R}(7,4,3)> 8$. 
On the other hand, 
$\bar{R}(k,4,3)\leq \bar{R}(4,3)=R(4,3)=9$.
Therefore $\bar{R}(k,4,3)=9$ for $k\geq 7$.

(iii) 
Since $\bR(4,4,4)\geq\bR(4,4,4,4)$ by Lemma~\ref{lem:4}, 
we see $\bR(4,4,4)\geq3^2+1=10$ by Theorem~\ref{thm:MOLS}.
To prove the reverse inequality, let
$f\in C(10,3)$ and $x\in [10]$.
If $f_i(x)+f_j(x)\geq\bar{R}(4,4,3)$ for some distinct
$i,j\in [3]$, then $\alpha_k(f)\geq4$ for some $k\in[3]$
by Lemma~\ref{lem:7}.
Thus we may
assume $f_i(x)+f_j(x)\leq \bar{R}(4,4,3)-1$ for any distinct
$i,j\in [3]$. Then
$$9=f_1(x)+f_2(x)+f_3(x)\leq\frac{3}{2}(\bar{R}(4,4,3)-1)
=9$$
by (ii), hence equality is forced. 
This implies that $f_i(x)=3$ for any $i\in [3]$. 
If $f^{-1}(3)$ contains $K_4$, 
then $\alpha_1(f)\geq 4$. 
If $f^{-1}(3)$ does not contain $K_4$, then
by Lemma~\ref{K-free}, we have $\alpha_3(f)\geq 4$.
Therefore $\bar{R}(4,4,4)\leq 10$. 
\end{proof}

\begin{theorem}\label{thm:k}
\begin{enumerate}
\item[{\rm(i)}] $\bR(4;6)=5$,
\item[{\rm(ii)}] $\bR(5;k)=6$ for $8\leq k\leq 10$,
\item[{\rm(iii)}] $\bR(6;8)=11$, $\bR(6;10)=8$ and $\bR(6;k)=7$ for
$11\leq k\leq 15$.
\end{enumerate}
\end{theorem}
\begin{proof}
Note that the upper bounds for each of these complementary Ramsey
numbers are derived from Lemma~\ref{ext}. Note also that
the lower bounds are derived from Lemma~\ref{lem:lower}
for $\bR(4;6)$, $\bR(5;k)$ for $8\leq k\leq 10$, and
$\bR(6;k)$ for $11\leq k\leq 15$. Also, 
$\bR(6;8)\geq\bR(6;9)=11$ by Lemma~\ref{lem:4} and
Corollary~\ref{cor:1}.
Thus, it remains to show $\bR(6;10)\geq8$.

Define $f\in C(7,10)$ by 
\begin{align*}
f^{-1}(i)&=\left\{ \{ i+2, i+5\}, \{i+3, i+4\} \right\} \text{ if } i\in [7], \\
f^{-1}(8)&=\left\{ \{1, 3\}, \{ 2,4\}\right\}, \\
f^{-1}(9)&=\left\{ \{3, 5\}, \{ 4,6\}\right\}, \\
f^{-1}(10)&=\left\{ \{5, 7\}, \{ 6,1\}, \{2,7\}\right\},
\end{align*}
where, in the definition of $f^{-1}(i)$,
the elements are read modulo $7$.
Then 
$\alpha _i(f)=5$ for any $i\in [10]$, and hence
$\bR (6;10)>7$. 
\end{proof}

In Table~\ref{tab2}, the values with subscripts
I--V are given by the corresponding row of Table~\ref{table:1},
those with subscript $b$ are given by 
Lemma~\ref{lem:lower}, 
while those with $c$ are given by Theorem~\ref{thm:k}.
We remark that upper bounds for some of the complementary 
Ramsey numbers in Table~\ref{tab3} 
can also be derived from known list of Ramsey 
$(s,t)$-graphs, using Lemma~\ref{lem:RamG}.


\begin{table}
\begin{center}
\begin{tabular}{|c|ccccccccccccc|}
\hline
$k$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ & $\cdots$ &  $15$ & $16$ \\
\hline 
$\bar{R}(3;k)$ & {$6$} & {$5_{\text{I}}$} & {$3_b$} & $\cdots$ &&&&&&&&&\\
\hline
$\bar{R}(4;k)$ & {$18$} & {$10$} & {$10_{\text{II}}$} & {$7_{\text{I}}$}  
& {$5_c$} & {$4_b$} 
&  $\cdots$ & & & & &&\\
\hline 
$\bar{R}(5;k)$ & ? & ? & ? & {$17_{\text{III}}$} 
& {$10_{\text{V}}$} & {$9_{\text{I}}$} 
& {$6_c$} & {$6_c$} & {$6_c$} & {$5_b$} & $\cdots$ &&\\
\hline 
$\bar{R}(6;k)$ & ? & ? & ? & ? & {$26_{\text{IV}}$} 
& {$16_{\text{II}}$} & 
{$11_c$} & {$11_{\text{I}}$} & {$8_c$} & {$7_c$} & {$\cdots$} & {$7_c$}  & {$6_b$}\\
\hline
\end{tabular}
\caption{$\bR(m;k)$ for $m=3,4,5,6$}
\label{tab2}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{|c|cccccc|}
\hline
$m_1$& $3$ & $4$ & $5$ & $6$ & $7$ & $8$\\
\hline 
$\bar{R}(m_1,3,3)$ & {$5$} & $5$ & $5$ & {$6$} & $\cdots$ & \\
\hline 
$\bar{R}(m_1,4,3)$ & - & $7$ & $8$ & $8$ &  {$9$} & $\cdots$\\
\hline
\end{tabular}
\caption{$\bR(m_1,m_2,3)$ for $m_2=3,4$}
\label{tab3}
\end{center}
\end{table}


\subsection*{Acknowledgements}
The authors would like to thank Katsuhiro Ota and a referee for 
providing us with a simplification of the proof of
Lemma~\ref{K-free}, Lemma~\ref{memo} and a part of the proof of Theorem~\ref{thm:3}. 

\begin{thebibliography}{99}
\bibitem{Bollobas} B. Bollob\'as, Modern Graph Theory,
Springer, 1998.
\bibitem{Magma}
W. Bosma, J. J. Cannon, C. Fieker, A. Steel (eds.).,
Handbook of Magma Functions.
Edition 2.19, 5291 pages. 2013.
\bibitem{C-L} G. Chartrand, L. Lesniak and P. Zhang,
Graphs and Digraphs, CRC Press, 5th ed., 2011.
\bibitem{DS} P. Danziger and B. Stevens, Class-uniformly resolvable designs, 
J. Combin.  Designs. 9 (2001), 79--99. 
\bibitem{DS2}  P. Danziger and B. Stevens, Class-uniformly resolvable group divisible 
structures I: Resolvable group divisible designs, 
Electron. J. Combin. 11:R23, 2004. 
\bibitem{DS3}  P. Danziger and B. Stevens, Class-uniformly resolvable group divisible 
structures II: Frames, 
Electron. J. Combin. 11:R24, 2004. 
\bibitem{Ramsey}
R.L. Graham, B.L. Rothschild and J.H. Spencer,
Ramsey Theory, 2nd ed., Wiley, New York, 1990.
\bibitem{LRV} E. Lamken, R. Rees and S. Vanstone, 
Class-uniformly resolvable pairwise balanced designs with block sizes two and three, 
Discrete Math. 92 (1991), 197--209.
\bibitem{R} R. Rees, 
Uniformly resolvable pairwise balanced designs with block size two and three, 
J.\ of Combin.  Theory Ser. A, 45 (1987), 207--225. 
\bibitem{R2} R. Rees, 
The existence of restricted resolvable designs I: $(1,2)$-factorizations of $K_{2n}$, 
Discrete Math. 81 (1990), 49--80. 
\bibitem{Shino} M. Shinohara,
Uniqueness of maximum three-distance sets in the three-dimensional Euclidean space,
preprint {\tt arXiv:1309.2047}.
\bibitem{S} D.R. Stinson, 
Combinatorial Designs: Construction and Analysis, Springer, 2004. 
\end{thebibliography}
\end{document}

1406.2050.extracted_bib
{Bollobas B. Bollob\'as, Modern Graph Theory, Springer, 1998.
1406.2050.extracted_bib
{Magma W. Bosma, J. J. Cannon, C. Fieker, A. Steel (eds.)., Handbook of Magma Functions. Edition 2.19, 5291 pages. 2013.
1406.2050.extracted_bib
{C-L G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, CRC Press, 5th ed., 2011.
1406.2050.extracted_bib
{DS P. Danziger and B. Stevens, Class-uniformly resolvable designs, J. Combin. Designs. 9 (2001), 79--99.
1406.2050.extracted_bib
{DS2 P. Danziger and B. Stevens, Class-uniformly resolvable group divisible structures I: Resolvable group divisible designs, Electron. J. Combin. 11:R23, 2004.
1406.2050.extracted_bib
{DS3 P. Danziger and B. Stevens, Class-uniformly resolvable group divisible structures II: Frames, Electron. J. Combin. 11:R24, 2004.
1406.2050.extracted_bib
{Ramsey R.L. Graham, B.L. Rothschild and J.H. Spencer, Ramsey Theory, 2nd ed., Wiley, New York, 1990.
1406.2050.extracted_bib
{LRV E. Lamken, R. Rees and S. Vanstone, Class-uniformly resolvable pairwise balanced designs with block sizes two and three, Discrete Math. 92 (1991), 197--209.
1406.2050.extracted_bib
{R R. Rees, Uniformly resolvable pairwise balanced designs with block size two and three, J.\ of Combin. Theory Ser. A, 45 (1987), 207--225.
1406.2050.extracted_bib
{R2 R. Rees, The existence of restricted resolvable designs I: $(1,2)$-factorizations of $K_{2n$, Discrete Math. 81 (1990), 49--80.
1406.2050.extracted_bib
{Shino M. Shinohara, Uniqueness of maximum three-distance sets in the three-dimensional Euclidean space, preprint {\tt arXiv:1309.2047.
1406.2050.extracted_bib
{S D.R. Stinson, Combinatorial Designs: Construction and Analysis, Springer, 2004.