%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % On multicolor Ramsey number for 3-paths of length three % % % % by % % % % Tomasz Luczak and Joanna Polcyn-Lewandowska % % % % % % % % sub. December 5, 2016, updated January 28, 2017 % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt]{article} \usepackage{e-jc} %\usepackage[a4paper,hmargin={3.5cm,3.5cm},vmargin={3.5cm,3.5cm}]{geometry} %PACKAGES \usepackage{amsthm,amssymb,amsmath,amscd} \usepackage{amsthm} %\usepackage{stmaryrd,color} \usepackage{pgf, tikz} %\usepackage{tkz-berge} \usepackage{graphicx,subcaption} %\usepackage[cp1250]{inputenc} %\usepackage[T1]{fontenc} %\usepackage[all,arc]{xy} %\usepackage[mathscr]{euscript} %\usepackage{verbatim} %\usepackage{setspace} %\usepackage{float} \usepackage{verbatim} %\singlespacing %\onehalfspacing %\usepackage{textcomp} %MACROS %THEOREMS \theoremstyle{definition} \newtheorem{definition}{Definition}%[section] %\newtheorem{axiom}{Axiom} \theoremstyle{plain} \newtheorem{theorem}[definition]{Theorem} \newtheorem*{lemman}%[definition] {Lemma} \newtheorem*{theoremn}%[definition] {Theorem} \newtheorem{lemma}[definition]{Lemma} \newtheorem{cor}[definition]{Corollary} \newtheorem{proposition}[definition]{Proposition} \newtheorem{example}[definition]{Example} \newtheorem{fact}[definition]{Fact} \newtheorem{claim}[definition]{Claim} \newtheorem*{conj}%[definition] {Conjecture} \theoremstyle{remark} \newtheorem{remark}[definition]{Remark} \newtheorem{question}[definition]{Question} \newtheorem{problem}[definition]{Problem} \newtheorem{counterexample}[definition]{Counterexample} \newcommand{\pp}{P} \hyphenation{e-li-mi-nate essen-tia-lly corres-pon-ding} %DOCUMENT BODY \title{On the multicolor Ramsey number\\ for 3-paths of length three} \author{Tomasz \L{}uczak\thanks{Partially supported by NCN grant 2012/06/A/ST1/00261.}\\ \small A. Mickiewicz University\\[-0.8ex] \small Faculty of Mathematics and Computer Science\\ \small ul.~Umultowska 87,\\ \small 61-614 Pozna\'n, Poland\\ \small\tt tomasz@amu.edu.pl\\ \and Joanna Polcyn\\ \small A. Mickiewicz University\\[-0.8ex] \small Faculty of Mathematics and Computer Science\\ \small ul.~Umultowska 87,\\ \small 61-614 Pozna\'n, Poland\\ \small\tt joaska@amu.edu.pl\\ } \date{\dateline{January 28, 2017}\\ \small Mathematics Subject Classifications: 05D10, 05C38, 05C55, 05C65 } \begin{document} \maketitle \begin{abstract} We show that if we color the hyperedges of the complete $3$-uniform hypergraph on $2n+\sqrt{18n+1}+2$ vertices with $n$ colors, then one of the color classes contains a loose path of length three. \end{abstract} %\maketitle %\section{Introduction} Let $\pp$ denote the $3$-uniform path of length three by which we mean the only connected 3-uniform hypergraph on seven vertices with the degree sequence $(2,2,1,1,1,1,1)$. By $R(\pp;n)$ we denote the multicolored Ramsey number for $\pp$ defined as the smallest number $N$ such that each coloring of the hyperedges of the complete 3-uniform hypergraph $K^{(3)}_N$ with $n$ colors leads to a monochromatic copy of $\pp$. It is easy to check that $R(\pp;n)\ge n+6$ (see \cite{GR, J}), and it is believed that in fact equality holds, i.e. \begin{equation*}\label{eq1} R(\pp;n)= n+6. \end{equation*} Gy\'{a}rf\'{a}s and Raeisi \cite{GR} proved, among many other results, that $R(\pp;2)=8$. Their theorem was extended by Omidi and Shahsiah~\cite{Omidi} to loose paths of arbitrary lengths, but still only for the case of two colors. On the other hand, in a series of papers \cite{J, JPR, PR, P} it was verified that $R(\pp;n)=n+6$ for all $3\le n\le 10$. % So far the above conjecture has been confirmed for all $n\le 10$ (see \cite{GR,J,JPR,P,PR}). Note that from the fact that for $N\ge 8$ the largest $\pp$-free $3$-uniform hypergraph on $N$ vertices contains at most $\binom {N-1}2$ hyperedges (see \cite{JPRt}), it follows that for $n\ge 3$ we have (see \cite{GR}) \begin{equation*}\label{eq2} R(\pp;n)\le 3n +1. \end{equation*} Our main goal is to improve the above bound. \begin{theoremn}\label{thm:main} $R(\pp;n)\le 2n+\sqrt{18n+1}+2$. \end{theoremn} %\section{Main Lemma} Let $C$ denote the (loose) $3$-uniform $3$-cycle, i.e. the only $3$-uniform linear hypergraph with six vertices and three hyperedges. Furthermore, let $F$ be the $3$-uniform hypergraph on vertices $v_1,v_2,v_3,v_4,v_5$ such that the first four of these vertices span a clique, and $v_5$ is contained in the following three hyperedges: $v_1v_2v_5$, $v_2v_3v_5$, and $v_3v_4v_5$. The following fact will be crucial for our argument. \begin{lemman}\label{l:main} Let $H$ be a $3$-uniform $\pp$-free hypergraph on $n\ge 5$ vertices. Then we can delete from $H$ fewer than $3n$ hyperedges in such a way that the resulting hypergraph contains no copies of $C$ and $F$. \end{lemman} \begin{proof} Let us first consider components containing $C$. Jackowska, Polcyn and Ruci\'nski \cite{JPR} showed that each such component of $H$ on $n_i$ vertices has at most $3n_i-8< 3n_i$ hyperedges, provided $n_i\ge 7$. Furthermore, from the complete 3-uniform hypergraph on $n_i=6$ vertices it is enough to delete $10<3n_i$ hyperedges to get a star, which clearly contains no copies of $C$ and $F$. Hence, to get rid of all copies of $C$ (and $F$ in components containing $C$) it is enough to remove fewer than $3n'$ hyperedges from components containing them, where $n'$ denotes the number of vertices in these components combined. Now let us consider components containing $F$ but not $C$. It is easy to check by direct inspection that any hyperedge $e$ which shares with $F$ just one vertex would create a copy of $P$. Moreover, any hyperedge $e'$ which shares with $F$ two vertices would create a copy of $C$. Consequently, each copy of $F$ in a $\pp$-free, $C$-free 3-uniform hypergraph is contained in a component on 5 vertices. Note that each such component has at most $\binom 53=10$ hyperedges and we can destroy $F$ by removing just $4< 3\cdot 5$ of them. Thus, one can delete from $H$ fewer than $3n$ hyperedges to destroy all copies of $C$ and~$F$. \end{proof} \begin{proof}[Proof of Theorem] Consider a coloring of the hyperedges of the complete 3-uniform hypergraph on $2n+m$ vertices with $n$ colors. Assume that no color class contains a copy of $P$. Then, by the lemma, we can mark as `blank' fewer than $r=3(2n+m)n$ hyperedges of the hypergraph in such a way that when we ignore blank hyperedges no color class contains a monochromatic copy of $C$ and~$F$. Let us color a pair of vertices $vw$ with a color $s$, $s=1,2,\dots,n$, if there exist at least three hyperedges of color $s$, $s=1,2,\dots,n$, which contain this pair. If there are many such colors we choose any of them; if there are none we leave $vw$ uncolored. Note that every uncolored pair must be contained in at least $m-2$ blank hyperedges. Consequently, fewer than $3r/(m-2)$ pairs remain uncolored. But then there exists a color $t$, $t=1,2,\dots,n$, such that there are more than $$\bigg[\binom{2n+m}{2}-\frac{3r}{m-2}\bigg]\bigg/n=2n+m+(2n+m)\Big[\frac{m-1}{2n}-\frac{9}{m-2}\Big] $$ pairs colored with $t$. If $m\ge \sqrt{18n+1}+2$, then $$\frac{m-1}{2n}-\frac{9}{m-2}> 0\,, $$ and the graph $G_t$ spanned by these pairs has more edges than vertices. But this means that $G_t$ contains a path of length 3, i.e. there are vertices $v_1,v_2, v_3,v_4$ and a color $t$ such that each of the three pairs $v_1v_2$, $v_2v_3$, $v_3v_4$ is contained in at least three different hyperedges colored with $t$. We shall show that this leads to a contradiction. Indeed, let $H_t$ be a hypergraph spanned by hyperedges colored with the $t$th color. Observe first that since $v_2v_3$ is contained in three different hyperedges of $H_t$ there must be one which is different from $v_1v_2v_3$ and $v_2v_3v_4$; let us call it $v_2v_3v_5$ where $v_5\neq v_1,v_2,v_3,v_4$. Furthermore, $v_1v_2$ must be contained in a hyperedge $v_1v_2w$ of $H_t$ where $w\neq v_3,v_5$, while $v_3v_4$ is contained in some $v_3v_4u$, where $u\neq v_2,v_5$. Note now that if $w\neq v_4$ and $u\neq w,v_1$, then $H_t$ contains a copy of $P$ which contradicts the fact that it is $P$-free. The case $w=u\neq v_1,v_4$, as well as the cases $w=v_4$, $u\neq v_1$, and $u=v_1$, $w\neq v_4$, would lead to a cycle $C$. Finally, if the only possible choices for $w$ and $u$ are $w=v_4$ and $u=v_1$, then the vertices $v_1,\dots, v_5$ span a copy of $F$, so we arrive at a contradiction again. \end{proof} {\sl Remark}\ The bound $3n$ given in the lemma is rather crude. Using the fact that each component of $H$ on $n_i$ vertices containing $C$ and two disjoint hyperedges has at most $n_i+5$ hyperedges, provided $n_i\ge 7$ (see \cite{P}) and by careful analysis of 3-uniform intersecting families (see \cite{EKR,HK,HM,KM,PRIF}) one can improve it by a constant factor and, consequently, improve by a constant factor the second order term in the estimate for $R(P;n)$. Nonetheless our method, based on the reduction of the hypergraph problem to the analogous problem for graphs, clearly cannot be used to produce an upper bound better than $2n$. However, we still believe that $n+6$ could be the correct value for $R(P;n)$. \bigskip {\bf Acknowledgement.} We wish to thank Andrzej Ruci\'nski for stimulating conversations and the anonymous referee for his/her comments. \bibliographystyle{plain} \begin{thebibliography}{99} \bibitem{EKR} P.~Erd\H{o}s, C.~Ko, R.~Rado, {\sl Intersection theorems for systems of finite sets}, {Quart.\ J.\ Math.\ Oxford Ser.\ (2)}, 12 (1961), 313--320. \bibitem{GR} A.~Gy\'{a}rf\'{a}s, G.~Raeisi, {\sl The Ramsey number of loose triangles and quadrangles in hypergraphs}, {Electron.\ J.\ Combin.}, 19(2) (2012), \# R30. \bibitem{HK} J.~Han, Y.~Kohayakawa, { \sl Maximum size of a non-trivial intersecting uniform family which is not a subfamily of the Hilton-Milner family}, {Proc.\ Amer.\ Math.\ Soc.}, 145(1) (2017), 73--87. \bibitem{HM} A.~J.~W.~Hilton, E.~C.~Milner, {\sl Some intersection theorems for systems of finite sets}, {Quart.\ J.\ Math.\ Oxford Ser.\ (2)}, 18 (1967), 369--384. \bibitem{J} E.~Jackowska, {\sl The 3-color Ramsey number for a 3-uniform loose path of length 3}, {Australas.\ J.\ Combin}, 63(2) (2015), 314--320. \bibitem{JPRt} E.~Jackowska, J.~Polcyn, A.~Ruci\'nski, {\sl Tur\'an numbers for 3-uniform linear paths of length 3}, {Electron.\ J.\ Combin.}, 23(2) (2016), \#P2.30 \bibitem{JPR} E.~Jackowska, J.~Polcyn, A.~Ruci\'nski, {\sl Multicolor Ramsey numbers and restricted Tur\'an numbers for the loose 3-uniform path of length three}, {\tt arXiv:1506.03759v1}. \bibitem{KM} A.~Kostochka, D.~Mubayi, {\sl The structure of large intersecting families}, {Proc.\ Amer.\ Math.\ Soc.}, to appear, {\tt arXiv:1602.01391}. \bibitem{Omidi} G.~R.~Omidi, M.~Shahsiah, {\sl Ramsey Numbers of 3-Uniform Loose Paths and Loose Cycles}, {J.\ Combin.\ Theory Ser. A}, 121 (2014), 64--73. \bibitem{P} J.~Polcyn, {\sl One more Tur\'an number and Ramsey number for the loose 3-uniform path of length three}, {Discuss.\ Math.\ Graph Theory}, to appear, {\tt arXiv:1511.09073}. \bibitem{PRIF} J.~Polcyn, A.~Ruci\'nski, {\sl A hierarchy of maximal intersecting triple systems}, {Opuscula Math.}, to appear, {\tt arXiv:1608.06114}. \bibitem{PR} J.~Polcyn, A.~Ruci\'nski, {\sl Refined Tur\'an numbers and Ramsey numbers for the loose 3-uniform path of length three}, {Discrete Math.}, 340 (2017), 107--118. \end{thebibliography} \end{document}