Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 644

claims/: The 1 claim page of Problem 644, one per claimant's result; the problem's standing derives from them.

Statement. Let $f(k,r)$ be minimal such that if $A_1,A_2,\ldots$ is a family of sets, all of size $k$ , such that for every collection of $r$ of the $A_is$ there is some pair $\{x,y\}$ which intersects all of the $A_j$ , then there is some set of size $f(k,r)$ which intersects all of the sets $A_i$ . Is it true that

f(k,7)=(1+o(1))\frac{3}{4}k?

Is it true that for any $r\geq 3$ there exists some constant $c_r$ such that

f(k,r)=(1+o(1))c_rk?

Status. Open.

Source. erdosproblems.com/644, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #644, https://www.erdosproblems.com/644.

References.

[EFKT92] Erdős, P. and Fon-Der-Flaass, D. and Kostochka, A. V. and Tuza, Zs., Small transversals in uniform hypergraphs. Siberian Adv. Math. (1992), 82-88.

Formalization. Statement in formal-conjectures.

Current assessment

The status above is the site's label. One claim page, the exact values of Erdős, Fon-Der-Flaass, Kostochka and Tuza, records the refereed values $f(k,3)=2k$ , $f(k,4)=\lceil3k/2\rceil$ , $f(k,5)=\lceil5k/4\rceil$ and $f(k,6)=k$ , an accepted partial claim that answers the second question yes for $r=3,4,5,6$ and covers neither the $r=7$ asymptotic nor the second question for $r\ge7$ , so the derived standing is open; the site's commentary prints the two middle values with floors, which fail already for $k=3$ . This page records no current literature search or independent assessment of proof coverage.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (30)

problems/set_systems/E0644/claims Set Systems, Designs and Hypergraphs Seven-edge transversal bounds Bucić et al.: Covering graphs by monochromatic trees and Helly-type results for hypergraphs Erdös: Some recent problems and results in graph theory Fon-Der-Flaass et al.: Transversals in uniform hypergraphs with property (7,2)Tuza: Critical hypergraphs and intersecting set-pair systems ramsey_theory/erdos_1997_some_recent_problems_results_graph_theory Set Systems, Designs and Hypergraphs Bucić et al.: Covering graphs by monochromatic trees and Helly-type results for hypergraphs Corollary 2.9 (Bollobás): a critical r-graph with cover number t+1 has at most binom(r+t, t) edges Lemma 5.10: h_r(k, l) >= r l^2/(6k)Lemma 5.8: an l-uniform auxiliary hypergraph covers any floor((e(G)-1)/(e(G)-delta)) edges Observation 5.1: elementary bounds on the Helly-type cover number h_r(k, l)Proposition 5.6: h_r(l+1, l) = rl Proposition A.1: the (k, l)-covering property through the l-covering hypergraph Theorem 1.7: the behaviour of h_r(k, r) for fixed r as k varies Theorem 5.2: h_r(k, l) = l once k >= binom(r+l, l)Theorem 5.3: h_r(k, l) <= t when k >= binom(r+t, t)^{1/floor(t/l)} 2rl log(rl)Theorem 5.7: h_r(k, l) > t for k < binom(t+r, l)/binom(t, l)Theorem 6.1: the behaviour of the partite cover number hp_r(k) for fixed r Fon-Der-Flaass et al.: Transversals in uniform hypergraphs with property (7,2)Lemma 1 (p. 281): a good triple with bounded pairwise intersections yields Theorem 2 Theorem 1 (p. 278): the odd-intersection 4k-sets of a (7k+1)-set have property (7,2) and transversal number 3k+1 Theorem 2 (p. 281): an r-uniform family with transversal number above the ceiling of 7r/8 has a subfamily of at most seven edges with no two-point transversal Tuza: Critical hypergraphs and intersecting set-pair systems Lemma 4 (p. 137): a family of small transversals satisfying (**) bounds the s-transversal number by n_1(t, s-1)Theorem 17 (p. 142): an r-uniform tau-critical hypergraph with tau = t has at most n_1(r, t-1) < binomial(t+r, r) vertices Theorem 20 (p. 144): n_1(s,t-1)/k <= m_k(s,t) <= n_1(s,t-1) for k-intersecting tau-critical hypergraphs Theorem 6 (p. 138): n(a,b) for a >= b, and n_1(a,b), lie between a quarter of binomial(a+b+1, b+1) and binomial(a+b+1, b+1)

Graph