We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Transversals in regular uniform hypergraphs.
- Authors
Henning, Michael A.; Yeo, Anders
- Abstract
The transversal number τ(H) $\tau (H)$ of a hypergraph H $H$ is the minimum number of vertices that intersect every edge of H $H$. This notion of transversal is fundamental in hypergraph theory and has been studied a great deal in the literature. A hypergraph H $H$ is r $r$‐regular if every vertex of H $H$ has degree r $r$, that is, every vertex of H $H$ belongs to exactly r $r$ edges. Further, H $H$ is k $k$‐uniform if every edge of H $H$ has size k $k$, and so every edge of H $H$ is a k $k$‐element subset of V(H) $V(H)$. For r≥2 $r\ge 2$ and k≥2 $k\ge 2$, let Hr,k,nreg ${{\rm{ {\mathcal H} }}}_{r,k,n}^{\text{reg}}$ be the class of all r $r$‐regular k $k$‐uniform hypergraphs of order n $n$. In this paper we study the problem posed by Tuza to determine or estimate the best possible constants θr,k ${\theta }_{r,k}$ (which depend only on r $r$ and k $k$) for each r≥2 $r\ge 2$ and k≥2 $k\ge 2$, such that τ(H)≤θr,k×n $\tau (H)\le {\theta }_{r,k}\times n$ for all H∈Hr,k,nreg $H\in {{\rm{ {\mathcal H} }}}_{r,k,n}^{\text{reg}}$. These constants are given by θr,k=supτ(H)n ${\theta }_{r,k}=\text{sup}\frac{\tau (H)}{n}$, where the supremum is taken over all H∈Hr,k,nreg $H\in {{\rm{ {\mathcal H} }}}_{r,k,n}^{\text{reg}}$. Tuza presented closed formulas when r=2 $r=2$ or k=2 $k=2$, and showed that θr,2=rr+1 ${\theta }_{r,2}=\frac{r}{r+1}$ for all r≥2 $r\ge 2$, θ2,k=43k ${\theta }_{2,k}=\frac{4}{3k}$ for k≥2 $k\ge 2$ even, and θ2,k=43k+1 ${\theta }_{2,k}=\frac{4}{3k+1}$ for k≥3 $k\ge 3$ odd. We conjecture that θ3,k≤32k ${\theta }_{3,k}\le \frac{3}{2k}$ for all k≥2 $k\ge 2$ and that θ4,k≤127k ${\theta }_{4,k}\le \frac{12}{7k}$ for all k≥2 $k\ge 2$. We show that both these conjectures hold for k∈{2,3,4,6} $k\in \{2,3,4,6\}$. Moreover we show, for example, that θ3,3=12 ${\theta }_{3,3}=\frac{1}{2}$ and θ4,3=59 ${\theta }_{4,3}=\frac{5}{9}$. We show that for every 0<ε<1 $0\lt \varepsilon \lt 1$ and for sufficiently large r $r$ and k $k$, the growth of θr,k ${\theta }_{r,k}$ is given by ε1+ln(r)k≤θr,k≤1+ln(r)k $\varepsilon \left(\frac{1+\mathrm{ln}(r)}{k}\right)\le {\theta }_{r,k}\le \frac{1+\mathrm{ln}(r)}{k}$.
- Subjects
HYPERGRAPHS; TRANSVERSAL lines; PROJECTIVE planes
- Publication
Journal of Graph Theory, 2024, Vol 105, Issue 3, p468
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.23051