2009/01/14 by Tom Bohman, Alan Frieze, Bohman, Tom +3
Computer Science · Engineering · Mathematics · #05C65 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO #msc:05C65
paper · pdf · doi:10.48550/arxiv.0901.2061
openalex publication_date 2009/01/14 · arxiv created 2009/02/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Fix r ≥ 2 and a collection of r-uniform hypergraphs \cH. What is the minimum number of edges in an \cH-free r-uniform hypergraph with chromatic number greater than k. We investigate this question for various \cH. Our results include the following: An (r,l)-system is an r-uniform hypergraph with every two edges sharing at most l vertices. For k sufficiently large, the minimum number of edges in an (r,l)-system with chromatic number greater than k is at most c(kr-1log k)l/(l-1), where c<... This improves on the previous best bounds of Kostochka-Mubayi-Rödl-Tetali \citeKMRT. The upper bound is sharp aside from the constant c as shown in \citeKMRT. The minimum number of edges in an r-uniform hypergraph with independent neighborhoods and chromatic number greater than k is of order kr+1/(r-1) as k → ∞. This generalizes (aside from logarithmic factors) a result of Gimbel and Thomassen \citeGT for triangle-free graphs. Let T be an r-uniform hypertree of t edges. Then every T-free r-uniform hypergraph has chromatic number at most p(t), where p(t) is a polynomial in t. This generalizes the well known fact that every T-free graph has chromatic number at most t. Several open problems and conjectures are also posed.