Matematičeskie zametki, Tome 61 (1997) no. 6, pp. 873-883
Citer cet article
V. E. Tarakanov. Estimates of the independence number of a hypergraph and the Ryser conjecture. Matematičeskie zametki, Tome 61 (1997) no. 6, pp. 873-883. http://geodesic.mathdoc.fr/item/MZM_1997_61_6_a7/
@article{MZM_1997_61_6_a7,
author = {V. E. Tarakanov},
title = {Estimates of the independence number of a hypergraph and the {Ryser} conjecture},
journal = {Matemati\v{c}eskie zametki},
pages = {873--883},
year = {1997},
volume = {61},
number = {6},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/MZM_1997_61_6_a7/}
}
TY - JOUR
AU - V. E. Tarakanov
TI - Estimates of the independence number of a hypergraph and the Ryser conjecture
JO - Matematičeskie zametki
PY - 1997
SP - 873
EP - 883
VL - 61
IS - 6
UR - http://geodesic.mathdoc.fr/item/MZM_1997_61_6_a7/
LA - ru
ID - MZM_1997_61_6_a7
ER -
%0 Journal Article
%A V. E. Tarakanov
%T Estimates of the independence number of a hypergraph and the Ryser conjecture
%J Matematičeskie zametki
%D 1997
%P 873-883
%V 61
%N 6
%U http://geodesic.mathdoc.fr/item/MZM_1997_61_6_a7/
%G ru
%F MZM_1997_61_6_a7
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$.