% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.28}{22(1)}{2015} % 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 % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb, mathrsfs} % 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 \newcommand{\be}{\begin{enumerate}} \newcommand{\ee}{\end{enumerate}} \newcommand{\pp}{\prime \prime} \newcommand{\SM}{\mathscr{M}} % 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 Density of Gallai multigraphs} % 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{Colton Magnant\\ \small Department of Mathematical Sciences\\[-0.8ex] \small Georgia Southern University\\[-0.8ex] \small Statesboro, GA, U.S.A.\\ \small\tt cmagnant@georgiasouthern.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{Aug 20, 2014}{Dec 22, 2014}{Feb 16, 2015}\\ \small Mathematics Subject Classifications: 05C15, 05C35} \begin{document} \maketitle \begin{abstract} Diwan and Mubayi asked how many edges of each color could be included in a $3$-edge-colored multigraph containing no rainbow triangle. We answer this question under the modest assumption that the multigraphs in question contain at least one edge between every pair of vertices. We also conjecture that this assumption is, in fact, without loss of generality. % keywords are optional \bigskip\noindent \textbf{Keywords:} rainbow triangle, Gallai coloring, multigraph \end{abstract} % -------------------- \section{Introduction} % -------------------- In a yet unpublished manuscript, Diwan and Mubayi \cite{DM14} asked the following question. \begin{question}[Diwan, Mubayi - \cite{DM14}]\label{DMProblem} Let $R$, $G$, and $B$ be graphs on the same vertex set of size $n$. How large must $\min \{ e(R), e(G), e(B)\}$ be to guarantee that $R \cup G \cup B$ contains a rainbow triangle? \end{question} A graph (or multigraph) with no rainbow triangle is called \emph{Gallai-colored} (or simply \emph{G-colored}) in honor of Gallai's seminal work in \cite{G67}. \begin{theorem}[Gallai - \cite{G67}]\label{Gallai} Every G-colored complete (simple) graph has a partition of the vertices into at least two parts such that on the edges between the parts there are at most two colors and on the edges between each pair of parts, there is only one color. \end{theorem} Let $G$ be a G-colored multigraph on $n$ vertices using three colors. For this paper, we will not allow more than one edge of a single color between any pair of vertices. Let $m(G)$ be the minimum number of edges in a single color in $G$. Let $m = m(n)$ be limit of the maximum value of $m(G)$ over all Gallai colored multigraphs $G$ on $n$ vertices as $n \rightarrow \infty$. Here, the limit is taken simply to avoid rounding in subsequent arguments. Then a relaxed version of Question~\ref{DMProblem} can be stated as `find $m$'. %%%%%%%%%%%%%%%% Pairs of vertices connected by two edges are said to have a \emph{double edge} between them. Similarly define a \emph{triple edge} to be a pair of vertices with three edges connecting them. A subgraph is called a \emph{double clique} if all pairs of vertices in the subgraph have a double edge between them. Trivially, $m \geq \frac{n^{2}}{4}$ by considering two double cliques $A$ and $B$ each of order $n/2$ and each using colors red and blue with all edges in between using green. This colored graph contains no rainbow triangle and each color has approximately $n^{2}/4$ edges. We call this multigraph \emph{complete} since it has at least one edge between every pair of vertices. It should be noted that there is also a non-complete example that also achieves this trivial lower bound. Consider the balanced complete bipartite graph $A \cup B$ in which all multi-edges between $A$ and $B$ are triple edges. These very different examples may suggest that this lower bound is not sharp and, in fact, this is the case, as seen in our first result. \begin{proposition}\label{Prop:LowBd} $$ m \geq \frac{26 - 2\sqrt{7}}{81} n^{2} \sim 0.25566 n^{2}. $$ \end{proposition} \begin{proof} Consider a large graph on $n$ vertices partitioned into $3$ parts $H_{1}, H_{2}$ and $H_{3}$. Between the parts we have all green edges. Within $H_{1}$, we have all multi-edges in red and blue, in $H_{2}$ all multi-edges are red and green while in $H_{3}$, all multi-edges are blue and green. This graph certainly contains no rainbow triangle. We balance the orders of $H_{1}, H_{2}$ and $H_{3}$ in such a way that all colors appear on an equal number of edges. In particular, this means $|H_{2}| = |H_{3}|$ while $|H_{1}|$ is significantly larger. As $n$ gets large, the appropriate orders approach $|H_{1}| = c_{1}n$ and $|H_{2}| = |H_{3}| = c_{2}n$ where \begin{equation}\label{C1C2} c_{1} = \frac{1 + 2\sqrt{7}}{9} \sim 0.69906 ~ ~ ~ ~ ~ \text{and} ~ ~ ~ ~ ~ c_{2} = \frac{4 - \sqrt{7}}{9} \sim 0.15047. \end{equation} In this case, each color has $\frac{26 - 2\sqrt{7}}{81} n^{2}$ edges as desired. \end{proof} We consider the case where the multigraph in question is complete, a useful but justifiable property. Since Question~\ref{DMProblem} involves finding the maximum density under certain restrictions, the assumption of completeness is only natural. As seen in Conjecture~\ref{Conj:Equal} below, we believe that this assumption does not lose generality, meaning that the maximum density occurs when this property holds. Another property that will be implied was defined and used in \cite{HMP14}. A G-colored complete multigraph is called \emph{reduced} if it contains no pair of vertices $\{ u, v\}$ with all three colors on edges between them. This gives us the following fact. \begin{fact}\label{Triple} If $uv$ is a triple edge, then each other vertex in $G$ must have exactly one color on edges to both $u$ and $v$ to avoid creating a rainbow triangle. \end{fact} Let $M$ be limit of the maximum value of $m(G)$ over all G-colored, complete, %reduced multigraphs $G$ on $n$ vertices as $n \rightarrow \infty$. With this notation, our main result is the following. \begin{theorem}\label{Thm:Main} $$ M = \frac{26 - 2\sqrt{7}}{81} n^{2} \sim 0.25566 n^{2}. $$ \end{theorem} This result is proven in Section~\ref{Sect:MainPf}. Note that the multigraph constructed in the proof of Proposition~\ref{Prop:LowBd} is complete and actually contains no triple edges. In support of our assumptions, we believe the following conjecture to be true. \begin{conjecture}\label{Conj:Equal} $m = M = \frac{26 - 2\sqrt{7}}{81} n^{2}$. \end{conjecture} \section{Preliminaries} Here we state a result of Halperin, Magnant and Pula \cite{HMP14} which provides structure of complete G-colored multigraphs much like that provided in Theorem~\ref{Gallai}. Let $\SM$ be the family of multigraphs defined inductively by: \be \item Any multigraph with at most two vertices is in $\SM$. \item Fix colors $A$ and $B$ and graphs $\{M_i : 1 \leq i \leq t \} \subseteq \SM$. For each $1 \leq i \neq j \leq t$, connect $M_i$ and $M_j$ by either $A$ or $B$. If $|M_i| = |M_j| = 1$, we may also connect $M_i$ and $M_j$ by both $A$ and $B$. The resulting multigraph is in $\SM$. \ee \begin{theorem}[\cite{HMP14}]\label{Theorem:G-partition} $\SM$ is the family of all complete G-colored multigraphs. \end{theorem} Since this result implies a partition much like that of Theorem~\ref{Gallai}, we call this partition a \emph{G-partition}. In an effort to include as many edges as possible, we always assume our graphs to be \emph{maximal} G-colored multigraphs, meaning that no edge can be added in any color without producing a rainbow triangle. In particular, in Item~2 above, this means that if $|M_{i}| = |M_{j}| = 1$, then the two must be connected by both colors. Such parts of the partition with $|M_{i}| = 1$ will be called \emph{singleton} parts. With this notation, we have observed that we may assume the singleton parts of a G-partition induce a double clique. In particular, by Theorem~\ref{Theorem:G-partition}, Fact~\ref{Triple} implies that triple edges can only occur inside parts of a G-partition. Also, since we have assumed $G$ is complete, no two triple edges can share a vertex. Note that a G-partition can be iterated by considering each part of the partition and again applying Theorem~\ref{Theorem:G-partition}. Define a \emph{layer} of a G-partition to be the set of all the parts in a partition. Note that a layer may be contained within a single part of a previous layer. \section{Proof of Theorem~\ref{Thm:Main} \label{Sect:MainPf}} Let $G$ be a maximum G-colored $3$-coloring of a large complete multigraph on $n$ vertices. Say we use colors red, blue, and green. By Proposition~\ref{Prop:LowBd}, there are at least $$ 3 \left( \frac{26 - 2\sqrt{7}}{81} \right) n^{2} \sim 0.76698n^{2} $$ edges in $G$. This gives us the following fact. \begin{fact}\label{Fact:Extras} There are at least $$ \frac{25 - 4\sqrt{7}}{54} n^{2} \sim 0.26698n^{2} $$ extra edges in $G$ in addition to the underlying complete graph with ${n \choose 2}$ edges. \end{fact} Since $G$ contains no triple edges, all extra edges must be double. By Fact~\ref{Triple}, it is easy to show that there are at most $2 {n \choose 2}$ edges in $G$ so we get a trivial upper bound of $M \leq \frac{n^{2}}{3}$. We now start building structure on $G$. This first claim follows easily from the assumption that $G$ is edge-maximal with no rainbow triangle (or using Theorem~\ref{Theorem:G-partition}). \begin{claim}\label{Claim:D-Cliques} Each maximal subset of $V(G)$ inducing a connected subgraph of double edges induces a double clique (with exactly two colors). \end{claim} %\begin{proof} %By Theorem~\ref{Theorem:G-partition}, any set $S$ of vertices inducing a connected subgraph using double edges must be a set of singleton-parts in some level of an iterated G-partition. In particular, this means that no two singleton parts from different layers can be adjacent by double edges. Since $G$ is edge-maximal, a maximal such set $S$ must be the entire set of singleton-parts in some level of a G-partition. By Theorem~\ref{Theorem:G-partition} and since $G$ is edge-maximal, such a set must be a double clique using the two colors of that layer. %\end{proof} Recall the definitions of $c_{1}$ and $c_{2}$ in \eqref{C1C2}. Let $t$ be the number of double cliques in $G$ and let $H_{1}, H_{2}, \dots, H_{t}$ be these double cliques with $|H_{i}| \geq |H_{i + 1}|$ for all $i$. \begin{claim}\label{Claim:LargeH1} $|H_{1}| \leq c_{1}n$. \end{claim} \begin{proof} Suppose $|H_{1}| > \frac{1 + 2\sqrt{7}}{9} n$ and that $H_{1}$ uses colors red and blue. Then all the green edges of $G$ must lie within $G \setminus H_{1}$ and between $H_{1}$ and $G \setminus H_{1}$. This means there are fewer than $$ \frac{1 + 2\sqrt{7}}{9} \left(1 - \frac{1 + 2\sqrt{7}}{9}\right)n^{2} + \frac{\left( 1 - \frac{1 + 2\sqrt{7}}{9} \right)^{2}}{2} n^{2} = \frac{26 - 2\sqrt{7}}{81} n^{2} $$ green edges, contradicting Proposition~\ref{Prop:LowBd}. \end{proof} Using Claim~\ref{Claim:LargeH1} and convexity, we can easily obtain an improved upper bound on $M$ as follows $$ M \leq \frac{ 2\frac{(c_{1} n)^{2}}{2} + 2\frac{(n - c_{1}n)^{2}}{2} + (c_{1}n)(n - c_{1}n) }{3} \sim 0.2633n^{2}. $$ This is still not the desired upper bound of about $0.25566n^{2}$ so we continue forcing structure on $G$. % Good to here. Although this next claim is not actually necessary for the remainder of the proof, it is an easy observation that shows $|H_{1}|$ must be close to the bound from Claim~\ref{Claim:LargeH1}. \begin{claim}\label{Claim:H1-0.6225} $|H_{1}| \geq 0.63n$. \end{claim} \begin{proof} Suppose $|H_{1}| < 0.63n$. Then, by convexity and Fact~\ref{Triple}, the total number of extra edges in $G$ is at most $$ {|H_{1}| \choose 2} + {n - |H_{1}| \choose 2} < \frac{(0.63n)^{2}}{2} + \frac{(0.37n)^{2}}{2} = 0.2669n^{2} $$ contradicting Fact~\ref{Fact:Extras}. \end{proof} Certainly $t \geq 2$ since $|H_{1}| < 0.7n$ by Claim~\ref{Claim:LargeH1}. Our next claim provides the main argument of the proof. \begin{claim}\label{Bigx} There are at least $c_{2}n$ vertices in $G \setminus (H_{1} \cup H_{2})$. \end{claim} \begin{proof} Let $x$ be chosen so that $xn = |G \setminus (H_{1} \cup H_{2})|$ and suppose $x < c_{2}$. If $H_{1}$ and $H_{2}$ use the same two colors, say red and blue, then the only green edges in $G$ are outside (or in between) $H_{1}$ and $H_{2}$. By Claim~\ref{Claim:LargeH1}, there must be at most $$ |H_{1}||H_{2}| + {xn \choose 2} + xn(|H_{1}| + |H_{2}|) < \frac{26-2\sqrt{7}}{81}n^{2} $$ green edges in the graph, a contradiction to Proposition~\ref{Prop:LowBd}. Without loss of generality, suppose $H_{1}$ uses red and blue while $H_{2}$ uses blue and green. Let $r$ be the number of red edges that appear in $G \setminus H_{1}$ and let $g$ be the number of green edges that appear in $G \setminus H_{2}$. Furthermore let $h$ be chosen so that $hn = |H_{1}|$. Then we get $|H_{2}| = (1 - x - h)n$. This means $$ r \geq \left( \frac{26 - 2\sqrt{7}}{81} - \frac{h^{2}}{2} \right)n^{2} $$ and $$ g \geq \left( \frac{26 - 2\sqrt{7}}{81} - \frac{(1 - x - h)^{2}}{2} \right) n^{2}. $$ On the other hand, there are fewer than \begin{equation}\label{TotalEdgesLeft} 2\frac{x^{2}}{2}n^{2} + xn(n - xn) + h(1 - x - h)n^{2} \end{equation} edges available in $G \setminus (E(H_{1}) \cup E(H_{2}))$. Since $r + g$ must be at most the quantity in \eqref{TotalEdgesLeft}, we get $$ \left( \frac{26 - 2\sqrt{7}}{81} - \frac{h^{2}}{2} \right)n^{2} + \left( \frac{26 - 2\sqrt{7}}{81} - \frac{(1 - x - h)^{2}}{2} \right) n^{2} \leq (x + h - xh - h^{2})n^{2} $$ which simplifies to $$ x \geq \frac{ \sqrt{23 - 8\sqrt{7}}}{9} = c_{2}, $$ completing the proof of Claim~\ref{Bigx}. \end{proof} \begin{claim}\label{BigH2} $|H_{1}| = c_{1}n$ and $|H_{2}| = c_{2}n$. \end{claim} \begin{proof} The number of extra edges is at most $n^2 \left( \frac{h_1^2}{2} + h_2^2 + \frac{(1-h_1-h_2)^2}{2} \right)$ subject to $h_1 \leq c_1$, $h_1+h_2 \leq c_2$, and $h_1 \geq h_2$, where $h_1n = |H_1|$ and $h_2n = |H_2|$. This can reach the required value only when $h_1 = c_1$, $h_2 = c_2$ and $h_3 = 1-c_1-c_2 = c_2$. %With $x \geq c_{2}n$, we know $|H_{1}| + |H_{2}| \leq (c_{1} + c_{2})n$. If this inequality was strict, we would have $t \geq 4$ and there would be fewer than $3 \left( \frac{26 - 2\sqrt{7}}{81} \right) n^{2}$ edges in the graph, contradicting Proposition~\ref{Prop:LowBd}. This means $|H_{1}| + |H_{2}| = (c_{1} + c_{2})n$. Since $|H_{1}| \leq c_{1}n$ by Claim~\ref{Claim:LargeH1}, we see that $|H_{2}| \geq c_{2}n$. If this inequality was strict, there would again be fewer than $3 \left( \frac{26 - 2\sqrt{7}}{81} \right) n^{2}$ edges in the graph, completing the proof of the claim. \end{proof} By Claims~\ref{Bigx} and~\ref{BigH2}, if $|H_{3}| < c_{2}n$, there would be fewer than $3 \left( \frac{26 - 2\sqrt{7}}{81} \right) n^{2}$ edges in the graph, contradicting Proposition~\ref{Prop:LowBd}. Thus, $t = 3$ and $|H_{3}| = c_{2}n$. Since this is precisely the structure of the graph constructed in Proposition~\ref{Prop:LowBd}, the proof of Theorem~\ref{Thm:Main} is complete. \qed \begin{thebibliography}{1} \bibitem{DM14} A.~Diwan and D.~Mubayi. \newblock Tur{\'a}n's theorem with colors. \newblock Manuscript, 2006. \url{http://www.math.cmu.edu/~mubayi/papers/webturan.pdf} \bibitem{G67} T.~Gallai. \newblock Transitiv orientierbare {G}raphen. \newblock {\em Acta Math. Acad. Sci. Hungar}, 18:25--66, 1967. \bibitem{HMP14} A.~Halperin, C.~Magnant, and K.~Pula. \newblock A decomposition of {G}allai multigraphs. \newblock {\em Discussiones Math. Graph Th.}, 34(1):160--172, 2014. \end{thebibliography} %\bibliography{ref} %\bibliographystyle{plain} \end{document}