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

Autor: V. E. Tarakanov
Rok vydání: 1997
Předmět:
Zdroj: Mathematical Notes. 61:731-738
ISSN: 1573-8876
0001-4346
Popis: Consider a hypergraphH withn vertices andm edges. Suppose that its edges contain at mostr vertices,r≥2, and the degrees of its vertices do not exceed δ, δ≥2. Let τ(H) be the transversal number of the graphH and μ(H) be its independence number, i.e., the maximal number of pairwise nonintersecting edges containingr vertices. We strengthen the known estimate μ≥(δn−(r−1)m)/(δr−r+1) for the case in whichH is a pseudograph and the maximal degree of its vertices equals Δ, 2δ−2≥Δ (there is a similar result for graphs). Then we use the sharpened estimate to prove the well known Ryser conjecture onr-partiter-uniform hypergraphsH: this conjecture states that τ(H)≤(r−1)μ(H), and we prove it for δ-regularH, where 2≤δ≤r−1.
Databáze: OpenAIRE
Externí odkaz: