% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.35}{25(3)}{2018}

% Please remove all commands that change parameters such as
%    margins or page sizes.

% Packages amssymb and amsthm are already loaded. 
% We recommend these AMS packages:
\usepackage{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}

% Theorem-like environments that are declared in the style file are:
% theorem, lemma, corollary, proposition, fact, observation, claim,
% definition, example, conjecture, open, problem, question, remark, note

%%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{Jun 22, 2018}{Aug 8, 2018}{Aug 24, 2018}

% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{05D10, 05C80}

% Uncomment exactly one of the following copyright statements.  Alternatively,
% you can write your own copyright statement subject to the approval of the journal.
% See https://creativecommons.org/licenses/ for a full explanation of the 
% Creative Commons licenses.
%
% We strongly recommend CC BY-ND or CC BY. Both these licenses allow others
% to freely distribute your work while giving credit to you. The difference between
% them is that CC BY-ND only allows distribution unchanged and in whole, while
% CC BY also allows remixing, tweaking and building upon your work.  
%
%    One author:
%\Copyright{The author.}
%\Copyright{The author. Released under the CC BY license (International 4.0).}
%\Copyright{The author. Released under the CC BY-ND license (International 4.0).}
%    More than one author:
%\Copyright{The authors.}
%\Copyright{The authors. Released under the CC BY license (International 4.0).}
\Copyright{  The authors. Released under the CC BY-ND license (International 4.0).}

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

\newcommand{\ram}[1]{\hat{R}({#1})}
\newcommand{\G}{{\mathcal{G}}}
\newcommand{\bin}{{\mathrm{Bin}}}
\newcommand{\E}{\mathbb E}


% If needed, include a line break (\\) at an appropriate place in the title.
\title{Note on the multicolour size-Ramsey \\ number for paths}

% Input author, affiliation, address and support information as follows;
% The address should include the country, but does not have to include
%    the street address. Give at least one email address.

\author{Andrzej Dudek\thanks{Supported in part by Simons Foundation Grant \#522400.}\\
\small Department of Mathematics\\[-0.8ex]
\small Western Michigan University\\[-0.8ex] 
\small Kalamazoo, MI, U.S.A.\\
\small\tt andrzej.dudek@wmich.edu\\
\and
Pawe\l{} Pra\l{}at\thanks{Supported in part by NSERC.}\\
\small Department of Mathematics\\[-0.8ex]
\small Ryerson University\\[-0.8ex]
\small Toronto, ON, Canada\\
\small\tt pralat@ryerson.ca}

\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 may be distributed without the rest of the
% paper so it must be entirely self-contained.  Try to include all words
% and phrases that someone might search for when looking for your paper.

\begin{abstract}
The size-Ramsey number $\ram{F,r}$ of a graph $F$ is the smallest integer $m$ such that there exists a graph $G$ on $m$ edges with the property that any colouring of the edges of $G$ with $r$ colours yields a monochromatic copy of $F$. In this short note, we give an alternative proof of the recent result of Krivelevich that $\ram{P_n,r} = O((\log r)r^2 n)$. This upper bound is nearly optimal, since it is also known that $\ram{P_n,r} = \Omega(r^2 n)$.
\end{abstract}

\section{Introduction}
Following standard notation, we write $G\to (F)_r$ if any $r$-edge-colouring of $G$ (that is, any colouring of the edges of $G$ with $r$ colours) yields a monochromatic copy of $F$. We define the \emph{size-Ramsey number} of $F$ as $\ram{F,r} = \min \{ |E(G)| : G \to (F)_r \}$; that is, $\ram{F,r}$ is the smallest integer $m$ such that there exists a graph $G$ on $m$ edges such that $G \to (F)_r$. For two colours (that is, for $r=2$) the size-Ramsey number was first studied by Erd\H os, Faudree, Rousseau and Schelp~\cite{EFRS1978}.

In this note, we are concerned with the size-Ramsey number of the path $P_n$ on $n$ vertices. It is obvious that $\ram{P_n,2} = \Omega(n)$ and it is easy to see that $\ram{P_n,2} = O(n^2)$; for example, $K_{2n}\to (P_n)_2$. 
The exact behaviour of $\ram{P_n,2}$ was not known for a long time. In fact, Erd\H{o}s~\cite{E81} offered \$100 for a proof or disproof that $\ram{P_n,2} / n \to \infty$ and $\ram{P_n,2} / n^2 \to 0$. This problem was solved by Beck~\cite{B83} in 1983 who, quite surprisingly, showed that $\ram{P_n,2} < 900 n$. (Each time we refer to inequality such as this one, we mean that the inequality holds for sufficiently large $n$.) A variant of his proof, provided by Bollob\'{a}s~\cite{B01}, gives $\ram{P_n,2} < 720 n$. Recently, the authors of this paper~\cite{DP15} used a different and more elementary argument that shows that $\ram{P_n,2} < 137 n$. The argument was subsequently tuned by Letzter~\cite{L15} who showed that $\ram{P_n,2} < 91 n$, and then further refined by the authors of this paper~\cite{DP2017} who showed that $\ram{P_n,2} \le 74n$.
On the other hand, the first nontrivial lower bound was provided by Beck~\cite{B90} and his result was subsequently improved by Bollob\'as~\cite{B86} who showed that $\ram{P_n,2} \ge (1+\sqrt{2}) n - O(1)$. The strongest known lower bound, $\ram{P_n,2} \ge 5n/2 - O(1)$, was proved in~\cite{DP2017}.

Let us now move to the multicolour version of this graph parameter. It was proved in~\cite{DP2017} that $\frac{(r+3)r}{4}n-O(r^2) \le \ram{P_n,r} \le 33 r 4^r n$. It follows that $\ram{P_n,r}$ is linear for any fixed value of $r$ but the two bounds are quite apart from each other in terms of their dependence on $r$. Subsequently, Krivelevich~\cite{K2016} showed that in fact the dependence on $r$ is (nearly) quadratic; that is, $\ram{P_n,r} = r^{2+o_r(1)}n$. Furthermore, for $r\ge 6$ he also improved the lower bound and showed that $\ram{P_n,r} \ge (r-2)^2 n + O(\sqrt{n})$. Here is the precise statement of his upper bound: 
\begin{theorem}[\cite{K2016}]
For any $C>5$, $r\ge 2$, and all sufficiently large $n$ we have
\[
\ram{P_n,r} < 400^5 C r^{2+\frac{1}{C-4}}n.
\]
\end{theorem}
\noindent
It is straightforward to see that $C=C(r)$ that minimizes the upper bound in this theorem is of order $\log r$. As a result we get that $\ram{P_n,r} = O((\log r)r^2 n)$. In this note, we give an alternative proof of this fact.
\begin{theorem}\label{thm:main}
For any integer $r\ge 2$ and all sufficiently large $n$ we have
\[
\ram{P_n,r} < 600 (\log r) r^2 n.
\]
\end{theorem}
\noindent
It will follow from the proof that the constant 600 is not optimal. Since we believe that the factor $\log r$ is not necessary, we do not attempt to optimize it.

\section{Proof}\label{sec:proof}

Before we move to the proof of Theorem~\ref{thm:main}, we need one, straightforward, auxiliary result.
\begin{proposition}\label{prop:G}
For any integer $r\ge 2$ there exists an integer $N=N(r)$ such that the following holds. For any integer $n \ge N$, there exists a graph $G=(V,E)$ such that 
\begin{itemize}
\item [(i)] $|V| = 7rn$, 
\item [(ii)] $500 (\log r) r^2 n < |E| < 600 (\log r) r^2 n$, and 
\item [(iii)] for every two disjoint sets $S,T \subseteq V$, $|S|=|T|=n$, the number of edges induced by $S\cup T$ with at least one endpoint in $S$ is at most $70(\log r)n$.
\end{itemize}
\end{proposition}

\begin{proof}
The proof is an easy application of random graphs.
Recall that the \emph{binomial random graph} $\G(n,p)$ is a distribution over the class of graphs with vertex set $[n]$ in which every pair $\{i,j\} \in \binom{[n]}{2}$ appears independently as an edge in $G$ with probability~$p$, which may (and usually does) tend to zero as $n$ tends to infinity. Furthermore,  
we say that events $A_n$ in a probability space hold \emph{asymptotically almost surely} (or \emph{a.a.s.}), if the probability that $A_n$ holds tends to $1$ as $n$ goes to infinity. 

Fix any integer $r\ge 2$. It suffices to show that the random graph $G\in \G(7rn, p)$ with $p = 22(\log r)/n$ a.a.s.\ satisfies properties (ii) and (iii). (Property (i) trivially holds.)  Indeed, if this is the case, then there exists an integer $N=N(r)$ such that the desired properties hold with probability at least $1/2$ for $G\in \G(7rn, p)$ for all $n \ge N$. This implies that for each $n \ge N$, there exists at least one graph with these properties. 

\medskip \emph{Property (iii)}: Fix any two disjoint subsets $S, T \subseteq V$, both of cardinality $n$. Let $X_{S,T}$ be the random variable counting the number of edges induced by $S\cup T$ with at least one endpoint in $S$. Clearly, $X_{S,T}$ has the binomial distribution $\bin\big{(} |S|\cdot |T| + \binom{|S|}{2}, p \big{)}$ with $\E(X_{S,T}) = (3/2+o(1)) n^2p = (33+o(1)) (\log r)n$. It follows from Chernoff's bound (see, for example, Corollary 21.7 in~\cite{FK16}) that 
\[
\Pr(X_{S,T}\hspace{-1pt}\ge 70(\log r)n) \le \hspace{-0.3pt}\Pr(X_{S,T} \hspace{-1pt}\ge 2 \E(X_{S,T})) \le \exp(-\E(X_{S,T})/3) \le \exp(-10.9(\log r)n).
\]
Thus, the probability that there exist $S$ and $T$ such that $X_{S,T} \ge 70(\log r)n$ is, by the union bound, at most
\begin{eqnarray*}
\binom{7rn}{n}^2 \exp(-10.9(\log r) n) &\le& (7er)^{2n} \exp(-10.9(\log r) n) \\
&\le& \exp \left( n \Big( 2\log(7e r) - 10.9 \log r \Big) \right) = o(1),
\end{eqnarray*}
since $(7e r)^2 < r^{10.9}$ for any $r\ge 2$. Property (iii) holds a.a.s.

\medskip \emph{Property (ii)}: This property is straightforward to prove. Note that $|E|$ is distributed as $\bin\big{(} \binom{7rn}{2}, p \big{)}$ with $\E(|E|) = (539+o(1)) (\log r) r^2 n$. It follows immediately from Chernoff's bound that property (ii) holds a.a.s. The proof of the proposition is finished. 
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
The proof is based on the depth first search algorithm (DFS), applied several times, and it is a variant of the previous approach taken in~\cite{DP2017} where it was proved that $ \ram{P_n,r} \le 33 r 4^r n$. Ben-Eliezer, Krivelevich and Sudakov~\cite{BKS2012} were the first to successfully apply the DFS algorithm to a Ramsey-type problem.

Fix $r\ge 2$ and suppose that $n$ is sufficiently large so that Proposition~\ref{prop:G} can be applied. Let $G=(V,E)$ be a graph satisfying properties (i)--(iii) from Proposition~\ref{prop:G}. We will show that $G\to (P_n)_r$ which implies the desired upper bound as $|E| < 600 (\log r) r^2 n$ by property (ii). Consider any $r$-colouring of the edges of $G$. By an averaging argument, there is a colour (say blue) such that the number of blue edges is at least $|E(G)|/r$. For a contradiction, suppose that there is no monochromatic copy of $P_n$; in particular, there is no blue copy of~$P_n$. 

From now on, we restrict ourselves to the subgraph of $G$ induced by blue edges, denoted $G_1 = (V_1=V, E_1 \subseteq E)$. We perform the following algorithm on $G_1$ to construct a path $P$. Let $v_1$ be an arbitrary vertex of $G_1$, let $P=(v_1)$, $U = V \setminus \{v_1\}$, and $W = \emptyset$. If there exists an edge from $v_1$ to some vertex in $U$ (say from $v_1$ to $v_2$), we extend the path as $P=(v_1,v_2)$ and remove $v_2$ from $U$. We continue extending the path $P$ this way for as long as possible. Since there is no $P_n$ in the blue graph, we must reach a point of the process in which $P$ cannot be extended, that is, there is a path from $v_1$ to $v_k$ ($k < n$) and there is no edge from $v_k$ to $U$ (including the case when $U$ is empty). This time, $v_k$ is moved to $W$ and we try to continue extending the path from $v_{k-1}$, reaching another critical point in which another vertex will be moved to $W$, etc. If $P$ is reduced to a single vertex $v_1$ and no edge to $U$ is found, we move $v_1$ to $W$ and simply re-start the process from another vertex from $U$, again arbitrarily chosen.

Observe that during this algorithm there is never an edge between $U$ and $W$. Moreover, in each step of the process, the size of $U$ decreases by 1 or the size of $W$ increases by 1. The algorithm ends when $U$ becomes empty and all vertices from $P$ are moved to $W$. However, we will finish it prematurely, distinguishing $7r$ phases; phase $i$ starts with graph $G_i=(V_i,E_i)$ and ends when for the first time $|W| = n$. Before we move to the next phase, we set $S_i = W$, $T_i = V(P)$, and $F_i$ to be all edges incident to $W$. Then, we set $V_{i+1} = V_i \setminus W$ and $G_{i+1} = G_i [V_{i+1}]$, the graph induced by $V_{i+1}$ (in other words, $G_{i+1}$ is formed from $G_i$ by removing vertices from $W$ together with $F_i$, all edges incident with them). Phase $i$ ends now and we move to phase $i+1$ where we run the algorithm on $G_{i+1}$. 

We make a few important observations. Note that, by property (i), $|V|=|V_1|=7rn$ so the last phase, phase $7r$, finishes with $U=\emptyset$ and $T_{7r}=\emptyset$. As a result, family $(F_i : 1 \le i \le 7r)$ is a partition of $E_1$. By construction, $|S_i| = n$ for all $i$ and, since there is no path on $n$ vertices in $G_1$ (and so also in any $G_i$), $|T_i| < n$ for all $i$.  Hence, $|F_i| < 70(\log r)n$ by property (iii). Putting these things together and using property (ii) in the very last inequality, we get the desired contradiction:
\begin{eqnarray*}
|E|/r \le  |E_1| = |F_1| + |F_2| + \dots + |F_{7r}| \le 7r \cdot 70(\log r)n < 500 (\log r) r n < |E|/r.
\end{eqnarray*}
The proof is finished.
\end{proof} 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% You do not have to use the same format for your references, but 
%    include everything in this file.  Don't use natbib please.
% If you use BibTeX to create a bibliography, copy the .bbl file into here.

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{B83}
J.~Beck, \emph{On size {R}amsey number of paths, trees, and circuits. {I}}, J.
  Graph Theory \textbf{7} (1983), no.~1, 115--129.

\bibitem{B90}
\bysame, \emph{On size {R}amsey number of paths, trees and circuits. {II}},
  Mathematics of {R}amsey theory, Algorithms Combin., vol.~5, Springer, Berlin,
  1990, pp.~34--45.

\bibitem{BKS2012}
I.~Ben-Eliezer, M.~Krivelevich, and B.~Sudakov, \emph{The size {R}amsey number
  of a directed path}, J. Combin. Theory Ser. B \textbf{102} (2012), no.~3,
  743--755.

\bibitem{B86}
B.~Bollob{\'a}s, \emph{Extremal graph theory with emphasis on probabilistic
  methods}, CBMS Regional Conference Series in Mathematics, vol.~62, Published
  for the Conference Board of the Mathematical Sciences, Washington, DC; by the
  American Mathematical Society, Providence, RI, 1986.

\bibitem{B01}
\bysame, \emph{Random graphs}, second ed., Cambridge Studies in Advanced
  Mathematics, vol.~73, Cambridge University Press, Cambridge, 2001.

\bibitem{DP15}
A.~Dudek and P.~Pra{\l}at, \emph{An alternative proof of the linearity of the
  size-{R}amsey number of paths}, Combin. Probab. Comput. \textbf{24} (2015),
  no.~3, 551--555.

\bibitem{DP2017}
\bysame, \emph{On some multicolor {R}amsey properties of random graphs}, SIAM
  J. Discrete Math. \textbf{31} (2017), no.~3, 2079--2092.

\bibitem{E81}
P.~Erd{\H{o}}s, \emph{On the combinatorial problems which {I} would most like
  to see solved}, Combinatorica \textbf{1} (1981), no.~1, 25--42.

\bibitem{EFRS1978}
P.~Erd{\H o}s, R.~J. Faudree, C.~C. Rousseau, and R.~H. Schelp, \emph{The size
  {R}amsey number}, Period. Math. Hungar. \textbf{9} (1978), no.~1-2, 145--161.

\bibitem{FK16}
A.~Frieze and M.~Karo\'nski, \emph{Introduction to random graphs}, Cambridge
  University Press, Cambridge, 2016.

\bibitem{K2016}
M.~Krivelevich, \emph{Long cycles in locally expanding graphs, with
  applications}, to appear in Combinatorica.

\bibitem{L15}
S.~Letzter, \emph{Path {R}amsey number for random graphs}, Combin. Probab.
  Comput. \textbf{25} (2016), no.~4, 612--622.

\end{thebibliography}

\end{document}
