Chromatic Ramsey number of acyclic hypergraphs

Abstract

Suppose that $T$ is an acyclic $r$-uniform hypergraph, with $r\ge 2$. We define the ($t$-color) chromatic Ramsey number $\chi (T,t)$ as the smallest $m$ with the following property: if the edges of any $m$-chromatic $r$-uniform hypergraph are colored with $t$ colors in any manner, there is a monochromatic copy of $T$. We observe that $\chi (T,t)$ is well defined and $$\lceil \frac{R^r(T,t)-1}{r-1}\rceil +1\le \chi (T,t)\le |E(T){|}^t+1$$ where $R^r(T,t)$ is the $t$-color Ramsey number of $H$. We give linear upper bounds for $\chi (T,t)$ when T is a matching or star, proving that for $r\ge 2,k\ge 1,t\ge 1$, $\chi (M_k^r,t)\le (t-1)(k-1)+2k$ and $\chi (S_k^r,t)\le t(k-1)+2$ where $M_k^r$ and $S_k^r$ are, respectively, the $r$-uniform matching and star with $k$ edges. The general bounds are improved for $3$-uniform hypergraphs. We prove that $\chi (M_k^3,2)=2k$, extending a special case of Alon-Frankl-Lovász' theorem. We also prove that $\chi (S_2^3,t)\le t+1$, which is sharp for $t=2,3$. This is a corollary of a more general result. We define $H^{[1]}$ as the 1-intersection graph of $H$, whose vertices represent hyperedges and whose edges represent intersections of hyperedges in exactly one vertex. We prove that $\chi (H)\le \chi (H^{[1]})$ for any $3$-uniform hypergraph $H$ (assuming $\chi (H^{[1]})\ge 2$). The proof uses the list coloring version of Brooks' theorem.

arXiv comment10 pages