Geodesic
Estimates of the independence number of a hypergraph and the Ryser conjecture
Matematičeskie zametki, Tome 61 (1997) no. 6, pp. 873-883.

Voir la notice de l'article provenant de la source Math-Net.Ru

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$. 
@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},
     publisher = {mathdoc},
     volume = {61},
     number = {6},
     year = {1997},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_1997_61_6_a7/
%G ru
%F MZM_1997_61_6_a7
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/

[1] Tarakanov V. E., “O maksimalnoi glubine odnogo klassa $(0,1)$-matrits”, Matem. sb., 75 (117) (1968), 4–14 | MR | Zbl

[2] Tarakanov V. E., “Maksimalnaya glubina proizvolnykh klassov $(0,1)$-matrits i nekotorye ee primeneniya”, Matem. sb., 92 (134) (1973), 472–490 | MR | Zbl

[3] Bollobás B., Extremal graph theory, Acad. Press, London, 1978 | Zbl

[4] Tuza Zs., “Ryser's conjecture for transversals of $r$-partite hypergraphs”, Ars Combin., 16 (B) (1983), 201–209 | MR | Zbl

[5] Haxell P. E., “A note on a conjecture of Ryser”, Period. Math. Hungar., 30:1 (1995), 73–79 | DOI | MR | Zbl

[6] Raizer G. Dzh., Kombinatornaya matematika, Mir, M., 1966