Independent Sets in Sparse Hypergraphs
Cooper, Jeffrey R.
MetadataShow full item record
We study the independence number and chromatic number of hypergraphs which contain no copies of a fixed subgraph. Let H be a 3-uniform hypergraph with maximum degree d. We show that if H contains no triangles, then the chromatic number of H is O(sqrt(d/log(d))). On the other hand, we give examples of hypergraphs which contain no copies of a fixed subgraph yet have independence number at most O(sqrt(d)).