% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need
\usepackage{enumerate}

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf A note on a Ramsey-type problem for sequences}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{
Andrzej Dudek\thanks{Supported in part by Simons Foundation Grant \#244712 and by a grant from the Faculty Research and Creative Activities Award (FRACAA), Western Michigan University.}\\
\small Department of Mathematics\\[-0.8ex]
\small Western Michigan University\\[-0.8ex] 
\small Kalamazoo, MI, USA\\
\small\tt andrzej.dudek@wmich.edu\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{March 24, 2014}{XX}\\
\small Mathematics Subject Classifications: 05A05, 05D10}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
Two sequences $\{x_i\}_{i=1}^{t}$ and $\{y_i\}_{i=1}^t$ of distinct integers are \emph{similar} if their entries are order-isomorphic. Let $f(r,X)$ be the length of the shortest sequence~$Y$ such that any $r$-coloring of the entries of $Y$ yields a monochromatic subsequence that is also similar to $X$. In this note we show that for any fixed non-monotone sequence $X$, $f(r,X)=\Theta(r^2)$, otherwise, for a monotone $X$, $f(r,X)=\Theta(r)$.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Permutations; Sequences; Ramsey problems
\end{abstract}

\section{Introduction}		

We consider the following Ramsey-type question.
We say that two sequences $\{x_i\}_{i=1}^{t}$ and $\{y_i\}_{i=1}^t$ of distinct integers are \emph{similar} if their entries are order-isomorphic, \textit{i.e.}, $x_i<x_j$ if and only if $y_i<y_j$ for all $1\le i<j\le t$. 
For a given sequence~$X$ and a positive integer~$r$ a sequence~$Y$ is \textit{Ramsey} for $X$ if for every $r$-coloring of the entries of~$Y$ there is a subsequence of~$Y$ which is both monochromatic and similar to $X$. Denote by $f(r,X)$ the length of the shortest sequence~$Y$ that is Ramsey for $X$, \textit{i.e.},
\[
f(r,X) = \min_{Y} |Y|,
\] 
where the minimum is taken over all Ramsey sequences for $X$.
Moreover, let
\[
f(r,t) = \max_{X} f(r,X),
\]
where the maximum is taken over all sequences $X$ with $|X|=t$. 

Frankl, R\"odl and the author~\cite{DFR} asked to determine for a fixed $t$ the order of magnitude of $f(r,t)$ as a function of~$r$. Here we show that $f(r,t)=\Theta(r^2)$. Indeed, we give a stronger result identifying the asymptotic behavior of $f(r,X)$ for every $X$.

\begin{samepage}
\begin{theorem}\label{thm:main}\
\begin{enumerate}[(i)]

\item\label{thm:i} Let $X$ be a monotone sequence, \textit{i.e.}, $X$ is similar to $(1,2,\dots,|X|)$ or $(|X|,\dots, 2,1)$. Then
\[
f(r,X) = \Theta(r).
\]
\item\label{thm:ii} Let $X$ be a non-monotone sequence. Then
\[
f(r,X) = \Theta(r^2).
\]
\end{enumerate}
(The hidden constants depend only on $X$.)
\end{theorem}
\end{samepage}

\noindent
It is also worth mentioning that the proof shows that for each $t$ there is a (universal) sequence $Y$ of length $O(r^2)$ which is Ramsey for every sequence $X$ of length $t$ and any number of colors~$r$. Furthermore, the entries of such $Y$ colored by the majority color contain a subsequence similar to~$X$. 

\section{Proof of Theorem~\ref{thm:main}}

For \eqref{thm:i} it is enough to observe that $(1,2,\dots,r|X|)$ is Ramsey for $(1,2,\dots,|X|)$, and similarly, $(r|X|,\dots,2,1)$ is Ramsey for $(|X|,\dots,2,1)$.

Now we prove (ii). First we show the lower bound. The proof is based on the Erd\H{o}s-Szekeres~\cite{ES} theorem which says that any sequence $S$ of length~$m$ contains a monotone subsequence of length $\lceil \sqrt{m}\, \rceil$. It is not difficult to observe (see, \textit{e.g.}, \cite{BF,MW}) that the repetitive application of this result shows that $S$ can be partitioned into at most $\lfloor 2\sqrt{m}\rfloor$ monotone subsequences. For the sake of completeness we prove a similar result here.

Let $X$ be any sequence of length~$t$ which is non-monotone. Assume that $Y$ is Ramsey for $X$. We show that $|Y| > \left(\frac{r}{2}\right)^2$. Suppose not, \textit{i.e.}, $|Y| \le \left(\frac{r}{2}\right)^2$.  We will repeatedly apply the Erd\H{o}s-Szekeres theorem. We start with $Y$ of length $a_0 = |Y|\le \left(\frac{r}{2}\right)^2$ and find a monotone subsequence of length $\lceil \sqrt{a_0}\, \rceil$. Then we remove it from $Y$ obtaining a sequence of length $a_1 = a_0 - \lceil \sqrt{a_0}\, \rceil$ and repeat the whole process again. After the $i$-th step the length of the remaining sequence is given by  the recursive formula
\[
a_{i+1} = a_i - \lceil \sqrt{a_i}\, \rceil.
\]
Let $N$ be the least integer for which $a_N = 0$. We show that $N \le r$. First observe that for each $i<N$, we have $a_{i} \ge 1$ and
\[
a_{i+1} = a_i - \lceil \sqrt{a_i}\, \rceil \le a_i - \sqrt{a_i} \le \left( \sqrt{a_i} - \frac{1}{2} \right)^2
\]
implying
\[
\sqrt{a_{i+1}} \le \sqrt{a_i} - \frac{1}{2},
\]
and consequently,
\[
\sum_{i=0}^{N-1} \sqrt{a_{i+1}} \le \sum_{i=0}^{N-1} \left( \sqrt{a_i} - \frac{1}{2} \right).
\]
Thus,
\[
\sqrt{a_N}  \le \sqrt{a_0} - \frac{N}{2} \le \frac{r}{2} - \frac{N}{2}
\]
and after at most $r$ steps we end up with an empty sequence. Summarizing, we just found a decomposition of $Y$ into at most $r$ monotone subsequences. Now we color each monotone subsequence with a different color. Since $X$ is non-monotone, there is no monochromatic subsequence similar to $X$, a contradiction.

Next we show the upper bound. First we need some notation. Let $A$ and $P$ be 0-1 matrices. We say that $A$ \emph{contains} the $t \times t$ matrix $P = (p_{i,j})$ if there exists a $t \times t$ submatrix $B = (b_{i,j})$ of $A$ with $b_{i,j} = 1$ whenever $p_{i,j} = 1$. Otherwise we say that $A$ \emph{avoids}~$P$. Notice that we can delete rows and columns of $A$ to obtain the submatrix $B$ but we cannot permute the remaining rows and columns. Given a permutation $\pi$ of $t$ elements its \emph{permutation matrix} is the $t\times t$ matrix $P_\pi=(p_{i,j})$ whose entries are all 0 except that in column $i$, the entry $\pi(i)$ equals~1, \textit{i.e.}, the only non-zero entries are $p_{\pi(i),i}$. 

We will use the following result conjectured by F\"uredi and Hajnal~\cite{FH} and proved by Marcus and Tardos~\cite{MT}. 
Let $P$ be a permutation matrix. Denote by $g(P,m)$ the maximum number of ones in a 0-1 matrix of size $m\times m$ avoiding $P$. Then, due to Marcus and Tardos~\cite{MT}, there exists a positive constant $c=c(P)$ such that
\begin{equation}\label{eq:MT}
g(P,m) \le c m.
\end{equation}

Let $X$ be a given sequence of $t$ different integers. (Here non-monotonicity is not required.) Without loss of generality we may assume that $X$ is a permutation of $\{1,\dots,t\}$. Let $P_X$ be the corresponding permutation matrix and let $c = c(P_X)$ be as in \eqref{eq:MT} yielding
\begin{equation}\label{eq:MT2}
g(P_X,m) \le c m.
\end{equation}
Set
\begin{equation}\label{eq:m}
m = \lfloor c r \rfloor + 1.
\end{equation}
Now we define a sequence $Y$ which is a permutation of $\{1,\dots,m^2\}$. Let 
\begin{equation*}
\setlength{\arraycolsep}{-7pt}
\begin{array}{r l l l l l l}
Y =  (\qquad &1, & m+1, & 2m+1, & 3m+1, &\quad\dots, &(m-1)m+1,\\
&\quad2, &\quad m+2, &\quad 2m+2, &\quad 3m+2, &\quad\quad \dots, &\quad (m-1)m+2,\\
&\quad\quad3, &\quad\quad m+3, &\quad\quad 2m+3, &\quad\quad 3m+3, &\quad\quad\quad \dots, &\quad\quad (m-1)m+3,\\
&\quad\quad\quad {\dots} &\quad\quad\quad \dots &\quad\quad\quad \dots &\quad\quad\quad \dots &\quad\quad\quad\quad \dots &\quad\quad\quad \dots\\
&\quad\quad\quad\quad m, &\quad\quad\quad\quad 2m, &\quad\quad\quad\quad  3m, &\quad\quad\quad\quad 4m, &\quad\quad\quad\quad\quad \dots, &\quad\quad\quad\quad m^2\ \,).\\
\end{array}
\end{equation*}
Clearly, $|Y| = \Theta(r^2)$. It remains to show that $Y$ is Ramsey for $X$.

Let $A_Y$ be the following matrix of size $m \times m$ based on $Y$. The first $m$ elements of $Y$ form the first column in $A_Y$ in reverse order. The next $m$ elements of $Y$ form the second column in $A_Y$ in reverse order, etc. Thus,
\[
A_Y = 
\left(
\begin{array}{r r r r r}
(m-1)m+1 & (m-1)m+2 & (m-1)m+3 & \dots & m^2\\
(m-2)m+1 & (m-2)m+2 & (m-2)m+3 & \dots & (m-1)m\\
(m-3)m+1 & (m-3)m+2 & (m-3)m+3 & \dots & (m-2)m\\
\vdots & \vdots &\vdots & \vdots & \vdots\\
m+1 & m+2 & m+3 & \dots & 2m\\
1 & 2 & 3 & \dots & m\\
\end{array}
\right).
\]
Now let us arbitrarily color the elements of $Y$ with $r$ colors. We need to show that there is a monochromatic subsequence in $Y$ that is similar to $X$.

Clearly, every coloring of $Y$ uniquely induces a coloring of the entries of $A_Y$.
Choose the most frequent color, say red, and let $A=(a_{ij})$ be the 0-1 matrix of size $m\times m$ whose entries correspond to it. That means $a_{ij}=1$ if and only if the $ij$-entry in $A_Y$ is colored red.
The key observation is the following: if $A$ does not avoid $P_X$, then $Y$ contains a monochromatic subsequence similar to~$X$.
By \eqref{eq:m} and \eqref{eq:MT2}, we get that the  number of ones in $A$ is at least
\[
\frac{m^2}{r} > c m \ge g(P_X,m).
\]
Hence, $A$ does not avoid $P_X$. This completes the proof of \eqref{thm:ii}.


\section{Concluding remarks}

It may be of some interest to study $f(r,t)$ in more detail. Theorem~\ref{thm:main} implies that
\[
c_1 r^2 \le f(r,t) \le c_2 r^2,
\]
for some positive constants $c_1 = c_1(t)$ and $c_2 = c_2(t)$. For the sake of simplicity we did not attempt to optimize theses constants. The proof gives $c_1 = \frac{1}{4}$ and this constant can be improved to $\frac{1}{2}$ by using a result of Brandst\"adt and Kratsch~\cite{BK}. On the other hand, $c_2$ is entirely based on the result of Marcus and Tardos~\cite{MT} and so is exponential in $t$ (see also a result of Fox~\cite{F}).

It would be also interesting to consider a similar question and study the growth of $f(r,t)$ for a fixed $r$ and large $t$.

For only two colors it is not difficult to see that
\begin{equation}\label{eq:f2n}
f(2,t)  = \Theta(t^2).
\end{equation}
Indeed, let $X=\{x_i\}_{i=1}^{t}$ be any sequence. Without loss of generality we may assume that $X$ is a permutation of $\{0,\dots,t-1\}$. 
For the upper bound let us define $Y=Y^{(1)}Y^{(2)}\dots Y^{(t)}$, where 
$Y^{(i)}=\left(t x_i+x_1,\ t x_i+x_2,\ \dots,\ t x_i+x_t\right)$
for $1\le i \le t$. Now let us arbitrarily color the entries of $Y$ with two colors. Since each $Y^{(i)}$ is similar to $X$, we may assume that there is no monochromatic $Y^{(i)}$. Thus, there is a monochromatic subsequence $(y_1,y_2,\dots,y_t)$ such that $y_i\in Y^{(i)}$ for $1\le i\le t$. It is easy to see that such $(y_1,y_2,\dots,y_t)$ is similar to $X$. Consequently, $Y$ is Ramsey for $X$ and $f(2,X)\le |Y| = t^2$. 

To see the lower bound of \eqref{eq:f2n} consider 
$X=\left(1,2,\dots,\lfloor\frac{t}{2}\rfloor,t,t-1,\dots,\lfloor\frac{t}{2}\rfloor+1\right)$. Let~$Y$ be any Ramsey sequence for $X$. Clearly, $Y$ must contain many subsequences similar to $Z = \left(1,2,\dots,\lfloor\frac{t}{2}\right\rfloor)$. Starting with $Y_0=Y$, we find a subsequence similar to $Z$ and remove it obtaining $Y_1$ (of length $|Y|-\lfloor \frac{t}{2}\rfloor$). 
We repeatedly continue the process of removing subsequences similar to $Z$ until we cannot longer find a subsequence similar to $Z$. Let $m$ denote the number of steps and $Y_m$ be the remaining sequence. Now we color $Y_m$ blue and $Y\setminus Y_m$ red. Since $Y_m$ contains no subsequence similar to $Z$, there is no blue subsequence similar to $X$ in $Y$. Therefore, there must be a red subsequence in $Y$ which is similar to~$X$. In particular, there is a red subsequence similar to $X\setminus Z$. Since $Y\setminus Y_m$ is a disjoint union of $m$ (increasing) sequences similar to $Z$, each of these $m$ subsequences can contain at most one element of the (decreasing) sequence $X\setminus Z$. Thus, $m\ge t - \lfloor \frac{t}{2} \rfloor =  \lceil \frac{t}{2} \rceil$ and so
\[
|Y| \ge |Y\setminus Y_m| \ge m \left\lfloor \frac{t}{2} \right\rfloor \ge \left\lceil \frac{t}{2} \right\rceil\left\lfloor \frac{t}{2} \right\rfloor \ge \frac{t^2-1}{4}.
\]

By recursively extending the above construction one can get an upper bound for any $r\ge 2$ and show that 
\begin{equation}\label{eq:frn}
f(r,t)\le t^r.
\end{equation}
For example, for $r=3$ and a permutation $X=\{x_i\}_{i=1}^{t}$ of $\{0,\dots,t-1\}$ it is enough to take $Y=Y^{(1)}Y^{(2)}\dots Y^{(t)}$, where
\begin{equation*}
\setlength{\arraycolsep}{-3pt}
\begin{array}{r l l l l }
Y^{(i)}=(\quad &t^{2}x_i+t x_1+x_1, & t^{2}x_i+t x_1+x_2, &\quad \dots, & t^2x_i+t x_1+x_t,\\
&\quad t^{2}x_i+t x_2+x_1,&\quad t^{2}x_i+t x_2+x_2, &\quad\quad \dots,& \quad t^2x_i+t x_2+x_t,\\
&\quad\quad {\dots} &\quad\quad \dots &\quad\quad\quad \dots &\quad\quad \dots\\
&\quad\quad\quad t^{2}x_i+t x_t+x_1, &\quad\quad\quad t^{2}x_i+t x_t+x_2,& \quad\quad\quad\quad \dots,&\quad\quad\quad t^2x_i+t x_t+x_t\ ),\\
\end{array}
\end{equation*}
for $1\le i \le t$. Observe that $Y$ is Ramsey for $X$. Hence, $f(3,X)\le |Y| = t^3$. 

The lower bound in \eqref{eq:f2n} and the upper bound in \eqref{eq:frn} imply that for a fixed $r\ge 2$
\[
\Omega(t^2) = f(r,t) = O(t^r).
\]
Determining the right order of magnitude of $f(r,t)$ as a function of $t$ remains open.~\footnote{Very recently, together with Klimo\v{s}ov\'a and Kr\'al' we showed that $f(r,t) = \Omega\big{(}\frac{t^{{(r+1)}/{2}}} {\textrm{polylog}(t)}\big{)}$. The proof uses some ideas from \cite{F}.}

\subsection*{Acknowledgements}
The author would like to thank to Boris Bukh for working on this problem. He was originally intended as a coauthor but later declined this. The author also would like to thank to the referee for her/his valuable comments and suggestions, and in particular for pointing out reference~\cite{BF}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{BF} R.~Bar-Yehuda and S.~Fogel.
\newblock Partitioning a sequence into few monotone subsequences.
\newblock {\em  Acta Inform.}, 
35(5):421--440, 1998.

\bibitem{BK} A.~Brandst\"adt and D.~Kratsch.
\newblock On partitions of permutations into increasing and decreasing subsequences.
\newblock {\em Elektron. Informationsverarb. Kybernet.},
22(5-6):263--273, 1986.

\bibitem{DFR} A.~Dudek, P.~Frankl and V.~R\"odl.
\newblock A note on universal and canonically coloured sequences. 
\newblock {\em Combin. Probab. Comput.},
18(5):683--689, 2009.

\bibitem{ES} P.~Erd\H{o}s and G.~Szekeres.
\newblock A combinatorial problem in geometry.
\newblock {\em Compos. Math.}, 
2:463--470, 1935. 

\bibitem{F} J.~Fox.
\newblock Stanley-Wilf limits are typically exponential. \arxiv{1310.8378}.

\bibitem{FH} Z.~F\"uredi and P.~Hajnal.
\newblock Davenport-Schinzel theory of matrices.
\newblock {\em Discrete Math.}, 
103(3):233--251, 1992. 

\bibitem{MT} A.~Marcus and G.~Tardos.
\newblock Excluded permutation matrices and the Stanley-Wilf conjecture.
\newblock {\em J. Combin. Theory Ser. A},
107(1):153--160, 2004.

\bibitem{MW} J.~Matou\v{s}ek and E.~Welzl.
\newblock Good splitters for counting points in triangles. 
\newblock {\em J. Algorithms},
13(2):307--319, 1992.

\end{thebibliography}

\end{document}