Estimates of the independence number of a hypergraph and the Ryser conjecture

V. E. Tarakanov

Matematičeskie zametki, Tome 61 (1997) no. 6, pp. 873-883

Résumé

Consider a hypergraph $H$ with $n$ vertices and $m$ edges. Suppose that its edges contain at most $r$ vertices, $r\ge2$, and the degrees of its vertices do not exceed $\delta\ge2$. Let $\tau(H)$ be the transversal number of the graph $H$ and $\mu(H)$ be its independence number, i.e., the maximal number of pairwise nonintersecting edges containing $r$ vertices. We strengthen the known estimate $\mu\ge(\delta n-(r-1)m)/(\delta r-r+1)$ for the case in which $H$ is a pseudograph and the maximal degree of its vertices equals $\Delta$, $2\delta-2\ge\Delta$ (there is a similar result for graphs). Then we use the sharpened estimate to prove the well known Ryser conjecture on $r$-partite $r$-uniform hypergraphs $H$: this conjecture states that $\tau(H)\le(r-1)\mu(H)$, and we prove it for $\delta$-regular $H$, where $2\le\delta\le r-1$.