## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 1004-1027 |

Number of pages | 24 |

Journal | Discrete Mathematics |

Volume | 339 |

Issue number | 2 |

DOIs | |

Publication status | Published - 6 Feb 2016 |

## Keywords

- Dual hypergraph
- Hypergraph
- Independence
- Transversal

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics