Independence in 5-uniform hypergraphs

Alex Eustis, Michael A. Henning, Anders Yeo*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

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.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
JournalDiscrete Mathematics
Volume339
Issue number2
Pages (from-to)1004-1027
ISSN0012-365X
DOIs
Publication statusPublished - 2016
Externally publishedYes

Keywords

  • Dual hypergraph
  • Hypergraph
  • Independence
  • Transversal

Fingerprint

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

Cite this