Open-access mathematical research insights
About Contact
Home / Erdos Problems / Problem #616

Problem #616: Let $r\geq 3$. For an $r$-uniform hypergraph $G$ let...

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...

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$.
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

Stay Updated

Get weekly digests of new research insights delivered to your inbox.