\documentclass[11pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[margin=27mm]{geometry}
\usepackage{lmodern,amsmath,amssymb,amsthm,microtype}
\usepackage{graphicx,tikz,booktabs,array,xcolor,flafter,needspace}
\usepackage[font=small,labelfont=bf]{caption}
\usepackage[section]{placeins}
\usepackage[hidelinks]{hyperref}
\usepackage{orcidlink}
\usetikzlibrary{arrows.meta,decorations.pathreplacing,positioning}
\definecolor{edgeblue}{HTML}{0072B2}
\definecolor{edgered}{HTML}{B34700}
\definecolor{edgegreen}{HTML}{007C59}
\tikzset{
 vertex/.style={circle,fill=black,inner sep=1.5pt},
 blueedge/.style={edgeblue,line width=1.0pt},
 rededge/.style={edgered,line width=1.0pt,dashed},
 greenedge/.style={edgegreen,line width=1.1pt,dash pattern=on 4pt off 1.5pt on .8pt off 1.5pt}
}
\newcommand{\edge}[2]{\{#1,#2\}}
\newcommand{\Rnn}{R_{\mathrm{nn}}}
\newcommand{\blocklabels}{%
 \foreach \lo/\hi/\lab in {0/1/X,2/4/U,5/6/V,7/9/W}{%
  \draw[decorate,decoration={brace,mirror,amplitude=3pt},draw=black!65]
   (\lo-.25,-.58)--(\hi+.25,-.58);
  \node at ({(\lo+\hi)/2},-.99) {$\lab$};
 }%
}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\renewcommand{\topfraction}{.90}
\renewcommand{\bottomfraction}{.85}
\renewcommand{\textfraction}{.08}
\renewcommand{\floatpagefraction}{.78}
\hypersetup{
 pdftitle={Counterexamples to the multicolor nonnested matching conjecture},
 pdfauthor={Pedro M. M. de Castro},
 pdfsubject={A uniform counterexample with an elementary proof},
 pdfkeywords={ordered graph; nonnested matching; Ramsey number}
}
\title{Counterexamples to the multicolor\\nonnested matching conjecture}
\author{Pedro M. M. de Castro\,\orcidlink{0000-0002-9470-7458}\\
\small Centro de Inform\'atica, Universidade Federal de Pernambuco\\
\small Recife, Pernambuco, Brazil\\
\small \texttt{pmmc@cin.ufpe.br}}
\date{October 17, 2026}
\begin{document}
\maketitle

\begin{abstract}
We show that excluding nested pairs can increase the number of vertices needed to force a matching of one color, disproving a conjecture of Barát, Gyárfás and Tóth. A matching consists of edges with no shared endpoint. In a fixed vertex order, two edges are nested if both endpoints of one lie between those of the other. For $r$ colors and a target of $k$ edges, the classical theorem guarantees a matching of one color on $(r-1)(k-1)+2k$ vertices when every pair is joined by an edge. For every $r,k\ge3$, we construct a coloring at this very threshold in which every such matching contains a nested pair. Thus the nonnested threshold is larger by at least one vertex. Already with three colors, ten vertices force three disjoint edges of one color, while our coloring makes every such triple contain a nested pair. The self-contained proof combines endpoint counts with two edge recolorings that obstruct the pairings allowed by the vertex order.
\end{abstract}

\medskip
\noindent\textbf{AI-use disclosure.}
This work was developed with substantial use of OpenAI's ChatGPT and Codex and Anthropic's Claude for literature searches, mathematical exploration, the development and review of proofs, and manuscript preparation. The author directed the research and contributed to successive revisions of the exposition, with particular attention to making the explanations, examples, and figures clearer for mathematically trained readers outside the immediate specialty. The manuscript is primarily AI-generated. The author understands the mathematical construction and proof presented here and takes responsibility for the mathematical content.

\medskip
\noindent\textbf{Keywords.} ordered graph; nonnested matching; Ramsey number.

\section{Introduction}\label{sec:introduction}
Take $n$ vertices, join every pair by an edge, and color each edge with one of $r$ colors. We seek $k$ edges of one color with no shared endpoint, a \emph{monochromatic matching}. For fixed $r$ and $k$, there is a least number of vertices that guarantees such a matching in every coloring. We ask whether this minimum still suffices when the vertices have a fixed order and nested pairs are forbidden. We show, by explicit colorings, that the additional restriction can raise the minimum.

With the vertices placed in the order $1,\ldots,n$, this is the \emph{ordered complete graph} $K_n$. A matching with $k$ edges uses $2k$ distinct vertices; selecting it leaves all other edges of the graph in place. The vertex order stays fixed while the matching and its color may be chosen freely.

Write an edge $\edge ab$ as $ab$ when the endpoints are unambiguous, always with $a<b$. Two disjoint edges $ab$ and $cd$, with $a<c$, are \emph{nested} if $a<c<d<b$: both endpoints of $cd$ lie between those of $ab$. The other possibilities are $a<b<c<d$ (separated edges) and $a<c<b<d$ (crossing edges), as illustrated in Fig.~\ref{fig:positions}. A matching is \emph{nonnested} if it has no nested pair. In the drawings, edges are arcs above the ordered vertices; crossings of these arcs are allowed and do not create vertices.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[font=\small,x=.83cm,y=1cm]
\begin{scope}
\node at (1.5,1.28) {(a) Separated};
\draw[line width=1pt] (0,0) .. controls (0,.50) and (1,.50) .. (1,0);
\draw[line width=1pt] (2,0) .. controls (2,.50) and (3,.50) .. (3,0);
\foreach \j in {1,...,4}{\node[vertex] at (\j-1,0) {};\node[below=4pt] at (\j-1,0) {\j};}
\node at (1.5,-.75) {allowed};
\end{scope}
\begin{scope}[xshift=5.2cm]
\node at (1.5,1.28) {(b) Crossing};
\draw[line width=1pt] (0,0) .. controls (0,1) and (2,1) .. (2,0);
\draw[line width=1pt] (1,0) .. controls (1,1) and (3,1) .. (3,0);
\foreach \j in {1,...,4}{\node[vertex] at (\j-1,0) {};\node[below=4pt] at (\j-1,0) {\j};}
\node at (1.5,-.75) {allowed};
\end{scope}
\begin{scope}[xshift=10.4cm]
\node at (1.5,1.28) {(c) Nested};
\draw[line width=1pt] (0,0) .. controls (0,1.15) and (3,1.15) .. (3,0);
\draw[line width=1pt] (1,0) .. controls (1,.42) and (2,.42) .. (2,0);
\foreach \j in {1,...,4}{\node[vertex] at (\j-1,0) {};\node[below=4pt] at (\j-1,0) {\j};}
\node at (1.5,-.75) {forbidden};
\end{scope}
\end{tikzpicture}
\caption{The order restriction on two disjoint edges. In (a) and (b), neither edge has both endpoints between those of the other. In (c), the edge $23$ lies inside $14$. The drawings show only the selected edges of a complete graph.}
\label{fig:positions}
\end{figure}

A matching that fails the order condition may coexist with a suitable matching in another color. For example, on six vertices, let exactly the edges $16$, $25$ and $34$ be red and all other edges be blue. These three red edges form a matching in which every pair is nested, whereas the blue matching $\{13,24,56\}$ is nonnested. A counterexample must therefore prevent the required nonnested matching in every color simultaneously.

Let $\Rnn^{(r)}(k)$ be the least integer $n$ for which every $r$-coloring of the ordered $K_n$ contains a monochromatic nonnested matching with $k$ edges. Without the nonnesting condition, Cockayne and Lorimer~\cite{CL1975} proved that the corresponding threshold is
\begin{equation}\label{eq:ordinary}
(r-1)(k-1)+2k.
\end{equation}
For three colors and three edges, this gives ten vertices: every three-coloring of $K_{10}$ contains a monochromatic three-edge matching. The nonnested threshold is therefore at least the ordinary one.

Barát, Gyárfás and Tóth~\cite[Conjecture~4.1(i)]{BGT2024} conjectured that the threshold remains unchanged:
\begin{equation}\label{eq:conjecture}
\Rnn^{(r)}(k)=(r-1)(k-1)+2k.
\end{equation}
This equality holds for two-edge matchings in any number of colors~\cite[Theorem~2.11]{BGT2024}, and for three-edge matchings in two colors~\cite[Theorem~2.10]{BGT2024}. These positive cases make the proposed equality natural. The next theorem shows that three colors and three edges already permit a counterexample, and that the failure persists throughout the larger parameter range.

\begin{theorem}\label{thm:main}
For every pair of integers $r,k\ge3$, there is an $r$-coloring of the ordered complete graph on $(r-1)(k-1)+2k$ vertices with no monochromatic nonnested matching with $k$ edges. Consequently,
\begin{equation}\label{eq:bound}
\Rnn^{(r)}(k)\ge (r-1)(k-1)+2k+1.
\end{equation}
\end{theorem}
The proof is given in Sections~\ref{sec:construction}--\ref{sec:more-colors}. For $r=k=3$, the construction colors $K_{10}$ and gives $\Rnn^{(3)}(3)\ge11$. At the ten vertices that force an ordinary monochromatic three-edge matching, our coloring forces every such matching to contain a nested pair. Fig.~\ref{fig:construction} displays this coloring; we use the same example throughout the proof.

Our construction starts with a blue graph described by Barát, Freschi and Tóth~\cite[Section~2.2, after Conjecture~2.6]{BFT2025}, which already avoids a nonnested $k$-edge matching. We color every remaining edge red or green so that these two colors also avoid the target. A first recoloring eliminates a red nonnested matching and creates a green one. A second recoloring eliminates that green matching, and its position in the vertex order prevents it from restoring a red nonnested target. The proof shows why these changes leave no alternative: endpoint counts and the nonnesting condition restrict the possible endpoints, after which the order forces their partners to appear in increasing order. All three color classes are verified in full below.

Theorem~\ref{thm:main} establishes a strict increase over the ordinary threshold; the exact larger value remains open. It also refutes the universal assertion in Conjecture~2.8 of~\cite{BGT2024}, which allows different required matching sizes in the different colors and includes the equal-size setting of our counterexamples. Our construction starts with three colors, leaving the two-color problem outside its scope.

The author's preprint~\cite{Castro2026} classifies the smallest edge sets whose deletion destroys every nonnested perfect matching and constructs graphs exceeding the extremal bound conjectured by Barát, Freschi and Tóth. These questions concern the edges retained in a single ordered graph. Here, all edges of the complete graph must be partitioned into color classes that simultaneously avoid the target matching. The construction and proof are self-contained.

\section{The three-color construction}\label{sec:construction}
We first build the counterexample for three colors, where Eq.~\eqref{eq:ordinary} gives $4k-2$ vertices. Four consecutive vertex blocks separate the roles of the colors. Almost every edge follows a rule determined by its two blocks. The proof will restrict the possible endpoints of a target matching, and two exceptional edges will obstruct the increasing pairings required in red and green.

Fix $k\ge3$ and partition the vertices into consecutive blocks
\[
X<U<V<W,\qquad
|X|=|V|=k-1,\qquad |U|=|W|=k.
\]
Here $X<U$ means that every vertex of $X$ precedes every vertex of $U$, and similarly for the other blocks. Write
\[
U=\{u_1<\cdots<u_k\},\qquad
V=\{v_1<\cdots<v_{k-1}\},\qquad
W=\{w_1<\cdots<w_k\}.
\]
Color all edges as follows:
\begin{enumerate}
\item Blue: every edge with an endpoint in $X$, and every edge with both endpoints in $U$.
\item Red: every edge from $U$ to $W$ except $u_1w_1$, every edge with both endpoints in $W$, and the edge $v_1w_2$.
\item Green: every remaining edge.
\end{enumerate}
In particular, $u_1w_1$ is green and $v_1w_2$ is red. Table~\ref{tab:blocks} records the complete assignment by block pair. It shows that the green edges are precisely $u_1w_1$ together with all edges in $U\cup V\cup W$ having an endpoint in $V$, except for $v_1w_2$.

\begin{table}[htbp]
\centering
\caption{The coloring by block pair. A diagonal entry concerns edges within one block. Every edge involving $X$ is blue. The only exceptions to a constant color between blocks are $u_1w_1$ and $v_1w_2$.}
\label{tab:blocks}
\renewcommand{\arraystretch}{1.25}
\begin{tabular}{@{}c>{\centering\arraybackslash}p{1.2cm}>{\centering\arraybackslash}p{1.2cm}>{\centering\arraybackslash}p{1.2cm}>{\centering\arraybackslash}p{5.0cm}@{}}
\toprule
 & $X$ & $U$ & $V$ & $W$\\
\midrule
$X$ & blue & blue & blue & blue\\
$U$ & & blue & green & red, except $u_1w_1$ green\\
$V$ & & & green & green, except $v_1w_2$ red\\
$W$ & & & & red\\
\bottomrule
\end{tabular}
\end{table}

The blue graph has the form cited in the introduction: every pair of vertices in $X\cup U$ is blue, and each later vertex is joined in blue exactly to $X$. This is the single-color construction of~\cite[Section~2.2 and Fig.~4]{BFT2025}. The red and green assignment completes the coloring of the entire graph. To see the purpose of the two exceptional edges, first make all edges from $U$ to $W$ red and all edges from $V$ to $W$ green, keeping the other block rules. This initial coloring contains the red nonnested matching $u_1w_1,\ldots,u_kw_k$. Changing $u_1w_1$ from red to green blocks that matching and creates the green candidate
\[
u_1w_1,\ v_1w_2,\ v_2w_3,\ \ldots,\ v_{k-1}w_k.
\]
Changing $v_1w_2$ from green to red blocks this second candidate and gives the final coloring in Table~\ref{tab:blocks}. The proof in Section~\ref{sec:proof} shows that these two changes leave no alternative in either color.

For $k=3$, the blocks and exceptional edges are
\[
X=\{1,2\},\quad U=\{3,4,5\},\quad
V=\{6,7\},\quad W=\{8,9,10\},\qquad
u_1w_1=38,\quad v_1w_2=69.
\]
Fig.~\ref{fig:construction} displays this coloring. Its matrix specifies every edge, while the arc drawing isolates the two exceptions. We will use these same vertex labels when illustrating the proof.

\begin{figure}[htbp]
\centering
{\small (a) Ordered blocks and exceptional edges}\par\medskip
\begin{tikzpicture}[font=\small,x=.95cm,y=1cm]
\draw[greenedge] (2,0) .. controls (2,2.15) and (7,2.15) .. (7,0);
\draw[rededge] (5,0) .. controls (5,1.25) and (8,1.25) .. (8,0);
\foreach \j in {1,...,10}{
 \node[vertex] at (\j-1,0) {};
 \node[below=4pt] at (\j-1,0) {\j};
}
\blocklabels
\end{tikzpicture}
\par\smallskip
{\small
\tikz[baseline=-.55ex]\draw[greenedge] (0,0)--(.65,0);
\(\edge38=u_1w_1\): green
\qquad
\tikz[baseline=-.55ex]\draw[rededge] (0,0)--(.65,0);
\(\edge69=v_1w_2\): red
}\par\bigskip
{\small (b) Complete coloring: the cell in row \(a\), column \(b\) gives the color of \(\edge ab\)}\par\medskip
\begin{tikzpicture}[font=\small,x=.57cm,y=.57cm]
\foreach \a in {1,...,9}{
 \pgfmathtruncatemacro{\start}{\a+1}
 \foreach \b in {\start,...,10}{
  \def\cc{edgegreen}\def\ll{G}
  \ifnum\a<3 \def\cc{edgeblue}\def\ll{B}\else
   \ifnum\a<6 \ifnum\b<6 \def\cc{edgeblue}\def\ll{B}\fi\fi
   \ifnum\a>7 \def\cc{edgered}\def\ll{R}\fi
   \ifnum\a>2 \ifnum\a<6 \ifnum\b>7 \def\cc{edgered}\def\ll{R}\fi\fi\fi
  \fi
  \ifnum\a=3 \ifnum\b=8 \def\cc{edgegreen}\def\ll{G}\fi\fi
  \ifnum\a=6 \ifnum\b=9 \def\cc{edgered}\def\ll{R}\fi\fi
  \filldraw[fill=\cc!14,draw=black!18,line width=.25pt]
   (\b-2-.46,1-\a-.46) rectangle (\b-2+.46,1-\a+.46);
  \node at (\b-2,1-\a) {\ll};
 }
}
\node at (4,1.90) {larger endpoint \(b\)};
\node at (-1.05,.95) {\(a\)};
\foreach \b in {2,...,10}{\node at (\b-2,.95) {\b};}
\foreach \a in {1,...,9}{\node at (-1.05,1-\a) {\a};}
\draw[line width=1pt] (5.53,-2.47) rectangle (6.47,-1.53);
\draw[line width=1pt] (6.53,-5.47) rectangle (7.47,-4.53);
\end{tikzpicture}
\par\smallskip
{\small \(B\): blue \qquad \(R\): red \qquad \(G\): green.\quad
The boxes mark \(\edge38\) and \(\edge69\).}
\caption{The three-color counterexample on ten vertices, with block sizes \(2,3,2,3\). In (a), only the two exceptional edges are drawn; their endpoints alternate, \(3<6<8<9\), so they cross without nesting. The braces identify the vertex blocks. In (b), all 45 edge colors are recorded, including edges absent from (a). For example, row \(3\), column \(8\) is the boxed green entry. The cell letters and line patterns preserve the information without color.}
\label{fig:construction}
\end{figure}

\Needspace{10\baselineskip}
\section{Why each color avoids the matching}\label{sec:proof}
The verification uses the same observation twice: when a nonnested matching pairs all vertices of one ordered list with all vertices of a later list, the partners must appear in increasing order. After proving this observation, we rule out blue by counting endpoints and rule out red and green by locating a required edge of the wrong color. Each argument applies to arbitrary $k\ge3$.

\begin{lemma}[Increasing partners]\label{lem:partners}
Let $p_1<\cdots<p_m<q_1<\cdots<q_m$ be $2m$ distinct ordered vertices. The only nonnested matching that pairs every $p_i$ with a vertex of $\{q_1,\ldots,q_m\}$ is
\[
p_1q_1,\ p_2q_2,\ \ldots,\ p_mq_m.
\]
\end{lemma}
\begin{proof}
Such a matching has the form $p_iq_{\pi(i)}$, where $\pi$ is a permutation of $1,\ldots,m$. If $i<j$ but $\pi(i)>\pi(j)$, then
\[
p_i<p_j<q_{\pi(j)}<q_{\pi(i)},
\]
so these two edges are nested. Avoiding every such pair forces $\pi(1)<\cdots<\pi(m)$, hence $\pi(i)=i$ for all $i$. Conversely, in the displayed matching any two edges cross, so no pair is nested.
\end{proof}

For example, pairing $\{3,4,5\}$ with $\{8,9,10\}$ in a nonnested way forces $38$, $49$ and $\edge5{10}$. Changing the last two partners to obtain $\edge4{10}$ and $59$ puts the latter edge inside the former. This is the order constraint that the two exceptions in the construction exploit.

\Needspace{7\baselineskip}
\subsection{Blue: too few vertices remain}\label{sec:blue}
A blue edge from $X$ to $V\cup W$ surrounds every edge inside $U$. A nonnested matching cannot use both types. Counting endpoints first forces an edge inside $U$; the order restriction then confines the entire matching to $X\cup U$. That set has one fewer vertex than a $k$-edge matching needs.

Suppose that there were a blue nonnested matching $M$ with $k$ edges. Since $|X|=k-1$ and the edges of $M$ have disjoint endpoints, at most $k-1$ of them can meet $X$. At least one edge of $M$ must therefore have both endpoints in $U$, because those are the only blue edges avoiding $X$.

Every edge from $X$ to $V\cup W$ has this edge inside it: the block order is $X<U<V<W$. Such an edge cannot also belong to the nonnested matching $M$. All edges of $M$ must consequently have their endpoints in $X\cup U$. But $|X\cup U|=2k-1$, whereas $M$ needs $2k$ distinct endpoints, a contradiction. In the ten-vertex example, the same argument confines a proposed three-edge blue matching to vertices $1,\ldots,5$.

\subsection{Red: every vertex of \texorpdfstring{$W$}{W} must be used}\label{sec:red}
Every red edge meets $W$, whose size is exactly $k$. A red matching with $k$ edges would therefore have to use one vertex of $W$ per edge and use all of $W$. This leaves two cases for the left endpoints, according to whether $v_1$ is selected. The increasing-partners lemma rules out both possibilities.

Indeed, suppose that $M$ is a red nonnested matching with $k$ edges. The endpoint count just described excludes every edge internal to $W$: one such edge would use two vertices of $W$, leaving too few for the other $k-1$ edges. Thus $M$ pairs $k$ distinct vertices of $U\cup\{v_1\}$ with all of $W$. All these possible left endpoints precede $W$.

If $v_1$ is not used, then all $k$ left endpoints lie in $U$, and hence every vertex of $U$ is used. Lemma~\ref{lem:partners} forces $u_iw_i$ for each $i$. In particular, it forces $u_1w_1$, which is green. This excludes the first case.

If $v_1$ is used, then it is the largest left endpoint, because $U<V$. Lemma~\ref{lem:partners} requires it to be paired with $w_k$. Its only red neighbor in $W$, however, is $w_2$. The two vertices are distinct since $k\ge3$, so this case is also impossible. This proves that red has no nonnested $k$-edge matching. Fig.~\ref{fig:red} illustrates both obstructions when $k=3$.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[font=\small,x=.85cm,y=1cm]
\begin{scope}
\node[anchor=west] at (0,2.0) {(a) All left endpoints are in \(U\)};
\draw[greenedge] (2,0) .. controls (2,2.0) and (7,2.0) .. (7,0);
\draw[rededge] (3,0) .. controls (3,1.65) and (8,1.65) .. (8,0);
\draw[rededge] (4,0) .. controls (4,1.3) and (9,1.3) .. (9,0);
\foreach \j in {1,...,10}{\node[vertex] at (\j-1,0) {};\node[below=4pt] at (\j-1,0) {\j};}
\blocklabels
\node[anchor=west,align=left] at (10.1,.65)
 {Increasing pairing:\\\(\edge38,\ \edge49,\ \edge5{10}\)\\[5pt]
 \(\edge38\) is green.};
\end{scope}
\begin{scope}[yshift=-3.9cm]
\node[anchor=west] at (0,2.0) {(b) The left endpoint \(v_1=6\) is used};
\draw[rededge] (3,0) .. controls (3,1.8) and (7,1.8) .. (7,0);
\draw[rededge] (4,0) .. controls (4,1.45) and (8,1.45) .. (8,0);
\draw[greenedge] (5,0) .. controls (5,1.1) and (9,1.1) .. (9,0);
\foreach \j in {1,...,10}{\node[vertex] at (\j-1,0) {};\node[below=4pt] at (\j-1,0) {\j};}
\blocklabels
\node[anchor=west,align=left] at (10.1,.65)
 {Largest pairs with largest:\\\(6\) must pair with \(10\).\\[5pt]
 \(\edge6{10}\) is green.\\The red neighbor of \(6\) is \(9\).};
\end{scope}
\end{tikzpicture}
\caption{The two red cases for \(k=3\). In (a), pairing all of \(U\) with all of \(W\) without nesting forces the green edge \(\edge38\). In (b), the left endpoints \(4,5,6\) illustrate a candidate using \(v_1=6\). Its required last partner is \(10\), and \(\edge6{10}\) is green; the only red edge from \(6\) is \(\edge69\). The same obstruction holds for every choice of two vertices from \(U\). Red edges are dashed and green edges are dash-dotted.}
\label{fig:red}
\end{figure}

\subsection{Green: one forced edge determines the rest}\label{sec:green}
All green edges except $u_1w_1$ meet the set $V$, which has only $k-1$ vertices. A green matching with $k$ edges must therefore include $u_1w_1$. We identify the green edges that can coexist with it, then apply the increasing-partners lemma to the remaining vertices.

Suppose that $M$ were a green nonnested matching with $k$ edges. The preceding count forces $u_1w_1\in M$. Every other green edge meets $V$, so consider the possible location of its other endpoint. An edge internal to $V$ is nested inside $u_1w_1$. An edge from $U$ to $V$ either shares the endpoint $u_1$ or is nested inside $u_1w_1$. An edge from $V$ to $w_1$ shares the endpoint $w_1$. None of these can belong to $M$.

The only remaining possibility is an edge from $V$ to $\{w_2,\ldots,w_k\}$. Both sets have $k-1$ vertices. To supply the other $k-1$ edges of $M$, the matching must use every vertex of both sets. Lemma~\ref{lem:partners} therefore forces
\[
v_1w_2,\ v_2w_3,\ \ldots,\ v_{k-1}w_k.
\]
The first of these edges is red, giving the required contradiction. This proves that green also avoids a nonnested $k$-edge matching, and completes the verification of the three-color construction.

Fig.~\ref{fig:green} makes the final step explicit for $k=3$. After choosing the green edge $38$, the other two edges of a proposed green nonnested matching must pair $\{6,7\}$ with $\{9,10\}$. There are just two ways to pair these sets. The increasing pairing uses the red edge $69$; the alternative uses only green edges but nests $79$ inside $\edge6{10}$. Thus Fig.~\ref{fig:green}(b) exhibits an ordinary monochromatic matching of the size guaranteed by the classical theorem, while the proof rules out every nonnested one. For larger $k$, the increasing-partners lemma gives the same obstruction without enumerating pairings.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[font=\small,x=.85cm,y=1cm]
\begin{scope}
\node[anchor=west] at (0,2.0) {(a) Nonnested, with two colors};
\draw[greenedge] (2,0) .. controls (2,1.85) and (7,1.85) .. (7,0);
\draw[rededge] (5,0) .. controls (5,1.25) and (8,1.25) .. (8,0);
\draw[greenedge] (6,0) .. controls (6,.95) and (9,.95) .. (9,0);
\foreach \j in {1,...,10}{\node[vertex] at (\j-1,0) {};\node[below=4pt] at (\j-1,0) {\j};}
\blocklabels
\node[anchor=west,align=left] at (10.1,.65)
 {\(\edge38,\ \edge69,\ \edge7{10}\)\\[5pt]
 The increasing pairing\\requires the red edge \(\edge69\).};
\end{scope}
\begin{scope}[yshift=-3.9cm]
\node[anchor=west] at (0,2.0) {(b) Monochromatic, with a nested pair};
\draw[greenedge] (2,0) .. controls (2,1.85) and (7,1.85) .. (7,0);
\draw[greenedge] (5,0) .. controls (5,1.85) and (9,1.85) .. (9,0);
\draw[greenedge] (6,0) .. controls (6,.60) and (8,.60) .. (8,0);
\foreach \j in {1,...,10}{\node[vertex] at (\j-1,0) {};\node[below=4pt] at (\j-1,0) {\j};}
\blocklabels
\node[anchor=west,align=left] at (10.1,.65)
 {\(\edge38,\ \edge6{10},\ \edge79\)\\[5pt]
 All three edges are green.\\\(\edge79\) lies inside \(\edge6{10}\).};
\end{scope}
\end{tikzpicture}
\caption{The two ways to pair \(\{6,7\}\) with \(\{9,10\}\) after selecting the forced edge \(\edge38\). The proof shows that these are the remaining endpoint sets for a proposed green nonnested matching. In (a), the increasing pairing is nonnested and uses two colors, since \(\edge69\) is red. In (b), all three edges are green, and \(\edge79\) is nested inside \(\edge6{10}\). This ordinary monochromatic matching illustrates the extra restriction that fails. Red edges are dashed and green edges are dash-dotted.}
\label{fig:green}
\end{figure}

\Needspace{12\baselineskip}
\section{Adding more colors}\label{sec:more-colors}
The three-color construction contains the entire order obstruction. To obtain any larger number of colors, we place additional blocks before it, giving each block its own new color. Every edge of a new color will meet a set of only $k-1$ vertices, which rules out a $k$-edge matching in that color even without an order restriction.

\begin{proof}[Proof of Theorem~\ref{thm:main}]
For $r=3$, Sections~\ref{sec:construction} and~\ref{sec:proof} give the required coloring on $4k-2$ vertices. For $r>3$, place $r-3$ new blocks before this graph, in the order
\[
D_1<\cdots<D_{r-3}<X<U<V<W,
\qquad |D_i|=k-1.
\]
Give each $D_i$ a distinct new color, called color $i$. If an edge has an endpoint in at least one of the blocks $D_i$, color it by the first such block in the order. This includes edges internal to a block and edges joining two different new blocks. Preserve the original blue, red and green coloring on $X\cup U\cup V\cup W$.

Every edge of color $i$ has an endpoint in $D_i$. Since a matching uses each vertex at most once, a matching in that color has at most $k-1$ edges. The original three colors occur only in the final $4k-2$ vertices, where Section~\ref{sec:proof} excludes a nonnested $k$-edge matching in each color. The enlarged coloring consequently avoids the target in all $r$ colors. Its number of vertices is
\[
(r-3)(k-1)+(4k-2)=(r-1)(k-1)+2k.
\]
A coloring avoiding the target at this order makes the least order that forces it strictly larger, proving Eq.~\eqref{eq:bound}.
\end{proof}

Fig.~\ref{fig:prefixes} shows one step of the extension. Repeating it $r-3$ times gives the construction just proved. A new color can have many edges, since its block is joined to all existing vertices, but its matchings are limited by the $k-1$ endpoints in that block. This is exactly the increase in the proposed threshold per added color.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[font=\small]
\node[draw,rounded corners,fill=gray!8,minimum width=2.0cm,minimum height=.85cm] (new) at (1.2,0) {\(D\)};
\node[draw,rounded corners,minimum width=6.7cm,minimum height=.85cm] (old) at (8.0,0) {existing counterexample};
\draw[-{Stealth[length=2mm]},line width=.85pt] (new.north)
 .. controls (1.2,1.9) and (7.2,1.9) .. (old.north);
\node[align=center] at (4.8,2.1)
 {edges from \(D\) to existing vertices\\receive the new color};
\node[below=7pt] at (new.south) {\(k-1\) new vertices};
\node[below=7pt] at (old.south) {all existing edge colors are preserved};
\draw[-{Stealth[length=2mm]},gray] (0,-1.45)--(11.4,-1.45);
\node[below=3pt] at (5.7,-1.45) {vertex order};
\end{tikzpicture}
\caption{One step in adding colors. A new block \(D\) of \(k-1\) vertices is placed before the existing coloring. Every edge with an endpoint in \(D\), including edges inside \(D\), receives the new color. A matching in that color has at most \(k-1\) edges. Repeating this step \(r-3\) times extends the three-color counterexample to \(r\) colors.}
\label{fig:prefixes}
\end{figure}

\section{Conclusion}\label{sec:conclusion}
The construction shows that avoiding nesting changes the multicolor matching Ramsey problem for every $r,k\ge3$. At the exact order that forces an ordinary monochromatic $k$-edge matching, our coloring still avoids a nonnested one. Its three-color core isolates the reason: disjointness forces whole sets of vertices to be used, and nonnesting then forces an increasing pairing that encounters an edge of another color. The additional blocks extend this obstruction to every larger number of colors.

The resulting lower bound refutes the proposed equality uniformly in both parameters. Determining the exact value of $\Rnn^{(r)}(k)$ remains a separate problem, beginning with the three-color, three-edge case for which our construction gives $\Rnn^{(3)}(3)\ge11$. More generally, it is natural to ask how large the difference from the ordinary threshold can be. The two-color conjecture also remains beyond this construction: the argument uses the third color to place the two obstructions in different classes.

\begin{thebibliography}{9}
\bibitem{BFT2025}
J. Barát, A. Freschi and G. Tóth,
\emph{Matchings avoiding ordered patterns}.
Preprint, arXiv:2512.15461v2 (2025).
\url{https://arxiv.org/abs/2512.15461}.

\bibitem{BGT2024}
J. Barát, A. Gyárfás and G. Tóth,
\emph{Monochromatic spanning trees and matchings in ordered complete graphs}.
Journal of Graph Theory \textbf{105}(4) (2024), 523--541.
\url{https://doi.org/10.1002/jgt.23058}.

\bibitem{Castro2026}
P. M. M. de Castro,
\emph{Minimum blockers and extremal graphs for nonnested matchings}.
Preprint, arXiv:2609.14484v2 (2026).
\url{https://arxiv.org/abs/2609.14484v2}.

\bibitem{CL1975}
E. J. Cockayne and P. J. Lorimer,
\emph{The Ramsey number for stripes}.
Journal of the Australian Mathematical Society (Series A) \textbf{19}(2) (1975), 252--256.
\url{https://doi.org/10.1017/S1446788700029554}.
\end{thebibliography}
\end{document}