List coloring triangle‐free hypergraphs. Issue 3 (11th June 2014) - Cooper, Jeff; Mubayi, Dhruv
Abstract A triangle in a hypergraph is a collection of distinct vertices u, v, w and distinct edges e, f, g with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw8cg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />u, v∈e, v, w∈f</alternatives>, <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw89c" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />w, u∈g</alternatives> and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw8bx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />u, v, w∩e∩f∩g=∅</alternatives>. Johansson [Tech. report (1996)] proved that every triangle‐free graph with maximum degree Δ has list chromatic number <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7h5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />O(Δ/logΔ)</alternatives>. Frieze and Mubayi (Electron J Comb 15 (2008), 27) proved that every linear (meaning that every two edges share at most one vertex) triangle‐free triple system with maximum degree Δ has chromatic number <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7gm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />O(Δ/logΔ)</alternatives>. The restriction to linear triple systems was crucial to their proof. We provide a common generalization of both these results for rank 3 hypergraphs (edges have size 2 or 3). Our result removes the linear restriction from 8, while reducing to the (best possible) result [Johansson, Tech. report (1996)] for graphs. In addition, our result provides a positive answer to a restricted version of a question of Ajtai Erdős, Komlós, and Szemerédi (combinatorica 1 (1981), 313–317) concerning sparse 3‐uniform hypergraphs. As an application, we prove that if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7f2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />C3</alternatives> is the collection of 3‐uniform triangles, then the Ramsey number <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7dh" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />R(C3, Kt3)</alternatives> satisfies <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7nc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />at3/2(logt)3/4≤R(C3, Kt3)≤bt3/2(logt)1/2</alternatives> for some positive constants a and b. The upper bound makes progress towards the recent conjecture of Kostochka, Mubayi, and Verstraëte (J Comb Theory Ser A 120 (2013), 1491–1507) that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7mt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />R(C3, Kt3)=o(t3/2)</alternatives> where C3 is the linear triangle. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 487–519, 2015