Independence in 5-uniform hypergraphs

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.8_n1+0.75_n2+0.7_n3+0.65_n4+_n4/300-(_n2+2_n3)/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.