Erdős Problem #644

Problem 644 --- ROUND 2

1) ROUND-2 OBJECTIVE

Path (C): correct a quantifier subtlety in the Round-1 finite-family restatement, then prove substantially sharper bounds for $f(k,7)$. A full solution still seems out of reach, but Round 2 can narrow the problem to the interval \[ \frac34 k + O(1) \le f(k,7) \le \frac78 k + O(1), \] with an explicit lower bound valid for all $k\ge 2$ and a literature-based upper bound.

2) Round-1 FOUNDATION USED

I use the following Round-1 items.

• The hypergraph reformulation: $f(k,7)$ is the largest possible transversal number $\tau(H)$ among $k$-uniform hypergraphs in which every $7$ edges admit a $2$-point transversal.
• The Round-1 baseline bound $f(k,r)\le k(r-1)$, obtained from the matching number.
• The Round-1 status: exact values for $r=3,4,5,6$ were known, while $r=7$ remained open.

3) NEW INSIGHT / TOOL (ROUND-2)

There are two genuinely new ingredients.

• Quantifier correction. The classical problem is stated for an arbitrarily long family $A_1,A_2,\dots$ (in particular, one may always enlarge a bad subfamily to size $7$). The finite-family Round-1 restatement is harmless for asymptotics, but for exact upper-bound arguments one should either assume the family has at least $7$ members or require the local property for all subfamilies of size at most $7$.
• New lower bound valid for all $k\ge 2$. The complete $k$-uniform hypergraph on $\lceil 7k/4\rceil-1$ vertices already has property $(7,2)$, yielding \[ f(k,7)\ge \left\lceil\frac{3k}{4}\right\rceil. \] This sharpens the Round-1 lower information considerably.

4) ATTACK PLAN (ROUND-2)

The Round-1 gap was enormous: only the very weak bound $f(k,7)\le 6k$ was available there. Round 2 closes much of this gap by proving or importing three precise claims:

1. a corrected formulation under which the modern upper-bound theorem applies;
2. a direct lower bound from complete hypergraphs, valid for all $k\ge 2$;
3. the best currently accessible sandwich bound \[ \left\lceil\frac{3k}{4}\right\rceil \le f(k,7) \le \left\lceil\frac{7k}{8}\right\rceil, \] plus the stronger residue-class lower bound $f(4q,7)\ge 3q+1$ for $q\ge 4$.

5) WORK (ROUND-2)

Minimal correction of the formulation.

The original Erdős problem is phrased for a family $A_1,A_2,\dots$ of $k$-sets. For the upper-bound theorem below, what matters is that whenever a subfamily $\mathcal F$ with $|\mathcal F|\le 7$ has transversal number $>2$, one can enlarge $\mathcal F$ to a $7$-member subfamily with the same property. This is automatic in the original infinite-family formulation, and also automatic for any finite family with at least $7$ members.

Thus the only correction needed to the Round-1 finite-family restatement is: for exact upper bounds, either work with the original arbitrarily long family, or explicitly restrict to families with at least $7$ members. This does not affect the asymptotic question.

Claim 644.1.

For every integer $k\ge 2$, the complete $k$-uniform hypergraph on \[ n_k:=\left\lceil \frac{7k}{4}\right\rceil-1 \] vertices has property $(7,2)$.

Proof.

Let $\mathcal H=K^{(k)}_{n_k}$, and choose any seven edges $E_1,\dots,E_7$ of $\mathcal H$. Each $E_i$ has size $k$, so the total incidence count is $7k$. Since \[ n_k < \frac{7k}{4}, \] we have \[ 7k > 4n_k. \] Hence some vertex $x$ belongs to at least five of the seven sets $E_i$. At most two of the seven sets do not contain $x$. If there are zero or one such sets, then any second point $y$ gives a $2$-point transversal $\{x,y\}$. If there are two such sets, call them $F$ and $G$. Because \[ n_k < 2k, \] any two $k$-subsets of an $n_k$-element ground set must intersect. Therefore $F\cap G\neq\varnothing$. Choose $y\in F\cap G$. Then $\{x,y\}$ meets all seven edges. So every seven edges of $\mathcal H$ have a transversal of size at most $2$, i.e. $\mathcal H$ has property $(7,2)$.

$\square$

Corollary 644.2.

For every $k\ge 2$, \[ f(k,7)\ge \left\lceil \frac{3k}{4}\right\rceil. \]

Proof.

The transversal number of the complete $k$-uniform hypergraph on $n_k$ vertices is $n_k-k+1$. Using Claim 644.1, \[ f(k,7)\ge n_k-k+1 = \left(\left\lceil \frac{7k}{4}\right\rceil-1\right)-k+1 = \left\lceil \frac{3k}{4}\right\rceil. \]

$\square$

External Theorem 644.3 (Fon-Der-Flaass--Kostochka--Woodall).

If $\mathcal B$ is an $r$-uniform family with \[ \tau(\mathcal B) > \left\lceil \frac{7r}{8}\right\rceil, \] then there exists a subfamily $\mathcal F\subseteq \mathcal B$ with $|\mathcal F|\le 7$ and $\tau(\mathcal F)>2$.

Corollary 644.4.

Under the original arbitrarily-long-family formulation of the problem, \[ f(k,7)\le \left\lceil \frac{7k}{8}\right\rceil. \]

Proof.

Assume to the contrary that some $k$-uniform family $\mathcal B$ has property $(7,2)$ and yet \[ \tau(\mathcal B) > \left\lceil \frac{7k}{8}\right\rceil. \] By External Theorem 644.3, there exists $\mathcal F\subseteq \mathcal B$ with $|\mathcal F|\le 7$ and $\tau(\mathcal F)>2$. If $|\mathcal F|=7$, this directly contradicts property $(7,2)$. If $|\mathcal F|<7$, enlarge $\mathcal F$ by adding arbitrary further members of $\mathcal B$ until it has size exactly $7$; call the enlarged family $\mathcal F'$. Since adding sets cannot decrease transversal number, \[ \tau(\mathcal F')\ge \tau(\mathcal F)>2, \] again contradicting property $(7,2)$. Therefore no such $\mathcal B$ exists, and the upper bound follows.

$\square$

External Theorem 644.5 (same paper, lower-bound construction).

For every integer $q\ge 4$, there exists a $(4q)$-uniform family with property $(7,2)$ and transversal number $3q+1$. Consequently, \[ f(4q,7)\ge 3q+1 \qquad (q\ge 4). \]

Combined Round-2 bound.

From Corollaries 644.2 and 644.4 and External Theorem 644.5 we obtain \[ \left\lceil \frac{3k}{4}\right\rceil \le f(k,7) \le \left\lceil \frac{7k}{8}\right\rceil \qquad (k\ge 2), \] and in addition \[ f(4q,7)\ge 3q+1 \qquad (q\ge 4). \] So the conjectured asymptotic constant, if it exists, lies in the interval \[ \frac34 \le c_7 \le \frac78. \] Round 2 therefore cuts the Round-1 upper bound from $6k$ down to $(7/8)k+O(1)$ and simultaneously proves the lower bound $(3/4)k+O(1)$ for all $k\ge 2$.

6) ADVERSARIAL VERIFICATION

The possible failure points are as follows.

• Quantifier issue. If one works with a finite family of fewer than $7$ sets and interprets property $(7,2)$ literally, the condition is vacuous. That is why I stated the minimal correction explicitly before using the upper-bound theorem. The original Erdős problem uses an arbitrarily long family, so the extension-to-$7$ step is legitimate.
• Claim 644.1. The incidence argument gives a vertex in at least five of the seven sets because $7k>4n_k$. The remaining two sets intersect because $n_k<2k$. No hidden assumption is used.
• Lower-bound arithmetic. The identity \[ \left(\left\lceil\frac{7k}{4}\right\rceil-1\right)-k+1 =\left\lceil\frac{3k}{4}\right\rceil \] is correct since subtracting the integer $k$ commutes with taking ceilings.
• Use of External Theorem 644.3. The hypotheses match exactly after the quantifier correction.

No contradiction or hidden gap remains in the Round-2 deductions.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The exact asymptotic of $f(k,7)$ remains open, but Round 2 gives the corrected formulation needed for the sharp known upper bound and proves the explicit lower bound valid for all $k\ge 2$ \[ \left\lceil \frac{3k}{4}\right\rceil \le f(k,7). \] Together with the literature upper bound this yields \[ \left\lceil \frac{3k}{4}\right\rceil \le f(k,7) \le \left\lceil \frac{7k}{8}\right\rceil, \] plus the stronger residue-class lower bound $f(4q,7)\ge 3q+1$ for $q\ge 4$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 68%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #644, accessed 2026-03-07.
2. D. G. Fon-Der-Flaass, A. V. Kostochka, and D. R. Woodall, Transversals in uniform hypergraphs with property $(7,2)$, Discrete Mathematics 207 $1999$, 277--284.

10) OUTPUT FORMAT

This section is part of the combined drop-in file 643_644_650_solutions.tex; no preamble is used.

OBJECTIVE AND SOURCE REVIEW

Erdős #644; independent attempt, 2026-09-23. Determine whether $f(k,7)=(3/4+o(1))k$, and whether $f(k,r)/k$ has a limit for every fixed $r\ge3$. Here $f(k,r)$ is the maximal transversal number for $k$-uniform families whose every subfamily of at most $r$ edges has a two-point transversal, using the supplied nonvacuous formulation. I read the full 644.tex, including its complete-hypergraph lower bound and imported upper bound. I test how lower constructions transfer between uniformities and whether the usual vertex duplication improves the ratio.

WORK: PADDING AND DUPLICATION HAVE DIFFERENT EFFECTS

Given such a family $\mathcal H$, attach to each edge $E$ a distinct private point $z_E$ and replace it by $E\cup\{z_E\}$. This gives a $(k+1)$-uniform family $\mathcal H'$ with the same transversal number. An old transversal still works, giving $\tau(\mathcal H')\le\tau(\mathcal H)$. Conversely replace each private point of any transversal of $\mathcal H'$ by an arbitrary old point of its one associated edge. The resulting set has no greater size and meets every old edge. Hence equality holds. The local two-point property is preserved because each old local transversal still meets the enlarged edges. Thus $f(k+1,7)\ge f(k,7)$ in this formulation. In contrast, replace every vertex $v$ by $t$ clones and each edge by the union of all clones of its vertices. The new rank is $tk$, but its transversal number remains $\tau(\mathcal H)$: choosing one clone per old transversal works, and projecting any new transversal to old vertices works in reverse. The local property again persists. Therefore this common duplication operation divides, rather than preserves, the ratio $\tau/k$ by $t$.

ADVERSARIAL VERIFICATION AND REMAINING GAP

Private points must be different for different edges; one shared new point would make the transversal number one. Duplicate selections may collapse on projection, which only helps the inequalities. Neither operation multiplies transversal number with rank, so neither promotes one isolated high-ratio example into an asymptotically equal ratio at all ranks. The source's known sandwich can be retained as external background, but no narrower interval or exact limiting constant is obtained. The at-most-seven formulation avoids vacuity for very small families. Both transformations work verbatim for every fixed $r$, but monotonicity of $f(k,r)$ alone does not prove convergence of its ratio to $k$. No such limit is obtained here.

SOURCES CHECKED

Complete local source gpt_pro_5.4/644.tex; official indexed statement https://www.erdosproblems.com/forum/thread/644. Both transformation lemmas are proved directly, with no claim of novelty or use of the source's unproved external extremal bounds.

FINAL

UNRESOLVED. Rank padding is verified, and a tempting ratio-preserving duplication argument is ruled out.

COMPLETION ESTIMATE

Conservative subjective progress toward the exact extremal constant. COMPLETION: 8%

Problem 644 (transversals from local 2-piercing)

FORMAL RESTATEMENT

Fix integers $k\ge 1$ and $r\ge 3$. Let $\mathcal A=\{A_1,\dots,A_m\}$ be a family of $k$-element subsets of some ground set $X$.

Assume the $(k,r)$-property with 2-piercing: for every choice of indices $i_1,\dots,i_r$, there exist elements $x,y\in X$ (depending on the $r$-tuple) such that \[ \{x,y\}\cap A_{i_j}\neq\varnothing\qquad\text{for all } j=1,\dots,r. \]

Let $f(k,r)$ be the least integer such that any such family $\mathcal A$ has a transversal (hitting set) $T\subseteq X$ with \[|T|\le f(k,r)\qquad\text{and}\qquad T\cap A_i\neq\varnothing\ \ \forall i. \]

The prompt records exact values for $r\in\{3,4,5,6\}$ and asks in particular:

• determine/estimate $f(k,7)$ (conjectured $\sim \tfrac34 k$);
• more generally, whether for each fixed $r$ there is a constant $c_r$ with $f(k,r)=(1+o(1))c_r k$ as $k\to\infty$.

QUICK LITERATURE/CONTEXT CHECK (browsing)

The prompt cites Erdős--Fűredi--Kostochka--Tuza $1992$ for the exact values \[f(k,3)=2k,\quad f(k,4)=\lfloor 3k/2\rfloor,\quad f(k,5)=\lfloor 5k/4\rfloor,\quad f(k,6)=k. \] A quick web check also turns up follow-up work on property $(p,2)$ transversals (e.g. papers by Fon-Der-Flaass and by Kostochka on general $(p,2)$ settings), but I did not locate a definitive resolution of the asymptotic for $r=7$ in freely accessible sources.

ATTACK PLAN

Translate to $k$-uniform hypergraphs and try to control the transversal number.

1. (Definitions) View $\mathcal A$ as the edge set of a $k$-uniform hypergraph $H$.
2. (Reduction) Note that the $(k,r)$-property implies $H$ has no matching of size $r$ (since $r$ disjoint edges cannot be hit by 2 vertices).
3. (Known general inequality attempt) Relate transversal number $\tau(H)$ to matching number $\nu(H)$.
4. (Try to use extra structure) The local "2-piercing" property is stronger than $\nu(H)\le r-1$; attempt to exploit it for $r=7$ (unsuccessful below).
5. (Constructions) Consider families that make $\tau(H)$ large while keeping every $r$-edge subfamily 2-pierceable.

WORK

Step 1: Hypergraph translation

Let $H$ be the $k$-uniform hypergraph on vertex set $X$ with edge set $E(H)=\mathcal A$. Let $\tau(H)$ be its transversal (vertex cover) number and $\nu(H)$ its matching number. The definition of $f(k,r)$ is \[ f(k,r)= \max\{\tau(H):\ H\text{ is $k$-uniform and every $r$ edges are 2-pierceable}\}. \]

Step 2: Immediate consequence: bounded matching number

Step 3: A simple universal upper bound via maximal matchings

This bound is very weak compared to the exact values for $r\le 6$ (e.g. it gives $f(k,6)\le 5k$ whereas the true value is $k$).

Step 4: Attempt to exploit the stronger local condition (incomplete)

The obstacle is that $\nu(H)\le r-1$ only uses the fact that $r$ disjoint edges are forbidden, but does not capture the stronger condition "every $r$ edges have a 2-vertex cover". For $r=7$, one would like to show $\tau(H)\le (3/4+o(1))k$.

I attempted (unsuccessfully) to derive a structural lemma of the following flavour:

if $\tau(H)$ is large (linear with constant $>3/4$), then one can find $7$ edges whose minimum vertex cover is $\ge 3$.

The natural place to apply such a lemma is to a minimal transversal $T$ and the associated family of edges witnessing minimality, but I did not close the argument.

VERIFICATION

The proven inequalities are checked directly:

• If there is a matching of size $r$, no 2-set can hit all $r$ disjoint edges.
• The union of a maximal matching must hit every edge.

FINAL

UNRESOLVED.

Strongest fully proved partial result in this write-up:

For all $k\ge 1$ and $r\ge 3$, one always has the universal linear bound \[ f(k,r)\le k(r-1). \]

This shows at least that $f(k,r)=O_r(k)$ for fixed $r$, though it does not address the conjectured constants $c_r$ (e.g. $c_7=3/4$).

COMPLETION ESTIMATE

$0.25$.