A Lower Bound on the Independence Number of General Hypergraphs in Terms of the Degree Vectors 


Torsten Thiele 
Fachbereich Mathematik und Informatik
Freie Universität Berlin
email: thiele@math.fu-berlin.de
Report B 95-02
März 1995 

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-95-02.ps.gz
A Lower Bound on the Independence Number of General Hypergraphs in Terms of the Degree Vectors This paper proves a lower bound on the independence number of general hypergraphs in terms of the degree vectors. The degree vector of a vertex $v$ is given by $d(v)=(d_1(v), d_2(v),\ldots)$ where $d_m(v)$ is the number of edges of size $m$ containing $v$. We define a function $f$ with the property that any hypergraph $H=(V,E)$ satisfies $\alpha(H)\geq \sum_{v\in V} f(d(v))$. This lower bound is sharp when $H$ is a matching. Furthermore this bound generalizes known bounds of Wei/Caro and Caro/Tuza for ordinary graphs and uniform hypergraphs.