Edge-colored 3-uniform hypergraphs without rainbow paths of length 3 and applications to Ramsey theory

Abstract

Motivated by problems in Ramsey theory, we study edge-colorings of 3-uniform hypergraphs that contain no rainbow paths of length 3. We consider the following three natural 3-uniform paths of length 3: the tight path $\mathcal{T}=\{v_1{v}_2{v}_3,v_2{v}_3{v}_4,v_3{v}_4{v}_5\}$, the messy path $\mathcal{M}=\{v_1{v}_2{v}_3,v_2{v}_3{v}_4,v_4{v}_5{v}_6\}$ and the loose path $\mathcal{L}=\{v_1{v}_2{v}_3,$ $v_3{v}_4{v}_5,v_5{v}_6{v}_7\}$. In this paper, we characterize the structures of rainbow $\mathcal{T}$-free, rainbow $\mathcal{M}$-free and rainbow $\mathcal{L}$-free edge-colorings of complete 3-uniform hypergraphs $K_n^{(3)}$, respectively. This extends a result of Thomason and Wagner (2007) on edge-colored complete graphs $K_n$ without rainbow paths of length 3. As applications, we obtain several Ramsey-type results. Given two $3$-uniform hypergraphs $H$ and $G$, the {\it constrained Ramsey number} $f(H,G)$ is defined as the minimum integer $n$ such that in every edge-coloring of $K_n^{(3)}$ with any number of colors, there is either a monochromatic copy of $H$ or a rainbow copy of $G$. For $G\in \{\mathcal{T},\mathcal{M},\mathcal{L}\}$ and infinitely many 3-uniform hypergraphs $H$, we show that $f(H,G)=R_2(H)$, where $R_2(H)$ is the 2-colored Ramsey number of $H$. Given a $3$-uniform hypergraph $G$ and an integer $n\ge |V(G)|$, the {\it anti-Ramsey number} $ar(n,G)$ is the minimum integer $k$ such that in every edge-coloring of $K_n^{(3)}$ with at least $k$ colors, there is a rainbow copy of $G$. We show that $ar(n,\mathcal{T})=\lfloor \frac{n}{3}\rfloor +2$ for $n\ge 5$, $ar(n,\mathcal{M})=3$ for $n\ge 7$, and $ar(n,\mathcal{L})=n$ for $n\ge 7$. Our Ramsey-type results extend results of Gyárfás, Lehel and Schelp (2007) and of Liu (2024) on constrained Ramsey numbers, and improve a result of Tang, Li and Yan (2022) on anti-Ramsey numbers.

29 pages; 2 figures