On Ryser’s Conjecture for $t$-Intersecting and Degree-Bounded Hypergraphs
| Autor: | Lilla Tóthmérész, Zoltán Király |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Hypergraph
Conjecture Degree (graph theory) Applied Mathematics 010102 general mathematics Complete graph 0102 computer and information sciences 01 natural sciences Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics Bounded function Affine plane (incidence geometry) Discrete Mathematics and Combinatorics Fraction (mathematics) Geometry and Topology 0101 mathematics Special case Mathematics |
| Zdroj: | Scopus-Elsevier |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/6448 |
| Popis: | A famous conjecture (usually called Ryser's conjecture) that appeared in the PhD thesis of his student, J. R. Henderson, states that for an $r$-uniform $r$-partite hypergraph $\mathcal{H}$, the inequality $\tau(\mathcal{H})\le(r-1)\!\cdot\! \nu(\mathcal{H})$ always holds. This conjecture is widely open, except in the case of $r=2$, when it is equivalent to Kőnig's theorem, and in the case of $r=3$, which was proved by Aharoni in 2001.Here we study some special cases of Ryser's conjecture. First of all, the most studied special case is when $\mathcal{H}$ is intersecting. Even for this special case, not too much is known: this conjecture is proved only for $r\le 5$ by Gyárfás and Tuza. For $r>5$ it is also widely open.Generalizing the conjecture for intersecting hypergraphs, we conjecture the following. If an $r$-uniform $r$-partite hypergraph $\mathcal{H}$ is $t$-intersecting (i.e., every two hyperedges meet in at least $t r/4$.Gyárfás showed that Ryser's conjecture for intersecting hypergraphs is equivalent to saying that the vertices of an $r$-edge-colored complete graph can be covered by $r-1$ monochromatic components.Motivated by this formulation, we examine what fraction of the vertices can be covered by $r-1$ monochromatic components of different colors in an $r$-edge-colored complete graph. We prove a sharp bound for this problem.Finally we prove Ryser's conjecture for the very special case when the maximum degree of the hypergraph is two. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|