\documentclass[12pt]{article} \usepackage{e-jc} \specs{P3.54}{24(3)}{2017} \usepackage{amssymb,latexsym,amsthm} \usepackage{amsmath} %\usepackage[dvipdfm]{graphicx} \usepackage{tikz} \usepackage{verbatim} \usetikzlibrary {positioning} \usetikzlibrary{arrows,topaths} %%%%%%%%%%%%%%%% %\newtheorem{theorem}{Theorem} %\newenvironment{proof}{{\em Proof.}}{\hfill $\Box$ \vskip 0.5cm} %szamozas szekcionkent ujrakezd \newtheorem{lemma}{Lemma}[section] \newtheorem{theorem}[lemma]{Theorem} \newtheorem{ack}{Acknowledgment} \renewcommand{\theack}{} \newtheorem{corollary}[lemma]{Corollary} \newtheorem{claim}[lemma]{Claim} \newtheorem{definition}[lemma]{Definition} \newtheorem{proposition}[lemma]{Proposition} \newtheorem{fact}[lemma]{Fact} \newtheorem{observation}[lemma]{Observation} \newtheorem{conjecture}[lemma]{Conjecture} \newtheorem{remark}[lemma]{Remark} \newtheorem{problem}[lemma]{Problem} \newtheorem{example}[lemma]{Example} %\newcommand{\comment}[1]{} %\renewcommand{\baselinestretch}{1.3} %\def\ujsor{\hfill\break${}$\quad} \def\bs{\bigskip}\def\ms{\medskip}\def\ds{\displaystyle} \def\beq{\begin{equation}}\def\eeq{\end{equation}} \def\beqn{\begin{eqnarray}}\def\eeqn{\end{eqnarray}} \def\pont{\hspace{-6pt}{\bf.\ }} \def\eps{\varepsilon}\def\ffi{\varphi} %\def\qed{\ifhmode\unskip\nobreak\fi\quad\ifmmode\Box\else$\Box$\fi} \def\marrow{{\boldmath {\marginpar[\hfill$\Rrightarrow \Rrightarrow$]{$\Lleftarrow \Lleftarrow$}}}} \def\janos#1{{\sc J\'anos: }{\marrow\sf #1}} \title{Large monochromatic components in edge colored graphs with a minimum degree condition} %%%%%%%% %% jeno's last update on 3/25/2016 %%%%% %%%%%%%% \author{Andr\'as Gy\'arf\'as\thanks{Research supported in part by NKFIH Grant No. K116769}\\ \small Alfr\'ed R\'enyi Institute of Mathematics\\[-0.8ex] \small Hungarian Academy of Sciences\\[-0.8ex] \small Budapest, P.O. Box 127\\[-0.8ex] \small Budapest, Hungary, H-1364\\ \and G\'{a}bor N. S\'ark\"ozy\thanks{Research supported in part by NKFIH Grants No. K116769, K117879.}\\ \small Alfr\'ed R\'enyi Institute of Mathematics\\[-0.8ex] \small Hungarian Academy of Sciences\\[-0.8ex] \small Budapest, P.O. Box 127\\[-0.8ex] \small Budapest, Hungary, H-1364\\ and\\ \small Computer Science Department\\[-0.8ex] \small Worcester Polytechnic Institute\\[-0.8ex] \small Worcester, MA, USA 01609\\[-0.8ex] \small \texttt{gsarkozy@cs.wpi.edu}\\[-0.8ex] } \date{\dateline{May 26, 2017}{Aug 30, 2017}{Sep 8, 2017}\\ \small Mathematics Subject Classifications: 05C55, 05C35.} \begin{document} \maketitle \vspace{-0.5cm} \begin{abstract} It is well-known that in every $k$-coloring of the edges of the complete graph $K_n$ there is a monochromatic connected component of order at least ${n\over k-1}$. In this paper we study an extension of this problem by replacing complete graphs by graphs of large minimum degree. For $k=2$ the authors proved that $\delta(G)\ge{3n\over 4}$ ensures a monochromatic connected component with at least $\delta(G)+1$ vertices in every $2$-coloring of the edges of a graph $G$ with $n$ vertices. This result is sharp, thus for $k=2$ we really need a complete graph to guarantee that one of the colors has a monochromatic connected spanning subgraph. Our main result here is that for larger values of $k$ the situation is different, graphs of minimum degree $(1-\epsilon_k)n$ can replace complete graphs and still there is a monochromatic connected component of order at least ${n\over k-1}$, in fact $$\delta(G)\ge \left(1 - \frac{1}{1000(k-1)^9}\right)n$$ suffices. Our second result is an improvement of this bound for $k=3$. If the edges of $G$ with $\delta(G)\geq {9n\over 10}$ are $3$-colored, then there is a monochromatic component of order at least ${n\over 2}$. We conjecture that this can be improved to ${7n\over 9}$ and for general $k$ we conjecture the following: if $k\geq 3$ and $G$ is a graph of order $n$ such that $\delta(G)\geq \left( 1 - \frac{k-1}{k^2}\right)n$, then in any $k$-coloring of the edges of $G$ there is a monochromatic connected component of order at least ${n\over k-1}$. \end{abstract} \section{Introduction} Erd\H os and Rado noticed that in every coloring of the edges of a complete graph with two colors there is a monochromatic spanning tree. This remark has been extended into many directions, a survey on the subject is \cite{GYSUR}. For example, a well-known extension of the remark is that in every $k$-edge coloring of a complete graph on $n$ vertices there is a monochromatic connected component of order at least ${n\over k-1}$ (\cite{GY}). In this paper connected components of a graph are just called {\em components} and in edge-colored graphs {\em monochromatic components} are the components of the graph defined by the edges of the same color. Components with one vertex are called {\em trivial} and considered monochromatic in any color. Recently there has been significant interest in extending classical Ramsey-type results to non-complete host graphs (e.g. \cite{BD}, \cite{bbggys}, \cite{barsar}, \cite{BBLS}, \cite{DN}, \cite{DP}, \cite{GYS}, \cite{GS}). One such class is the graphs with appropriately large minimum degree. Along these lines, the authors obtained the following extension of the remark of Erd\H os and Rado. \begin{lemma} \label{deglemma}(Gy\'arf\'as, S\'ark\"ozy \cite{GYS}) Let $G$ be a graph with $n$ vertices and minimum degree $\delta(G)\ge \frac{3}{4}n$. If the edges of $G$ are colored with two colors, then there is a monochromatic component with at least $\delta(G)+1$ vertices. This bound is sharp. \end{lemma} The sharpness of Lemma \ref{deglemma} is shown by the graph obtained from $K_n$ by removing the edges of a complete balanced bipartite subgraph $[A,B]$ ($|A|=|B|\le n/2$) with the $2$-coloring where edges incident to $A$ ($B$) are colored with color 1 (2). Thus we really need a complete graph to obtain a monochromatic spanning component. However, we show that for $k\ge 3$ the situation changes, a slightly lower minimum degree still ensures the same result as in the case of the complete graph. \begin{theorem} \label{tetel2} For every $k\geq 3$ there exists an $n_0=n_0(k)$ such that the following is true. Let $G$ be a graph of order $n\geq n_0$ with $\delta(G)\geq \left( 1 - \frac{1}{1000(k-1)^9}\right)n$. If the edges of $G$ are $k$-colored then there is a monochromatic component of order at least ${n\over k-1}$. \end{theorem} For $k=3$ the degree condition in Theorem \ref{tetel2} is improved as follows. \begin{theorem} \label{tetel3} Let $G$ be a graph of order $n$ and with $\delta(G)\geq \frac{9}{10}n$. If the edges of $G$ are $3$-colored then there is a monochromatic component of order at least ${n\over 2}$. \end{theorem} The degree bound of Theorem \ref{tetel2} is obviously far from best possible perhaps the following conjecture would give the right one. \begin{conjecture} \label{conj2} Let $G$ be a graph of order $n$ such that for some integer $k\geq 3$, $\delta(G)\geq \left( 1 - \frac{k-1}{k^2}\right)n$. If the edges of $G$ are $k$-colored then there is a monochromatic component of order at least ${n\over k-1}$. \end{conjecture} The bound in the conjecture cannot be improved when $k$ is a prime power and $n$ is divisible by $k^2$. Consider an affine plane of order $k$ and delete the pairs in one of the $k+1$ parallel classes. Then color the pairs within the groups of the $i$th parallel class with color $i$ for $i=1,2,\dots,k$. Replace each point with a complete graph of order $t$ and color their edges arbitrarily while all edges between the complete graphs replacing $v,w$ get the color of $vw$. The graph obtained has $n=k^2t$ vertices, it is regular of degree $$tk^2-(k-1)t-1=\left( 1 - \frac{k-1}{k^2}\right)n-1,$$ yet the largest monochromatic component has size only ${n\over k}$. Thus if Conjecture \ref{conj2} is true, there is a surprising jump in the size of the largest monochromatic component if we add one to the minimum degree. Note that Conjecture \ref{conj2} claims that for $k=3$ the bound $\delta(G)\geq \frac{9}{10}n$ in Theorem \ref{tetel3} can be improved to $\delta(G)\geq \frac{7}{9}n$. \section{Proof of Theorem \ref{tetel2}} For a set $S$, $|S|$ denotes the cardinality of $S$, while for a real number $x$, $|x|$ denotes the absolute value of $x$. Our starting point is the following lemma of the first author. \begin{lemma}(Gy\'arf\'as \cite{GY})\label{andraslemma2} Let $t\geq 2$ be an integer and $G$ be a bipartite graph with partite sets of size $m$ and $n$. If $|E(G)|\geq \frac{mn}{t}$, then $G$ has a component of order at least $\lceil \frac{m+n}{t} \rceil$. \end{lemma} Our main tool will be a stability version of this lemma, i.e. either we have a slightly larger component than guaranteed by Lemma \ref{andraslemma2} or we are close to the extremal case which may be interesting on its own. \begin{lemma}\label{andraslemma3} For every integer $t\geq 2$ and $\delta>0$ there is an $n_0=n_0(t,\delta)$ with the following properties. Let $G$ be a bipartite graph with partite sets $V_1$, $V_2$ of size $m$ and $n$ with $n_0\leq \frac{n}{2t}\leq m \leq n$. If $|E(G)|\geq (1-\delta)\frac{mn}{t}$, then one of the following two cases holds: \begin{enumerate} \item[(i)] $G$ has a component of order at least $\lceil \frac{m+n}{t} \rceil$. \item[(ii)] In $G$ there are $t$ components $C_i$ such that for each $C_i, 1\leq i \leq t$ we have the following properties: \begin{enumerate} \item $|C_i| < \lceil \frac{m+n}{t} \rceil$, \item $\left| |C_i\cap V_1| - \frac{m}{t} \right| \leq 10t^2 \sqrt{\delta} \frac{m}{t} = 10t\sqrt{\delta} m$, \item $\left| |C_i\cap V_2| - \frac{n}{t} \right| \leq 10t^2 \sqrt{\delta} \frac{n}{t} = 10t\sqrt{\delta} n$. \end{enumerate} \end{enumerate} \end{lemma} \noindent\textbf{Proof of Lemma \ref{andraslemma3}:} Let us assume that there is a bipartite graph $G$ with partite sets $V_1$, $V_2$ of size $m$ and $n$ with $n_0\leq \frac{n}{2t}\leq m \leq n$ and we have \beq\label{elek}|E(G)| \geq (1-\delta)\frac{mn}{t},\eeq but $(i)$ is not true in Lemma \ref{andraslemma3}. Thus we may assume that the components $C_1,\dots,C_r$ of $G$ satisfy $|C_i|\le \lceil \frac{m+n}{t} \rceil-1=M$ for all $1\le i \le r$. For $1\leq i \leq r$, set $|C_i\cap V_1|=a_i$, $|C_i\cap V_2|=b_i$ and $c_i=a_i+b_i=|C_i|$ ($c_i\ge 1$). Obviously we have \beq\label{aibi}|E(G)|\le S=\sum_{i=1}^r a_i b_i. \eeq A sequence $z'$ of $q$ pairs of non-negative integers, $a_1',b_1',\dots,a_q',b_q'$ is a {\em good sequence} if \beq\label{i} S \le S'=\sum_{i=1}^q a_i' b_i', \eeq \beq\label{ii} \sum_{i=1}^q a_i' = m, \sum_{i=1}^q b_i'=n, \eeq and \beq\label{iii} a_i'+b_i'\le M, i=1,2,\dots,q. \eeq Since $\lceil{m+n\over t}\rceil < {m+n\over t}+1$, we have $$q\ge {m+n\over M}={m+n\over \lceil{m+n\over t}\rceil-1} >t.$$ This implies \begin{claim}\label{long} $q \ge t+1$ for any good sequence. \end{claim} Note that $a_1,b_1,\dots,a_r,b_r$ is a good sequence, so $r\ge t+1$. A good sequence is {\em $A$-ordered} ({\em $B$-ordered}) if $a_1'\ge\dots \ge a_q'$ ($b_1'\ge \dots \ge b_q'$) and {\em $C$-ordered} if $c_1'\ge \dots \ge c_q'$. The next proposition will help us to give an upper bound for $S$. The idea behind this proposition is that the maximum number of edges is achieved if we have components with exactly $M$ vertices. \begin{proposition}\label{boundS} Assume that $m+n\ge t(t+1)$ and $z'=a_1',b_1',\dots,a_q',b_q'$ is a good sequence. Then there exists another good sequence $Z=A_1,B_1,\dots,A_{t+1},B_{t+1}$ such that \begin{itemize} \item[(i)] $A_i+B_i=M$ for $i=1,2,\dots,t-1$. \item[(ii)] Additionally, \begin{enumerate} \item[(A)] If $z'$ is $A$-ordered, then $A_1\ge a_1', A_t+B_t=M, A_{t+1}+B_{t+1}\le t$. \item[(B)] If $z'$ is $B$-ordered, then $B_1\ge b_1', A_t+B_t=M, A_{t+1}+B_{t+1}\le t$. \item[(C)] If $z'$ is $C$-ordered, then $A_t+B_t=K, A_{t+1}+B_{t+1}\le M-K+t$ for any integer $K$ satisfying $c_t'=a_t'+b_t'\le K\le M$. \end{enumerate} \end{itemize} \end{proposition} \begin{proof} %\noindent {\bf Proof of Proposition \ref{boundS}.} Initially we set $A_i=a_i', B_i=b_i'$ for $i=1,\dots,q$. Since $(ii)(A)$ and $(ii)(B)$ are symmetric, it is enough to ensure one of them, say $(ii)(A)$. With Procedure $A$ we will ensure $(i)$ and $(ii)(A)$ and with Procedure $C$ we will ensure $(i)$ and $(ii)(C)$. Both procedures will redefine $A_i, B_i$, but for simplicity we keep the notation $A_i, B_i$ throughout the iterations in the procedures. A pair $A_i, B_i$ is called {\em saturated}, if $A_i+B_i=M$, otherwise called {\em unsaturated}. \medskip\noindent {\bf Procedure $A$} \smallskip \noindent {\bf Step 1:} $A$-order the pairs of the sequence $A_i, B_i$. If there exist two unsaturated pairs $A_i,B_i$ and $A_j,B_j$, $1\le it$. We conclude that there is at most one unsaturated pair and this is possible only if the unsaturated pair is $A_{t+1},B_{t+1}$. Thus $A_1+B_1=A_2+B_2=\dots=A_{t-1}+B_{t-1}=M, A_t+B_t=K$ as required in $(i)$ and in $(ii)(C)$. Finally, $$m+n=(t-1)M+K+A_{t+1}+B_{t+1}=tM-M+K+ A_{t+1}+B_{t+1}=$$ $$t\left(\left\lceil {m+n\over t}\right\rceil -1\right) - M + K +A_{t+1}+B_{t+1}.$$ Thus $A_{t+1}+B_{t+1}-M+K-t=m+n-t\left\lceil {m+n\over t}\right\rceil \le 0$ implying $A_{t+1}+B_{t+1}\le M-K+t$ as required in $(ii)(C)$. \end{proof} \begin{proposition} \label{smallaandb} For any good sequence $z'=a_1',b_1',\dots,a_q',b_q'$, we have $a_i'\le \frac{m}{t} + 2\sqrt{\delta} m$, $b_i'\le \frac{n}{t} + 2\sqrt{\delta} n$ for $1\le i \le q$. \end{proposition} \begin{proof}Suppose w.l.o.g. indirectly that $z'$ is $A$-ordered and \beq \label{x} a_1' > \frac{m}{t} + 2\sqrt{\delta} m. \eeq We apply Proposition \ref{boundS} for $z'$ and we get another good sequence $Z=A_1,B_1,\dots,$ $A_{t+1}, B_{t+1}$ satisfying $(i)$ and $(ii)(A)$. (Similarly, if $b_1' > \frac{m}{t} + 2\sqrt{\delta} m$ we apply Proposition \ref{boundS} for $z'$ and we get another good sequence satisfying $(i)$ and $(ii)(B)$ and the proof is symmetric.) Then, since $Z$ is a good sequence as well, we get the following upper bound for the number of edges in $G$. $$S\le \sum_{i=1}^t A_i B_i + A_{t+1} B_{t+1} =$$ \beq\label{CS}\sum_{i=1}^t (A_i + B_i) A_i - \sum_{i=1}^t A_i^2 + A_{t+1} B_{t+1}= M (m-A_{t+1}) - \sum_{i=1}^t A_i^2 + A_{t+1} B_{t+1}\eeq (using $A_i+B_i=M, 1\leq i \leq t$ in the last equality). To estimate $\sum_{i=1}^t A_i^2$ from below we will use the ``defect form'' of the Cauchy-Schwarz inequality (as in \cite{Sz} or in \cite{KSSz3}): if $$\sum_{i=1}^k A_i=\frac{k}{t}\sum_{i=1}^t A_i +\Delta\qquad(k\leq t),$$ then $$\sum_{i=1}^t A_i^2\geq\frac1t \left(\sum_{i=1}^tA_i\right)^2+\frac{\Delta^2t}{k(t-k)}.$$ Indeed, we will use this with $k=1$. Then from (\ref{x}) and property $A_1\ge a_1'$ in $(ii)(A)$ in Proposition \ref{boundS} we get $$|\Delta| = \left| A_1 - \frac{m}{t} + \frac{A_{t+1}}{t} \right| \geq \left| A_1 - \frac{m}{t} \right| - \left|\frac{A_{t+1}}{t}\right|\geq \left( a_1' - \frac{m}{t} \right) - \frac{A_{t+1}}{t}> $$ $$ 2\sqrt{\delta}m - \frac{A_{t+1}}{t} \geq 2\sqrt{\delta}m - 1 \geq \frac{3}{2}\sqrt{\delta}m,$$ (using the triangle inequality and $m\geq n_0(t,\delta)$) and thus $\frac{\Delta^2 t}{t-1} > \Delta^2 > \frac{9}{4}\delta m^2$. Thus continuing the estimation in (\ref{CS}), the number of edges in $G$ is less than $$M (m-A_{t+1}) - \frac{(m-A_{t+1})^2}{t} - \frac{9}{4}\delta m^2 + A_{t+1} B_{t+1}\leq $$ $$\frac{m+n}{t} (m-A_{t+1}) - \frac{m^2-2mA_{t+1}+A_{t+1}^2}{t} - \frac{9}{4}\delta m^2 + A_{t+1} B_{t+1}\leq $$ $$\frac{mn}{t} - \frac{nA_{t+1}}{t} + \frac{mA_{t+1}}{t} - \frac{9}{4}\delta m^2 + A_{t+1} B_{t+1} \leq \frac{mn}{t} - \frac{9}{4}\delta m^2 + A_{t+1} B_{t+1}\leq $$ $$\frac{mn}{t} - \frac{9}{8}\delta \frac{mn}{t} + t^2 \leq (1-\delta)\frac{mn}{t},$$ indeed a contradiction with (\ref{elek}) (here in the last line we used $A_{t+1},B_{t+1}\leq t$ (see $(ii)(A)$ in Proposition \ref{boundS}) and $m\geq \frac{n}{2t}\geq n_0(t,\delta)$). \end{proof} \begin{proposition}\label{smallaplusb} For any $C$-ordered good sequence $z'=a_1',b_1',\dots,a_q',b_q'$, we have $c_t' =a_t'+b_t'\ge (1-2t\delta)M$. \end{proposition} \begin{proof} Suppose indirectly that $c_t'<(1-2t\delta)M$ and set $K=(1-2t\delta)M$ (for simplicity we assume that this is an integer). We apply Proposition \ref{boundS} for $z'$ and we get another good sequence $Z=A_1,B_1,\dots,$ $A_{t+1}, B_{t+1}$ satisfying $(i)$ and $(ii)(C)$ with this choice of $K$. Then, using $(ii)(C)$ we obtain the following upper bound for the number of edges in $G$. $$S\le \sum_{i=1}^{t+1} A_i B_i = \sum_{i=1}^{t+1} (A_i + B_i) A_i - \sum_{i=1}^{t+1} A_i^2 \le $$ $$ M (m-A_t - A_{t+1}) + (1-2t\delta) M A_t + (2t\delta M+t) A_{t+1} - \sum_{i=1}^{t+1} A_i^2=$$ $$ M ( m - 2t\delta A_t - (1- 2t\delta) A_{t+1}) + t A_{t+1} - \sum_{i=1}^{t} A_i^2 - A_{t+1}^2$$ To estimate $\sum_{i=1}^t A_i^2$ from below here we will use the ``ordinary form'' of the Cauchy-Schwarz inequality and thus continuing the estimation, the number of edges in $G$ is at most $$ M ( m - 2t\delta A_t - (1- 2t\delta) A_{t+1})- \frac{(m-A_{t+1})^2}{t} + t A_{t+1} - A_{t+1}^2\leq $$ $$\frac{m+n}{t} m - 2t\delta \frac{m+n}{t} A_t - (1- 2t\delta) \frac{m+n}{t} A_{t+1} - \frac{m^2-2mA_{t+1}+A_{t+1}^2}{t} + t A_{t+1} - A_{t+1}^2\leq $$ $$\frac{mn}{t} - 2t\delta \frac{m+n}{t} A_t - (1- 2t\delta) \frac{2m}{t} A_{t+1} + \frac{2m}{t} A_{t+1} + t A_{t+1}=$$ $$\frac{mn}{t} - 2t\delta \frac{n}{t} A_t - 2t\delta \frac{m}{t} A_t + 2t\delta \frac{2m}{t} A_{t+1} + t A_{t+1}\leq \frac{mn}{t} - 2t\delta \frac{n}{t} A_t < (1-\delta)\frac{mn}{t},$$ indeed a contradiction with (\ref{elek}). Here in the last line we used that $m\geq n_0(t,\delta)$, $A_{t+1}\leq 2t\delta M + t \ll \frac{m}{2t} \leq A_t$. To get the last inequality, observe that $Z$ is a good sequence and thus using Proposition \ref{smallaandb} we get $$A_t = K - B_t \geq (1-2t\delta)\frac{m+n}{t} - 1 - B_t \geq (1-2t\delta)\frac{m+n}{t} - 1 - \frac{n}{t} - 2t\sqrt{\delta} \frac{n}{t} \geq $$ $$\frac{m}{t} - 2t\delta \frac{m}{t} - 4t\sqrt{\delta} \frac{n}{t} -1 \geq \frac{m}{2t},$$ indeed if $m$ is sufficiently large. \end{proof} \begin{remark} Note that we will use Propositions \ref{smallaplusb} and \ref{smallaandb} only for $a_1, b_1, \ldots, a_r, b_r$. However, for the proof of Proposition \ref{smallaplusb} we needed Proposition \ref{smallaandb} for a more general good sequence. For uniformity, we proved Proposition \ref{smallaplusb} also for a general good sequence. \end{remark} Now we can use Propositions \ref{smallaandb} and \ref{smallaplusb} to finish the proof of Lemma \ref{andraslemma3}. Assume that $|C_1|\geq \ldots \geq |C_r|$ holds for the components of $G$, i.e. $a_1,b_1,\dots,a_r,b_r$ is a $C$-ordered good sequence. We claim that $C_1, \ldots, C_t$ satisfy $(ii)(b)$ and $(ii)(c)$ in Lemma \ref{andraslemma3}. Thus for each $1\leq i \leq t$ we need to show $$\frac{m}{t} - 10t\sqrt{\delta} m \leq a_i \leq \frac{m}{t} + 10t\sqrt{\delta} m,$$ and $$\frac{n}{t} - 10t\sqrt{\delta} n \leq b_i\le \frac{n}{t} + 10t\sqrt{\delta} n.$$ Indeed, we already have a stronger upper bound for $a_i$ and $b_i$ from Proposition \ref{smallaandb}. % (note again that $a_i, b_i$ is a good sequence and thus we can apply %Propositions \ref{smallaandb} and \ref{smallaplusb}). To get the lower bound for $a_i$ (and similarly for $b_i$) by using Proposition \ref{smallaplusb} for $C_i$ and Proposition \ref{smallaandb} for $b_i$ (and similarly for $a_i$) we have $$a_i = |C_i| - b_i \geq (1-2t\delta)\frac{m+n}{t} - 1 - b_i \geq (1-2t\delta)\frac{m+n}{t} - 1 - \frac{n}{t} - 2t\sqrt{\delta} \frac{n}{t}\geq $$ $$\frac{m}{t} - 2t\delta \frac{m}{t} - 4t\sqrt{\delta} \frac{n}{t} \geq \frac{m}{t} - 10t^2\sqrt{\delta} \frac{m}{t},$$ as desired (using again $n\leq 2tm$). {\hfill\quad\qed}\\ \noindent {\bf End of proof of Lemma \ref{andraslemma3}}. Now we are ready to prove Theorem \ref{tetel2}. \begin{proof}[Proof of Theorem \ref{tetel2}:] Let $k\geq 3$ be an integer and let $G$ be a graph of order $n\geq n_0$ with $\delta(G)\geq \left( 1 - \frac{1}{1000 (k-1)^9}\right)n$ and a $k$-coloring on the edges. Put $t=k-1$ (then $t\geq 2$) and let $\delta' = \frac{1}{1000 t^9}$. We have to show that there is a monochromatic component of order at least $\frac{n}{t}$. Assume indirectly that this is not the case. Consider the largest monochromatic component (say it is red) and denote the set of vertices in this component by $V_1$. Let $V_2=V(G)\setminus V_1$, $|V_1|=m'$ and $|V_2|=n-m'=n'$. We may clearly assume the following \beq\label{comp}n'\geq \frac{n}{t} > m' \geq \frac{n'}{2t}.\eeq (For the last inequality we may consider the monochromatic stars from any vertex of $V_1$ to vertices of $V_2$.) We consider the bipartite graph $G^b$ induced by $G$ between $V_1$ and $V_2$. Using the minimum degree condition in $G$, the number of edges in $G^b$ is at least \beq\label{G^b} m' ( n' - \delta' n) \geq m' ( n' - 2\delta' n') = (1-2\delta' )m'n',\eeq (using $n'\geq \frac{n}{2}$). We cannot have a red edge in $G^b$ and thus the number of colors used on the edges is at most $t=k-1$. Denote the monochromatic bipartite graphs induced by the $t$ colors with $G^b_1, \ldots, G^b_t$. Then for each $1\leq i \leq t$ we have $|E(G^b_i)|<\frac{m'n'}{t}$, since otherwise we are done by applying Lemma \ref{andraslemma2} to $G^b_i$, we have a monochromatic component of order at least $n/t$ in color $i$. This implies that for each $1\leq i \leq t$ we have \beq\label{G^b_i} |E(G^b_i)| \geq (1-2t\delta' ) \frac{m'n'}{t}.\eeq Indeed, otherwise the number of edges in $G^b$ would be less than $$(1-2t\delta' ) \frac{m'n'}{t} + (t-1) \frac{m'n'}{t} = (1-2\delta') m' n',$$ a contradiction with (\ref{G^b}). Using (\ref{G^b_i}), we can apply Lemma \ref{andraslemma3} for each $G^b_i, 1\leq i \leq t$ with $m=m'$, $n=n'$ and $\delta = 2 t \delta'$. Note that (\ref{comp}) and (\ref{G^b_i}) imply that the conditions of the lemma are satisfied. Since we cannot have $(i)$ in Lemma \ref{andraslemma3}, we must have the $t$ components described in $(ii)$ of Lemma \ref{andraslemma3} for each $G^b_i$, call these the {\em main components}. Consider the remaining set of vertices not covered by the union of these main components. By $(ii)(a)$ this set is non-empty and by $(ii)(b)$ and $(ii)(c)$ the intersections of this set with both partite classes of $G^b_i$ are small. Thus we get the following claim. \begin{claim} \label{uncovered} For each $G^b_i$ the set uncovered by the union of the main components is nonempty, and this set intersects both partite classes of $G^b_i$ in at most $10 t^2 \sqrt{2t\delta'} m'$ vertices. \end{claim} Assume that $G^b_1$ is blue. By Claim \ref{uncovered} (applied to $G_1^b$) there is a vertex uncovered by the main blue components, say $v\in V_1$. The edges between $v$ and the set of vertices in $V_2$ covered by the main blue components cannot be blue or red, so they are colored with $(t-1)$ colors. This implies using the minimum degree condition in $G$ and Claim \ref{uncovered} that in one of these $(t-1)$ colors (say in a green $G_2^b$), there is a green star from $v$ to $V_2$ of size at least $$\frac{n'-\delta' n - 10 t^2 \sqrt{2t\delta'}n'}{t-1} \geq \frac{1- 12t^2\sqrt{2t\delta'}}{t-1} n'.$$ However, this leads to contradiction because by Lemma \ref{andraslemma3} and Claim \ref{uncovered} (applied to $G_2^b$) this green star cannot be inside of any main green component and cannot be inside the set of vertices uncovered by their union, provided that $$\frac{1- 12t^2\sqrt{2t\delta'}}{t-1} > \max \left\{10 t^2 \sqrt{2t\delta'}, \frac{1}{t} + 10t \sqrt{2t\delta'}\right\}.$$ This in turn is true if $$\frac{1- 12t^2\sqrt{2t\delta'}}{t-1} \geq \frac{1}{t} + 10 t^2 \sqrt{2t\delta'},$$ which is true if $$1- 4t\sqrt{2t\delta'} \geq 1 - \frac{1}{t} + 10 t^3 \sqrt{2t\delta'}.$$ Finally, this is true if $$1 \geq 1 - \frac{1}{t} + 22 t^3 \sqrt{2t\delta'},$$ $$ \frac{1}{t} \geq 22 t^3 \sqrt{2t\delta'},$$ $$ \frac{1}{968t^9} \geq \delta',$$ which is true by our choice of $\delta'$. \end{proof} \section{Proof of Theorem \ref{tetel3}} Our starting point is the following lemma. \begin{lemma} \label{bipconn} Assume that $G=[A,B]$ is a bipartite graph with $|A|=\alpha n, |B|=\beta n$ and $\alpha \le \beta$. Set $\rho=min\{\alpha, {\beta \over 2}\}$. If every vertex of $G$ is non-adjacent to less than $\rho n$ vertices, then $G$ is connected. \end{lemma} \begin{proof} Let $x,y\in A$. Since $\rho n \leq {|B|\over 2}$, the neighbors of $x,y$ intersect in $B$. Also, because $\rho n \leq |A|$, every vertex of $B$ has a neighbor in $A$. Thus any two vertices of $G$ can be connected by a path (of length at most four).\qed Let $G$ be a graph of order $n$ with $\delta(G)\geq (1-\rho )n$ (thus every vertex is non-adjacent to less than $\rho n$ vertices) and consider a $3$-coloring on its edges. Let $v$ be an arbitrary vertex and let $N_i$ denote its neighbors in color $i$. We may assume that $|N_1|\ge |N_2|\ge |N_3|$, let $C_1,C_2$ be the monochromatic components in colors $1,2$ containing $N_1,N_2$. Assume that $|C_1|,|C_2|<{n\over 2}$. We are going to prove that there is a monochromatic component of size at least ${n\over 2}$ in color $3$. Set $$M=C_1\cap C_2, A_1=C_1\setminus M, A_2=C_2\setminus M, X=V(G)\setminus (C_1\cup C_2).$$ Observe that all edges of the bipartite graphs $[A_1,A_2],[M,X]$ are colored with color 3. We claim that the larger of them is connected and this proves the theorem since the larger must have at least ${n\over 2}$ vertices. \noindent {\bf Case 1. } $[A_1,A_2]$ has at least ${n\over 2}$ vertices. We may assume that $|A_1|\le |A_2|$ (otherwise the argument is symmetric). Since $\delta(G)\geq (1-\rho)n$, the choice of $C_1,C_2$ implies that $$|A_1|=|(C_1\cup C_2)\setminus C_2| \ge {2n\over 3}(1-\rho)-{n\over 2}={n(1-4\rho)\over 6}.$$ Therefore if we select $\rho$ to satisfy $$\rho = {(1-4\rho)\over 6}$$ i.e. $\rho={1\over 10}$, then $|A_1|\geq {n\over 10}$. We also have $${|A_2|\over 2}\ge {{n\over 4}\over 2} ={n\over 8}.$$ Therefore Lemma \ref{bipconn} implies that (the color $3$) bipartite graph $[A_1,A_2]$ is connected. \noindent {\bf Case 2. } $[M,X]$ has at least ${n\over 2}$ vertices. Since $|C_1|,|C_2|\le {n\over 2}$, $$n=|C_1|+|C_2|-|M|+|X|\le n-|M|+|X|,$$ we have $|M|\le |X|$. Also, from the choice of $C_1,C_2$, $|C_1\cup C_2|\ge {2n\over 3}(1-\rho)$, therefore $|X|\le {n\over 3}(1+2\rho)$ thus $$|M|\ge {n\over 2}-{n\over 3}(1+2\rho)={n(1-4\rho)\over 6},$$ giving the same inequality for $|M|$ as we had before for $|A_1|$. Since $|M|\le |X|$, the same proof as in Case 1. works here as well. Thus if $\rho={1\over 10}$ (i.e. $\delta(G)\ge {9n\over 10}$) we have a monochromatic component of size at least ${n\over 2}$ in every $3$-coloring of the edges of $G$. \end{proof} \section{Further directions} A further extension of the problem addressed in this paper would be to investigate graphs of smaller minimum degree, for example, extending Lemma \ref{deglemma} in this direction. For graphs of ``very small'' minimum degree this problem can be answered easily. Indeed, there is always a monochromatic star that has at least $\lceil{\delta(G)\over 2}\rceil +1$ vertices, and this estimate is close to best possible if $\delta(G)< 2\sqrt{n}$. For instance, if $\delta(G)$ is even, one can partition $n$ vertices into disjoint copies of $K{_{\delta\over 2}} \square K_{{\delta\over 2}}$ (where $\square$ denotes the Cartesian product) and color the edges between vertices in the same row blue, the edges in the same column red. Thus the order of the largest monochromatic component (connected subgraph) we can guarantee decreases roughly from $\delta(G)$ to $\delta(G)/2$ when $\delta(G)$ decreases from $\frac{3}{4}n$ to $2\sqrt{n}$. It is natural to ask what happens in-between. Somewhat surprisingly in this range the order of the largest monochromatic component changes as a {\em stepwise constant} function in terms of $\delta(G)$. More precisely, the following holds. \begin{theorem} \label{tetel1} (White \cite{Wh1}) Let $G$ be a graph of order $n$ such that for some integer $m\geq 3$, $\delta(G)\geq \frac{2m-1}{m^2}n$. If the edges of $G$ are $2$-colored then there is a monochromatic component of order at least ${n\over m-1}$. \end{theorem} This result is basically implicit in the proof of Lemma 4.7 in White \cite{Wh1} (see also in \cite{Wh2}); however, it is not even stated there as a separate statement. Note that Theorem \ref{tetel1} is false for $m=2$, in which case Lemma \ref{deglemma} gives the order of the largest monochromatic component. The bound on the minimum degree in Theorem \ref{tetel1} cannot be weakened as the following example shows. \begin{example} Let $G_b\square G_r$ be the Cartesian product of a blue $m$-clique $G_b$ and a red $m$-clique $G_r$, and substitute every vertex of $G_b\square G_r$ by an arbitrarily $2$-colored $t$-clique, for any $t\geq 1$. We obtain a graph on $n=m^2t$ vertices, which has minimum degree $\delta=(2m-1)t-1= {2m-1\over m^2}n - 1$, and each monochromatic component has only ${n\over m}$ vertices. \end{example} We believe that a similar phenomenon occurs for more than 2 colors. \begin{conjecture} \label{conj1} Let $m\geq 3, k\geq 2, m\geq k$ be integers and let $G$ be a graph of order $n$ such that $\delta(G)\geq \frac{k(m-1)+1}{m^2}n$. If the edges of $G$ are $k$-colored then there is a monochromatic component of order at least ${n\over m-1}$. \end{conjecture} Again this would be best possible. For $k=2$ we get Theorem \ref{tetel1}. For $m=k\geq 3$ we get Conjecture \ref{conj2}. \smallskip \noindent {\bf Remark.} Bal, DeBiasio and McKenney \cite{BDM} (with a similar proof) improved the condition $\delta(G)\ge {9\over 10}$ to $\delta(G)\ge {7\over 8}$ in Theorem \ref{tetel3}. \smallskip \subsection*{Acknowledgment.} The authors are grateful to a referee for many important remarks and for catching an error in an earlier version of the manuscript. \begin{thebibliography}{99} \bibitem{BD} D. Bal, L. DeBiasio, Partitioning random graphs into monochromatic components, {\em Electronic Journal of Combinatorics} {\bf 24} (2017), \#P1.18. \bibitem{BDM} D. Bal, L. DeBiasio, P. McKenney, personal communication. \bibitem{bbggys} J. Balogh, J. Bar\'at, D. Gerbner, A. Gy\'arf\'as, G.N. S\'ark\"ozy, Partitioning $2$-edge-colored graphs by monochromatic paths and cycles, {\em Combinatorica} {\bf 34} (2014), 507--526. \bibitem{barsar} J. Bar\'at, G.N. S\'ark\"ozy. Partitioning $2$-edge-colored Ore-type graphs by monochromatic cycles. {\em Journal of Graph Theory} {\bf 81} (2016), 317--328. \bibitem{BBLS} F.S. Benevides, T. {\L}uczak, A. Scott, J. Skokan, M. White, Monochromatic cycles and the monochromatic circumference in 2-coloured graphs, {\em Combinatorics, Probability and Computing} {\bf 21} (2012), 57--87. \bibitem{DN} L. DeBiasio, L. Nelsen, Monochromatic cycle partitions of graphs with large minimum degree, {\em Journal of Combinatorial Theory, Ser. B} {\bf 122} (2017), 634--667. \bibitem{DP} A. Dudek, P. Pralat, On some multicolour Ramsey properties of random graphs, submitted for publication. \bibitem{GY} A. Gy\'arf\'as, Partition covers and blocking sets in hypergraphs, Candidate's Thesis, MTA SZTAKI Tanulm\'anyok 71/1977, (In Hungarian), MR 58, 5392. \bibitem{GYSUR} A. Gy\'arf\'as, Large monochromatic components in edge colorings of graphs: a survey, In: Alexander Soifer (editor) Ramsey Theory: Yesterday, Today and Tomorrow. New York; London: Birkhauser Verlag, 2010, 77--96. \bibitem{GYS} A. Gy\'arf\'as, G.N. S\'ark\"ozy, Star versus two stripes Ramsey numbers and a conjecture of Schelp, {\em Combinatorics, Probability and Computing}, {\bf 21} (2012), 179--186. \bibitem{KSSz3} J. Koml\'os, G.N. S\'ark\"ozy, E. Szemer\'edi, An algorithmic version of the Blow-up Lemma, {\em Random Structures and Algorithms}, {\bf 12} (1998), 297--312. \bibitem{GS} G.N. S\'ark\"ozy, Monochromatic cycle partitions of edge-colored graphs, {\em Journal of Graph Theory}, {\bf 66} (2011), 57--64. \bibitem{Sz} E. Szemer\'edi, Regular partitions of graphs, Colloques Internationaux C.N.R.S. $\mbox{N}^{\underline{o}}$ 260 - Probl\`emes Combinatoires et Th\'eorie des Graphes, Orsay (1976), 399--401. \bibitem{Wh1} M. White, The monochromatic circumference of 2-edge-colored graphs, {\em Journal of Graph Theory}, {\bf 85} (2017), 133--151. \bibitem{Wh2} M. White, Cycles in edge-coloured graphs and subgraphs of random graphs, PhD thesis, University of Oxford, Oxford, 2011. \end{thebibliography} \end{document} We get the following upper bound for the number of edges in $G$. $$S\le \sum_{i=1}^{t+1} A_i B_i = \sum_{i=1}^{t+1} (A_i + B_i) A_i - \sum_{i=1}^{t+1} A_i^2 =$$ $$ M (m-A_t - A_{t+1}) + (1-2t\delta) M A_t + 2t\delta M A_{t+1} - \sum_{i=1}^{t+1} A_i^2=$$ $$ M ( m - 2t\delta A_t - (1- 2t\delta) A_{t+1}) - \sum_{i=1}^{t} A_i^2 - A_{t+1}^2$$ (using Properties (i) and (ii) in Proposition \ref{boundS} in the last equality). To estimate $\sum_{i=1}^t A_i^2$ from below here we will use the ``ordinary form'' of the Cauchy-Schwarz inequality and thus continuing the estimation, the number of edges in $G$ is at most $$ M ( m - 2t\delta A_t - (1- 2t\delta) A_{t+1})- \frac{(m-A_{t+1})^2}{t} - A_{t+1}^2\leq $$ $$\frac{m+n}{t} m - 2t\delta \frac{m+n}{t} A_t - (1- 2t\delta) \frac{m+n}{t} A_{t+1} - \frac{m^2-2mA_{t+1}+A_{t+1}^2}{t} - A_{t+1}^2\leq $$ $$\frac{mn}{t} - 2t\delta \frac{m+n}{t} A_t - (1- 2t\delta) \frac{2m}{t} A_{t+1} + \frac{2m}{t} A_{t+1} =$$ $$\frac{mn}{t} - 2t\delta \frac{n}{t} A_t - 2t\delta \frac{m}{t} A_t + 2t\delta \frac{2m}{t} A_{t+1}\leq \frac{mn}{t} - 2t\delta \frac{n}{t} A_t < (1-\delta)\frac{mn}{t},$$ indeed a contradiction with (\ref{elek}) (here in the last line we used $A_t > \frac{m}{2t}\geq 2 A_{t+1}$). \qed Now we can use Propositions \ref{smallaandb} and \ref{smallaplusb} to finish the proof of Lemma \ref{andraslemma2}. Indeed, a stronger upper bound for $a_i$ and $b_i$ is given in Proposition \ref{smallaandb}. To get the lower bound for $a_i$ (and similarly for $b_i$) by using Propositions \ref{smallaandb} and \ref{smallaplusb} we get $$a_i = |C_i| - b_i \geq (1-2t\delta)\frac{m+n}{t} - b_i \geq (1-2t\delta)\frac{m+n}{t} - \frac{n}{t} - 2t\sqrt{\delta} \frac{n}{t}= $$ $$\frac{m}{t} - 2t\delta \frac{m}{t} - 4t\sqrt{\delta} \frac{n}{t} \geq \frac{m}{t} - 10t\sqrt{\delta} \frac{m}{t},$$ as desired (using again $n\leq 2tm$). Bevezetesbol leszedve A further extension of the problem would be to investigate graphs of smaller minimum degree, for example, extending Lemma \ref{deglemma} in this direction. For graphs of ``very small'' minimum degree this problem can be answered easily. Indeed, there is always a monochromatic star that has at least $\lceil{\delta(G)\over 2}\rceil +1$ vertices, and this estimate is close to best possible if $\delta(G)< 2\sqrt{n}$. For instance, if $\delta(G)$ is even, one can partition $n$ vertices into disjoint copies of $K{_{\delta\over 2}} \square K_{{\delta\over 2}}$ (where $\square$ denotes the Cartesian product) and color the edges between vertices in the same row blue, the edges in the same column red. Thus the order of the largest monochromatic component (connected subgraph) we can guarantee decreases roughly from $\delta(G)$ to $\delta(G)/2$ when $\delta(G)$ decreases from $\frac{3}{4}n$ to $2\sqrt{n}$. It is natural to ask what happens in-between. Somewhat surprisingly in this range the order of the largest monochromatic component changes as a {\em stepwise constant} function in terms of $\delta(G)$. More precisely, the following holds. \begin{theorem} \label{tetel1} (White \cite{Wh1}) Let $G$ be a graph of order $n$ such that for some integer $m\geq 3$, $\delta(G)\geq \frac{2m-1}{m^2}n$. If the edges of $G$ are $2$-colored then there is a monochromatic component of order at least ${n\over m-1}$. \end{theorem} This result is basically implicit in the proof of Lemma 4.7 in White \cite{Wh1} (see also in \cite{Wh2}); however, it is not even stated there as a separate statement. Note that Theorem \ref{tetel1} is false for $m=2$, in which case Lemma \ref{deglemma} gives the order of the largest monochromatic component. The bound on the minimum degree in Theorem \ref{tetel1} cannot be weakened as the following example shows. \begin{example} Let $G_b\square G_r$ be the Cartesian product of a blue $m$-clique $G_b$ and a red $m$-clique $G_r$, and substitute every vertex of $G_b\square G_r$ by an arbitrarily $2$-colored $t$-clique, for any $t\geq 1$. We obtain a graph on $n=m^2t$ vertices, which has minimum degree $\delta=(2m-1)t-1= {2m-1\over m^2}n - 1$, and each monochromatic component has only ${n\over m}$ vertices. \end{example} We believe that a similar phenomenon occurs for more than 2 colors. \begin{conjecture} \label{conj1} Let $m\geq 3, k\geq 2, m\geq k$ be integers and let $G$ be a graph of order $n$ such that $\delta(G)\geq \frac{k(m-1)+1}{m^2}n$. If the edges of $G$ are $k$-colored then there is a monochromatic component of order at least ${n\over m-1}$. \end{conjecture} Again this would be best possible. For $k=2$ we get Theorem \ref{tetel1}. For $m=k\geq 3$ we get Conjecture \ref{conj2}. Hozzavalo referencia