|
Estimates of the independence number of a hypergraph and the Ryser conjecture
V. E. Tarakanov Steklov Mathematical Institute, Russian Academy of Sciences
Abstract:
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$.
Received: 19.09.1996
Citation:
V. E. Tarakanov, “Estimates of the independence number of a hypergraph and the Ryser conjecture”, Mat. Zametki, 61:6 (1997), 873–883; Math. Notes, 61:6 (1997), 731–738
Linking options:
https://www.mathnet.ru/eng/mzm1571https://doi.org/10.4213/mzm1571 https://www.mathnet.ru/eng/mzm/v61/i6/p873
|
|