On independent sets in hypergraphs

The independence number of a hypergraph H is the size of a largest set of vertices containing no edge of H . In this paper, we prove that if H n is an n ‐vertex ‐uniform hypergraph in which every r ‐element set is contained in at most d edges, where , then urn:x-wiley::media:rsa20453:rsa20453-math-0004 where satisfies as . The value of c r improves and generalizes several earlier results that all use a theorem of Ajtai, Komlós, Pintz, Spencer and Szemerédi (J Comb Theory Ser A 32 (1982), 321–335). Our relatively short proof extends a method due to Shearer (Random Struct Algorithms 7 (1995), 269–271) and Alon (Random Struct Algorithms 9 (1996), 271–278). The above statement is close to best possible, in the sense that for each and all values of , there are infinitely many H n such that urn:x-wiley::media:rsa20453:rsa20453-math-0010 where depends only on r . In addition, for many values of d we show as , so the result is almost sharp for large r . We give an application to hypergraph Ramsey numbers involving independent neighborhoods.