Erdős Problem #616

Problem 616 $\#616$

1) ROUND-2 OBJECTIVE

Path (C): identify a minimal formal correction to the Round-1 restatement, and then use it to obtain exact information for small uniformities. Concretely, I will replace the Round-1 "induced subhypergraph" phrasing by the original subgraph/edge-subfamily formulation, and then prove the exact values \[ t(3)=t(4)=t(5)=1,\qquad t(6)=2, \] together with a general improvement of the Round-1 bound from $\tau(G)\le r$ to $\tau(G)\le r-1$.

2) Round-1 FOUNDATION USED

I use the following Round-1 consequences of the local hypothesis.

1. For $r\ge 3$, any two edges of $G$ intersect.
2. For $r\ge 3$, any three edges of $G$ intersect.
3. For $r\ge 3$, for any two edges $e,f$, the set $e\cap f$ is a transversal of $G$.

I will not re-prove these; I use them as vetted Round-1 input.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is a "minimal non-Helly subfamily" lemma.

If $\mathcal{F}=\{E_1,\dots,E_m\}$ is an $r$-uniform family with empty total intersection and minimal with respect to that property, then \[ m\le r+1 \quad\text{and}\quad \left|\bigcup_{i=1}^m E_i\right|\le m(r-m+2). \]

This turns the local threshold $3r-3$ into a concrete obstruction for small $r$.

A second new observation is that if $T$ is a minimal transversal of size at least $2$, then two witness edges for distinct vertices of $T$ intersect in at most $r-1$ vertices; since every pair-intersection is a transversal by Round 1, this yields the global improvement \[ \tau(G)\le r-1. \]

4) ATTACK PLAN (ROUND-2)

The exact gap left by Round 1 was this: the local condition forced $3$-wise intersection, but there was no mechanism turning that into either (i) exact small-$r$ values or (ii) a sharper global upper bound than $\tau(G)\le r$.

The plan is:

1. reformulate the original hypothesis exactly in terms of edge-subfamilies;
2. study a minimal edge-subfamily with empty total intersection;
3. bound the union size of such a minimal obstruction;
4. compare that bound with $3r-3$.

For $r\le 5$, this forces a contradiction, giving $\tau(G)=1$. For $r=6$, only a $4$-edge obstruction survives; that obstruction has enough rigid structure to force a $2$-vertex transversal.

5) WORK (ROUND-2)

Corrected local formulation.

The original problem is about all subgraphs on at most $3r-3$ vertices, not just induced subgraphs. The exact equivalent formulation is:

For every nonempty edge-subfamily $\mathcal{H}\subseteq E(G)$ with \[ \left|\bigcup \mathcal{H}\right|\le 3r-3, \] we have \[ \bigcap_{e\in \mathcal{H}} e\neq \varnothing. \]

Indeed, such an edge-subfamily spans a subgraph on $\left|\bigcup \mathcal{H}\right|$ vertices, and conversely every subgraph is determined by its edge set.

Lemma 5.1 (minimal non-Helly subfamily).

Let $\mathcal{F}=\{E_1,\dots,E_m\}$ be an $r$-uniform family such that \[ \bigcap_{i=1}^m E_i=\varnothing, \] but every proper subfamily has nonempty intersection. Then:

1. $m\le r+1$;
2. $\left|\bigcup_{i=1}^m E_i\right|\le m(r-m+2)$.

Proof.

For each $i$, minimality gives a vertex \[ x_i\in \bigcap_{j\ne i} E_j\setminus E_i. \] The vertices $x_1,\dots,x_m$ are distinct: if $x_i=x_j$ with $i\ne j$, then that common vertex would belong to $E_j$ (because $x_i\in \cap_{k\ne i} E_k$) and would also fail to belong to $E_j$ (because $x_j\notin E_j$), a contradiction.

Now fix $i$. Since $x_j\in E_i$ for every $j\ne i$, the edge $E_i$ contains at least the $m-1$ distinct vertices \[ \{x_j:\ j\ne i\}. \] As $|E_i|=r$, this implies $m-1\le r$, so $m\le r+1$.

Let \[ X=\{x_1,\dots,x_m\}. \] Each $E_i$ already contains the $m-1$ vertices $X\setminus\{x_i\}$, so it contributes at most \[ r-(m-1)=r-m+1 \] additional vertices outside $X$. Therefore \[ \left|\bigcup_{i=1}^m E_i\right| \le |X|+\sum_{i=1}^m \left(r-m+1\right) = m+m(r-m+1) = m(r-m+2). \] This proves the lemma. $\square$

Corollary 5.2.

If $r\in\{3,4,5\}$ and $G$ satisfies the local hypothesis, then all edges of $G$ have a common vertex. Equivalently, \[ t(3)=t(4)=t(5)=1. \]

Proof.

Assume for contradiction that $G$ has no common vertex. By Round 1, every three edges intersect. Hence any minimal edge-subfamily with empty total intersection has size \[ m\ge 4. \] By Lemma 5.1, necessarily $m\le r+1$ and its union has size at most $m(r-m+2)$.

Now check the finitely many cases.

• If $r=3$, then necessarily $m=4$, and \[ m(r-m+2)=4(3-4+2)=4\le 6=3r-3. \]
• If $r=4$, then $m\in\{4,5\}$, and \[ 4(4-4+2)=8\le 9,\qquad 5(4-5+2)=5\le 9. \]
• If $r=5$, then $m\in\{4,5,6\}$, and \[ 4(5-4+2)=12=3r-3,\qquad 5(5-5+2)=10\le 12,\qquad 6(5-6+2)=6\le 12. \]

So in every case the minimal obstruction has union size at most $3r-3$. By the local hypothesis, such a subfamily must have nonempty intersection, contradicting the choice of the obstruction.

Therefore all edges of $G$ intersect, so $\tau(G)=1$. $\square$

Proposition 5.3 (general improvement of the Round-1 upper bound).

For every $r\ge 3$, if $G$ satisfies the local hypothesis, then \[ \tau(G)\le r-1. \]

Proof.

If $\tau(G)=1$ there is nothing to prove. Assume $\tau(G)\ge 2$, and let $T$ be a minimal transversal of size $\tau(G)$.

For each $x\in T$, choose a witness edge $E_x$ with \[ E_x\cap T=\{x\}. \] Pick two distinct vertices $x,y\in T$. By the Round-1 foundation, the set \[ E_x\cap E_y \] is a transversal of $G$, so \[ \tau(G)\le |E_x\cap E_y|. \] On the other hand, because $E_x\cap T=\{x\}$ and $E_y\cap T=\{y\}$ with $x\ne y$, the intersection $E_x\cap E_y$ contains no vertex of $T$, hence \[ |E_x\cap E_y|\le r-1. \] Therefore $\tau(G)\le r-1$. $\square$

Construction 5.4 (a $2$-cover example for every $r\ge 6$).

Let \[ X=\{x_1,x_2,x_3,x_4\}, \] and let $A_1,A_2,A_3,A_4$ be pairwise disjoint sets of size $r-3$, all disjoint from $X$. Define four $r$-edges by \[ E_i=(X\setminus \{x_i\})\cup A_i \qquad (1\le i\le 4). \]

Then:

1. every three of the four edges intersect;
2. the total intersection is empty;
3. the local hypothesis holds whenever $r\ge 6$;
4. $\tau(\{E_1,E_2,E_3,E_4\})=2$.

Verification.

Any three edges contain the unique witness vertex omitted by the fourth. The total intersection is empty because no $x_i$ belongs to $E_i$, and the $A_i$ are disjoint.

The union of all four edges has size \[ |X|+\sum_{i=1}^4 |A_i|=4+4(r-3)=4r-8. \] For $r\ge 6$, \[ 4r-8>3r-3. \] So a subfamily on at most $3r-3$ vertices can contain at most three of the four edges; every such subfamily has nonempty intersection. Hence the local condition holds.

Finally, no single vertex hits all four edges, so $\tau\ge 2$. But if $a\in A_1$, then the $2$-set $\{x_1,a\}$ hits $E_1$ via $a$ and hits $E_2,E_3,E_4$ via $x_1$. Hence $\tau=2$.

Thus \[ t(r)\ge 2 \qquad\text{for all } r\ge 6. \] $\square$

Theorem 5.5.

\[ t(6)=2. \]

Proof.

Construction 5.4 gives $t(6)\ge 2$, so it remains to prove $t(6)\le 2$.

Let $G$ be a $6$-uniform hypergraph satisfying the local hypothesis. If all edges have a common vertex, then $\tau(G)=1$. So assume $G$ has no common vertex.

By Round 1, every three edges intersect. Choose a minimal edge-subfamily \[ \mathcal{F}=\{E_1,\dots,E_m\} \] with empty total intersection. Then $m\ge 4$.

By Lemma 5.1, \[ \left|\bigcup \mathcal{F}\right|\le m(8-m). \] If $m=5,6,$ or $7$, then \[ 5(8-5)=15,\qquad 6(8-6)=12,\qquad 7(8-7)=7, \] all of which are at most $15=3r-3$. That would contradict the local hypothesis. Hence the only possibility is \[ m=4. \]

Now apply Lemma 5.1 to this minimal $4$-edge obstruction. Choose witnesses \[ x_i\in \bigcap_{j\ne i} E_j\setminus E_i \qquad (i=1,2,3,4), \] and let \[ X=\{x_1,x_2,x_3,x_4\}. \] Each $E_i$ contains $X\setminus\{x_i\}$ and has size $6$, so it has exactly three additional vertices outside $X$. Therefore \[ \left|\bigcup_{i=1}^4 E_i\right|\le 4+4\cdot 3=16. \] Because $\mathcal{F}$ has empty intersection, the local hypothesis forces \[ \left|\bigcup_{i=1}^4 E_i\right|>15. \] Hence the union has size exactly $16$, so the upper bound is tight. Therefore the three extra vertices of each $E_i$ are disjoint from $X$ and pairwise disjoint across $i=1,2,3,4$. In particular, \[ E_i\cap E_j = X\setminus\{x_i,x_j\} \qquad (i\ne j). \]

Now let $F$ be any edge of $G$. By the Round-1 foundation, any three edges intersect, so for every pair $i\ne j$, \[ F\cap E_i\cap E_j\ne \varnothing. \] Since $E_i\cap E_j=X\setminus\{x_i,x_j\}$, it follows that \[ F\cap (X\setminus\{x_i,x_j\})\ne \varnothing \qquad\text{for every } i\ne j. \] Equivalently, the set $F\cap X$ meets every $2$-subset of $X$. This is possible only if \[ |F\cap X|\ge 3. \] Indeed, if $|F\cap X|\le 2$, then the complement $X\setminus (F\cap X)$ contains a $2$-subset disjoint from $F\cap X$.

Fix the pair \[ P=\{x_1,x_2\}. \] Each of the four core edges $E_1,E_2,E_3,E_4$ meets $P$, because each $E_i$ contains three of the four vertices of $X$. Any other edge $F$ also meets $P$, because $F\cap X$ has size at least $3$, and every $3$-subset of a $4$-set meets every fixed $2$-subset.

Thus $P$ is a transversal of $G$, so $\tau(G)\le 2$.

Combining this with the lower construction gives \[ t(6)=2. \] $\square$

6) ADVERSARIAL VERIFICATION

1. The only formal correction made to Round 1 is replacing the stronger "induced subhypergraph" wording by the original subgraph/edge-subfamily formulation. All Round-1 lemmas used here remain valid under the original statement.
2. In Lemma 5.1, the witness vertices $x_i$ are indeed distinct; this is the only subtle point in the proof.
3. In Corollary 5.2, the contradiction uses only the existence of one minimal empty-intersection subfamily with union at most $3r-3$, so the local hypothesis applies exactly as required.
4. In Construction 5.4, every potentially problematic subfamily is either:
   • a subfamily of at most three edges, which has nonempty intersection, or
   • the full $4$-edge family, whose union has size $4r-8>3r-3$.
   So the local condition is verified.
5. In the proof of $t(6)=2$, the step forcing $|F\cap X|\ge 3$ uses only the exact form of the six pair-intersections \[ E_i\cap E_j=X\setminus\{x_i,x_j\}, \] which was justified by the equality case in the union bound.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The main new results of this round are:

1. the exact values \[ t(3)=t(4)=t(5)=1,\qquad t(6)=2; \]
2. the general lower construction \[ t(r)\ge 2 \qquad (r\ge 6); \]
3. the general upper bound \[ \tau(G)\le r-1 \] for every admissible $r$-uniform hypergraph.

So the global problem is still open for $r\ge 7$, but the small cases are now settled through $r=6$, and the Round-1 bound $\tau(G)\le r$ has been sharpened to $\tau(G)\le r-1$.

8) COMPLETION ESTIMATE

COMPLETION: 72%

9) REFERENCES

• T. F. Bloom, Erdős Problem #616, accessed 2026-03-08.
• Round-1 notes from the previous iteration of this investigation (used only for the three structural lemmas listed in Section 2).

Erdős Problem #616: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

For an $r$-uniform hypergraph whose every edge subfamily on at most $3r-3$ vertices has a common vertex, determine the largest possible transversal number $t(r)$.

All supplied versions considered: 616.tex. The source proves exact small cases through $r=6$ and the upper bound $r-1$. Its claimed distinction between induced and arbitrary subgraphs is unnecessary here: a common vertex of all induced edges also hits every chosen subfamily. I extend its obstruction argument to $r=7$, without claiming a new literature result.

2) WORK

Rechecking the intersection input.

Two edges must intersect, since their union has at most $2r\le3r-3$ vertices. If three edges had empty intersection, their three pair intersections would be nonempty and disjoint, so inclusion--exclusion would give union size at most $3r-3$, a contradiction. Consequently every pair intersection is a transversal of the whole hypergraph.

Choose a minimal empty-intersection family $E_1,\ldots,E_m$. For each $i$ take $x_i\in\bigcap_{j\ne i}E_j\setminus E_i$. These witnesses are distinct; $E_i$ contains the other $m-1$ witnesses, so $4\le m\le r+1$. With $X=\{x_1,\ldots,x_m\}$ write \[ E_i=(X\setminus\{x_i\})\cup B_i,\qquad |B_i|=r-m+1, \] where every $B_i$ is disjoint from $X$. Therefore the union has at most $m(r-m+2)$ vertices.

The next uniformity.

Let $r=7$. Empty total intersection forces union size at least $19$. For $m\ge6$ the preceding bound is at most $18$, so $m=4$ or $5$. In either case its maximum is $20$. Thus \[ \sum_i|B_i|-\left|\bigcup_i B_i\right|\le1. \] There is at most one overlapping pair of petals: a vertex in three petals already contributes two to this difference, and two separate pair overlaps also contribute at least two. In particular some pair $B_i,B_j$ is disjoint. For that pair, \[ E_i\cap E_j=X\setminus\{x_i,x_j\},\qquad \tau(G)\le m-2\le3. \] If the minimal obstruction has four edges, the stronger bound $\tau(G)\le2$ follows.

The four-edge construction in the source, with $|X|=4$ and four disjoint private petals of size four, has union $20>18$, empty total intersection and common intersection for every proper subfamily. Any two witness vertices hit all edges. Hence $2\le t(7)\le3$.

3) ADVERSARIAL VERIFICATION

If total intersection is nonempty, the upper bound is immediate. For a potentially infinite edge family, an empty intersection has a finite witness subfamily: fix one finite edge and choose an edge omitting each of its vertices. Minimality is therefore legitimate. The overlap argument uses the integer lower bound 19, not just a weak asymptotic inequality.

4) FINAL

UNRESOLVED. This does not distinguish $t(7)=2$ from $3$, nor determine the general function. The original small-uniformity proofs and this extension are not claimed to improve published bounds.

5) SOURCES CHECKED

Full source read. The official indexed statement at https://www.erdosproblems.com/616 was checked on 2026-09-23. The displayed literature bounds in that index need qualification at small $r$ and are not used in this self-contained proof.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 12%

Problem 616

FORMAL RESTATEMENT

Fix an integer $r\ge 2$. An $r$-uniform hypergraph is a pair $G=(V,E)$ where $V$ is a finite vertex set and $E\subseteq \binom{V}{r}$.

For a vertex subset $U\subseteq V$, write $G[U]$ for the induced subhypergraph on $U$: \[ G[U] \;:=\; \left(U,\ \{e\in E:\ e\subseteq U\}\right). \]

A transversal (or vertex cover) of a hypergraph $H=(V(H),E(H))$ is a set $T\subseteq V(H)$ meeting every edge: $T\cap e\neq\varnothing$ for all $e\in E(H)$. The transversal number $\tau(H)$ is the minimum size of a transversal.

Assume $G$ satisfies the local property: \begin{equation} \label{wsref-0-65-71-3a-6c-6f-63-61-6c} \forall U\subseteq V\ \ (|U|\le 3r-3\ \Rightarrow\ \tau(G[U])\le 1). \end{equation} Equivalently: every induced subhypergraph on at most $3r-3$ vertices is either edge-empty or a star (all edges share a common vertex).

Define \[ t(r)\;:=\; \max\left\{\tau(G):\ G\ \text{is $r$-uniform and satisfies \eqref{wsref-0-65-71-3a-6c-6f-63-61-6c}}\right\}. \] The problem asks to determine the best possible $t(r)$ (exactly or asymptotically), and in particular the smallest universal $t$ such that $\tau(G)\le t$ for all $G$ satisfying (eq:local).

QUICK LITERATURE/CONTEXT CHECK

The statement in the prompt quotes Erdős--Hajnal--Tuza $1991$ giving linear-in-$r$ bounds of the form \[ c_1 r + O(1)\ \le\ t(r)\ \le\ c_2 r \] with explicit constants $c_1=\tfrac{3}{16}$ and $c_2=\tfrac{1}{5}$ (as written in the prompt). The ErdosProblems page for this item lists the problem as open and does not record a determination of $t(r)$.

ATTACK PLAN

The local hypothesis (eq:local) is a Helly-type / local-to-global condition. A natural approach is:

1. Extract structural consequences of (eq:local). In particular, apply it to unions of 2 or 3 edges to deduce strong intersection properties.
2. Relate $\tau(G)$ to intersections of edges. If one can show that some pair of edges intersects in $\le c r$ vertices, then $\tau(G)\le c r$ would follow from triplewise intersection.
3. If $\tau(G)$ is large, take a minimal transversal $T$ and use the standard "witness edge" construction (each $x\in T$ has an edge meeting $T$ exactly at $x$). Try to force a small-vertex induced subhypergraph whose transversal number is $\ge 2$, contradicting (eq:local).
4. If the above is insufficient, consider fractional transversals / LP duality and attempt to convert local constraints into a global bound (this is the sort of method used in several local-to-global covering results).

WORK

Step 1: (eq:local) forces pairwise intersection (for $r\ge 3$).

Assume $r\ge 3$. Let $e,f\in E$ be two edges. Then $|e\cup f|\le 2r\le 3r-3$. Apply (eq:local) to $U=e\cup f$. Since $G[U]$ contains $e$ and $f$, the condition $\tau(G[U])\le 1$ implies there exists a vertex $v\in U$ contained in every edge of $G[U]$, in particular $v\in e\cap f$. Hence \[ \boxed{\text{If $r\ge 3$, then every two edges intersect.}} \] So $G$ is an intersecting $r$-uniform hypergraph.

Step 2: (eq:local) forces 3-wise intersection (for $r\ge 3$).

Assume again $r\ge 3$. Take any three edges $e_1,e_2,e_3\in E$. From Step 1 we know $|e_i\cap e_j|\ge 1$ for each $i\ne j$. If $e_1\cap e_2\cap e_3=\varnothing$, then by inclusion--exclusion, \[ |e_1\cup e_2\cup e_3| = |e_1|+|e_2|+|e_3| - \sum_{i<j}|e_i\cap e_j| + |e_1\cap e_2\cap e_3| \le 3r - 3. \] Applying (eq:local) to $U=e_1\cup e_2\cup e_3$ would force $\tau(G[U])\le 1$, hence would force a vertex common to all edges of $G[U]$, in particular common to $e_1,e_2,e_3$, contradicting $e_1\cap e_2\cap e_3=\varnothing$. Therefore \[ \boxed{\text{If $r\ge 3$, then every three edges have nonempty intersection.}} \] So $G$ is 3-wise intersecting.

Step 3: In a 3-wise intersecting hypergraph, the intersection of two edges is a transversal.

Let $H=(V,E)$ be any hypergraph with the property that any three edges intersect. Fix two edges $e,f\in E$ and set $I:=e\cap f$. For any third edge $g\in E$, the triple intersection condition gives $(e\cap f\cap g)\neq\varnothing$, i.e., $I\cap g\neq\varnothing$. Thus every edge $g$ meets $I$, so $I$ is a transversal. Hence \[ \boxed{\tau(H)\le |e\cap f|\ \text{for all edges $e,f\in E$.}} \] In particular, \begin{equation} \label{wsref-0-65-71-3a-74-61-75-2d-6d-69-6e-2d-69-6e-74-65-72-73-65-63-74-69-6f-6e} \tau(H)\ \le\ \min\left\{|e\cap f|:\ e,f\in E\right\}. \end{equation} Applying this to $G$ (Step 2) yields the same bound.

A very coarse universal bound.

Since $G$ is intersecting (Step 1), for any edge $e\in E$ the set $e$ itself is a transversal (it meets every other edge). Therefore \[ \boxed{\tau(G)\le r\quad\text{for all $r\ge 3$ under \eqref{wsref-0-65-71-3a-6c-6f-63-61-6c}.}} \] This is far weaker than the best-known linear bounds, but it is immediate.

Why this does not determine $t(r)$.

The inequality (eq:tau-min-intersection) reduces the problem to bounding how large the minimum pairwise intersection $\min_{e\ne f}|e\cap f|$ can be under (eq:local). The known upper bound $t(r)\le r/5$ amounts (morally) to showing existence of a pair of edges intersecting in at most about $r/5$ vertices. I did not find a clean argument from first principles that forces such a small intersection, nor an explicit construction matching $r/5$.

VERIFICATION

• Step 1 used only that $2r\le 3r-3$, i.e. $r\ge 3$. For $r=2$ the local condition $|U|\le 3$ is too small to force pairwise intersection, so the reduction above is specific to $r\ge 3$.
• Step 2 is a direct inclusion--exclusion calculation plus an application of (eq:local). No hidden assumptions beyond Step 1.
• Step 3 is a standard consequence of 3-wise intersection and is completely general.

FINAL

UNRESOLVED

1. Where and why the attempt fails. The core missing step is an a priori bound (as a function of $r$) on the minimum pairwise intersection size $\min_{e\ne f}|e\cap f|$ for $r$-uniform hypergraphs satisfying (eq:local). While (eq:local) forces 3-wise intersection, that alone does not immediately control the size of a smallest pairwise intersection, and I did not succeed in pushing the local constraint to produce a pair with intersection $\le r/5$ or to build an example approaching the lower bound constant.

2. Strongest partial result proved here. For $r\ge 3$, the local hypothesis (eq:local) implies:
   • $G$ is pairwise intersecting and 3-wise intersecting;
   • for any two edges $e,f$, the intersection $e\cap f$ is a transversal;
   • consequently $\tau(G)\le \min_{e,f\in E}|e\cap f|$ and in particular $\tau(G)\le r$.

3. Most plausible next ideas. A promising route is to study minimal transversals $T$ and the associated witness edges $\{e_x:x\in T\}$ with $e_x\cap T=\{x\}$. Under 3-wise intersection, any three witness edges have a common vertex outside $T$, which imposes strong incidence constraints. One would like to convert these constraints into an upper bound on $|T|$ linear in $r$ with a sharp constant, perhaps via: $1$ a density/averaging argument on the outside vertices, $2$ a shifting/compression argument to obtain a near-extremal canonical form, or $3$ a fractional transversal/packing duality argument.

4. Small cases / computations. I did not carry out an exhaustive computation of $t(r)$ for small $r$. The arguments above show that for $r\ge 3$ any admissible $G$ is 3-wise intersecting, which already rules out many naive constructions. Determining $t(r)$ even for small fixed $r$ seems nontrivial and would likely require a dedicated search over $r$-uniform set systems.

COMPLETION ESTIMATE

COMPLETION ESTIMATE: 35%.