Independence in 5-uniform hypergraphs

Alex Eustis, Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


In this paper we improve the best known lower bounds on independent sets in 5-uniform hypergraphs. Our proof techniques introduce two completely new methods in order to obtain our improvements on existing bounds. A subset of vertices in a hypergraph H is an independent set if it contains no edge of H. The independence number, α(H), of H is the maximum cardinality of an independent set in H. Let H be a connected 5-uniform hypergraph with maximum degree Δ(H). For i=1,...,Δ(H), let ni denote the number of vertices of degree i in H. We prove the following results. If Δ(H)≤3 and H is not one of two forbidden hypergraphs, then α(H)≥0.8;bsubesubbsubesubbsubesubbsubesubbsubesub)/130. If Δ(H)≤4 and H is not a given forbidden hypergraph, then α(H)≥0.8n1+0.75n2+0.7n3+0.65n4+n4/300-(n2+2n3)/260. For Δ(H)≥5, we define f(1)=0.8, f(2)=5.2/7, f(3)=0.7-1/130, f(4)=0.65+1/300 and for d≥5, we define f(d)=f(d-1)-(2f(d-1)-f(d-2))/(4d) and prove that α(H)≥Συ∈V(H)f(d(v)). Furthermore, we prove that we can find an independent set I in H in polynomial time, such that |I|≥Συ∈V(H)f(d(v)). Our results give support for existing conjectures and we pose several new conjectures which are of independent interest.

Original languageEnglish
Pages (from-to)1004-1027
Number of pages24
JournalDiscrete Mathematics
Issue number2
Publication statusPublished - 6 Feb 2016


  • Dual hypergraph
  • Hypergraph
  • Independence
  • Transversal

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Independence in 5-uniform hypergraphs'. Together they form a unique fingerprint.

Cite this