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 HH is an independent set if it contains no edge of HH. The independence number, α(H)α(H), of HH is the maximum cardinality of an independent set in HH. Let HH be a connected 5-uniform hypergraph with maximum degree  Δ(H)Δ(H). For i=1,…,Δ(H)i=1,…,Δ(H), let nini denote the number of vertices of degree  ii in HH. We prove the following results. If Δ(H)≤3Δ(H)≤3 and HH is not one of two forbidden hypergraphs, then α(H)≥0.8n1+0.75n2+0.7n3+(n1−n3)/130α(H)≥0.8n1+0.75n2+0.7n3+(n1−n3)/130. If Δ(H)≤4Δ(H)≤4 and HH is not a given forbidden hypergraph, then α(H)≥0.8n1+0.75n2+0.7n3+0.65n4+n4/300−(n2+2n3)/260α(H)≥0.8n1+0.75n2+0.7n3+0.65n4+n4/300−(n2+2n3)/260. For Δ(H)≥5Δ(H)≥5, we define f(1)=0.8f(1)=0.8, f(2)=5.2/7f(2)=5.2/7, f(3)=0.7−1/130f(3)=0.7−1/130, f(4)=0.65+1/300f(4)=0.65+1/300 and for d≥5d≥5, we define f(d)=f(d−1)−(2f(d−1)−f(d−2))/(4d)f(d)=f(d−1)−(2f(d−1)−f(d−2))/(4d) and prove that α(H)≥∑v∈V(H)f(d(v))α(H)≥∑v∈V(H)f(d(v)). Furthermore, we prove that we can find an independent set II in HH in polynomial time, such that |I|≥∑v∈V(H)f(d(v))|I|≥∑v∈V(H)f(d(v)). Our results give support for existing conjectures and we pose several new conjectures which are of independent interest.