Problem Statement
Let $r\geq 3$. For an $r$-uniform hypergraph $G$ let $\tau(G)$ denote the covering number (or transversal number), the minimum size of a set of vertices which includes at least one from each edge in $G$.
Determine the best possible $t$ such that, if $G$ is an $r$-uniform hypergraph $G$ where every subgraph $G'$ on at most $3r-3$ vertices has $\tau(G')\leq 1$, we have $\tau(G)\leq t$.
Determine the best possible $t$ such that, if $G$ is an $r$-uniform hypergraph $G$ where every subgraph $G'$ on at most $3r-3$ vertices has $\tau(G')\leq 1$, we have $\tau(G)\leq t$.
Categories:
Graph Theory
Progress
Erdős, Hajnal, and Tuza [EHT91] proved that this $t$ satisfies\[\frac{3}{16}r+\frac{7}{8}\leq t \leq \frac{1}{5}r.\]Source: erdosproblems.com/616 | Last verified: January 15, 2026