Coloring H-free hypergraphs

2008-02-26T00:00:00Z (GMT) by Tom Bohman Alan Frieze Dhruv Mubayi
<p>Fix <em>r</em> ≥ 2 and a collection of <em>r</em>-uniform hypergraphs . What is the minimum number of edges in an -free <em>r</em>-uniform hypergraph with chromatic number greater than <em>k</em>? We investigate this question for various . Our results include the following:</p> <ul> <li> <p>An (<em>r</em>,<em>l</em>)-system is an <em>r</em>-uniform hypergraph with every two edges sharing at most <em>l</em> vertices. For <em>k</em> sufficiently large, there is an (<em>r</em>,<em>l</em>)-system with chromatic number greater than <em>k</em> and number of edges at most <em>c</em>(<em>k</em><sup><em>r</em>−1</sup> log <em>k</em>)<sup><em>l</em>/(<em>l</em>−1)</sup>, where</p> <ul> <li></li> </ul> <p>This improves on the previous best bounds of Kostochka et al. (Random Structures Algorithms 19 (2001), 87–98). The upper bound is sharp apart from the constant <em>c</em> as shown in (Random Structures Algorithms 19 (2001) 87–98).</p> </li> <li> <p>The minimum number of edges in an <em>r</em>-uniform hypergraph with independent neighborhoods and chromatic number greater than <em>k</em> is of order <em>k</em><sup><em>r</em>+1/(<em>r</em>−1)</sup> log <sup><em>O</em>(1)</sup><em>k</em> as <em>k</em> ∞. This generalizes (aside from logarithmic factors) a result of Gimbel and Thomassen (Discrete Mathematics 219 (2000), 275–277) for triangle-free graphs.</p> </li> <li> <p>Let <em>T</em> be an <em>r</em>-uniform hypertree of <em>t</em> edges. Then every <em>T</em>-free <em>r</em>-uniform hypergraph has chromatic number at most 2(<em>r</em> − 1)(<em>t</em> − 1) + 1. This generalizes the well-known fact that every <em>T</em>-free graph has chromatic number at most <em>t</em>.</p> </li> </ul> <p>Several open problems and conjectures are also posed.</p>