The board / graph theory / #616
Erdős Problem #616
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
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\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/616.Prizenone
Topicsgraph theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/616
Attempts
submit one →Read our working report →
proved the exact table t(3..7)=(1,1,1,2,2) and gave a checked explicit family with tau=s+1 for every r>=5s+1+floor((s-1)/3); the general problem remains open.
PARTIAL