On independent sets in hypergraphs

Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraëte

Research output: Contribution to journalArticlepeer-review

Abstract

The independence number α(H) 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 Hn is an n-vertex (r+1)-uniform hypergraph in which every r-element set is contained in at most d edges, where 0<d<n/(logn)3r2, then α(Hn)≥cr(ndlog<>nd)1/r where cr>0 satisfies cr~r/e as r→∞. The value of cr 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 r≥2 and all values of d∈ℕ, there are infinitely many Hn such that α(Hn)≤br(ndlog<>nd)1/r where br>0 depends only on r. In addition, for many values of d we show br~cr as r→∞, so the result is almost sharp for large r. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.

Original languageEnglish (US)
Pages (from-to)224-239
Number of pages16
JournalRandom Structures and Algorithms
Volume44
Issue number2
DOIs
StatePublished - Mar 2014

Keywords

  • Hypergraphs
  • Independent sets
  • Steiner systems

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On independent sets in hypergraphs'. Together they form a unique fingerprint.

Cite this