SPARSE HYPERGRAPHS WITH LOW INDEPENDENCE NUMBER

Let K ((3))(4) denote the complete 3-uniform hypergraph on 4 vertices. Ajtai, Erdos, Komlos, and Szemeredi (1981) asked if there is a function omega(d) -> infinity such that every 3-uniform, K ((3))(4) -free hypergraph H with N vertices and average degree d has independence number at least N/d(1/2)omega(d). We answer this question by constructing a 3-uniform, K (4) ((3)) -free hypergraph with independence number at most 2N/d(1/2). We also provide counterexamples to several related conjectures and improve the lower bound of some hypergraph Ramsey numbers.