Edge-colored 3-uniform hypergraphs without rainbow paths of length 3 and its applications to Ramsey theory
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914140059074560 |
|---|---|
| author | Li, Xihe Wang, Runshan |
| author_facet | Li, Xihe Wang, Runshan |
| contents | Motivated by Ramsey theory problems, we consider edge-colorings of 3-uniform hypergraphs that contain no rainbow paths of length 3. There are three 3-uniform paths of length 3: the tight path $\mathcal{T}=\{v_1v_2v_3, v_2v_3v_4, v_3v_4v_5\}$, the messy path $\mathcal{M}=\{v_1v_2v_3, v_2v_3v_4, v_4v_5v_6\}$ and the loose path $\mathcal{L}=\{v_1v_2v_3,$ $v_3v_4v_5, v_5v_6v_7\}$. In this paper, we characterize the structures of edge-colored complete 3-uniform hypergraph $K_n^{(3)}$ without rainbow $\mathcal{T}$, $\mathcal{M}$ and $\mathcal{L}$, respectively. This generalizes a result of Thomason-Wagner on edge-colored complete graph $K_n$ without rainbow paths of length 3. We also obtain a multipartite generalization of these results.
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^{(3)}_n$ 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 reduce $f(H, G)$ to the 2-colored Ramsey number $R_2(H)$ of $H$, that is, $f(H, G)=R_2(H)$. Given a $3$-uniform hypergraph $G$ and an integer $n\geq |V(G)|$, the {\it anti-Ramsey number} $ar(n, G)$ is the minimum integer $k$ such that, in every edge-coloring of $K^{(3)}_n$ with at least $k$ colors, there is a rainbow copy of $G$. We show that $ar(n, \mathcal{T})=\left\lfloor\frac{n}{3}\right\rfloor+2$ for $n\geq 5$, $ar(n, \mathcal{M})=3$ for $n\geq 7$, and $ar(n, \mathcal{L})=n$ for $n\geq 7$. Our newly obtained Ramsey-type results extend results of Gyárfás-Lehel-Schelp and Liu on constrained Ramsey numbers, and improve a result of Tang-Li-Yan on anti-Ramsey numbers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18246 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Edge-colored 3-uniform hypergraphs without rainbow paths of length 3 and its applications to Ramsey theory Li, Xihe Wang, Runshan Combinatorics 05C55, 05D10, 05C35 Motivated by Ramsey theory problems, we consider edge-colorings of 3-uniform hypergraphs that contain no rainbow paths of length 3. There are three 3-uniform paths of length 3: the tight path $\mathcal{T}=\{v_1v_2v_3, v_2v_3v_4, v_3v_4v_5\}$, the messy path $\mathcal{M}=\{v_1v_2v_3, v_2v_3v_4, v_4v_5v_6\}$ and the loose path $\mathcal{L}=\{v_1v_2v_3,$ $v_3v_4v_5, v_5v_6v_7\}$. In this paper, we characterize the structures of edge-colored complete 3-uniform hypergraph $K_n^{(3)}$ without rainbow $\mathcal{T}$, $\mathcal{M}$ and $\mathcal{L}$, respectively. This generalizes a result of Thomason-Wagner on edge-colored complete graph $K_n$ without rainbow paths of length 3. We also obtain a multipartite generalization of these results. 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^{(3)}_n$ 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 reduce $f(H, G)$ to the 2-colored Ramsey number $R_2(H)$ of $H$, that is, $f(H, G)=R_2(H)$. Given a $3$-uniform hypergraph $G$ and an integer $n\geq |V(G)|$, the {\it anti-Ramsey number} $ar(n, G)$ is the minimum integer $k$ such that, in every edge-coloring of $K^{(3)}_n$ with at least $k$ colors, there is a rainbow copy of $G$. We show that $ar(n, \mathcal{T})=\left\lfloor\frac{n}{3}\right\rfloor+2$ for $n\geq 5$, $ar(n, \mathcal{M})=3$ for $n\geq 7$, and $ar(n, \mathcal{L})=n$ for $n\geq 7$. Our newly obtained Ramsey-type results extend results of Gyárfás-Lehel-Schelp and Liu on constrained Ramsey numbers, and improve a result of Tang-Li-Yan on anti-Ramsey numbers. |
| title | Edge-colored 3-uniform hypergraphs without rainbow paths of length 3 and its applications to Ramsey theory |
| topic | Combinatorics 05C55, 05D10, 05C35 |
| url | https://arxiv.org/abs/2510.18246 |