Chromatic Ramsey number of acyclic hypergraphs
Suppose that T is an acyclic r-uniform hypergraph, with r≥2. We define the (t-color) chromatic Ramsey number χ(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 χ(T,t) is well defined and ⌈r−1Rr(T,t)−1⌉+1≤χ(T,t)≤∣E(T)∣t+1 where Rr(T,t) is the t-color Ramsey number of H. We give linear upper bounds for χ(T,t) when T is a matching or star, proving that for r≥2,k≥1,t≥1, χ(Mkr,t)≤(t−1)(k−1)+2k and χ(Skr,t)≤t(k−1)+2 where Mkr and Skr are, respectively, the r-uniform matching and star with k edges. The general bounds are improved for 3-uniform hypergraphs. We prove that χ(Mk3,2)=2k, extending a special case of Alon-Frankl-Lovász' theorem. We also prove that χ(S23,t)≤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 χ(H)≤χ(H[1]) for any 3-uniform hypergraph H (assuming χ(H[1])≥2). The proof uses the list coloring version of Brooks' theorem.
