Erdoes #616 - working report - Erdős Problem a Day

Erdős problem #616 — live-page audit and verified progress

Access date: 2026-07-28 UTC.

Claim labels used below:

(a) elementary-rigorous: proved here from finite-set arguments.
(b) rigorous-modulo-named-theorem/source: quoted from, or dependent on,

the named source.

(c) plausible/structural-unverified: a search diagnosis or a point not

proved here.

(d) computational-only: established by the standalone exact program.

0. Mandatory live-page check

(b) I fetched the rendered live page through the Bright Data browser, then separately fetched its LaTeX view, discussion thread, and revision history:

(b) The live status is OPEN. It says 0 claimed proofs, “Currently working on this problem: None,” and “Interested in collaborating: None.” Thus the mandatory stop condition is not triggered.

(b) The exact statement in the site's LaTeX view is:

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

(b) The only known result listed there is quoted verbatim as:

Erd\H{o}s, Hajnal, and Tuza \cite{EHT91} proved that this $t$ satisfies\[\frac{3}{16}r+\frac{7}{8}\leq t \leq \frac{1}{5}r.\]

The site's bibliography identifies EHT91 as P. Erdős, A. Hajnal, and Zs. Tuza, Local constraints ensuring small representing sets, J. Combin. Theory Ser. A 58 (1991), 78–84.

(b) I read all five comments, all posted on 18 January 2026:

jkabrg linked an AI-generated proposed answer.
TerenceTao reported multiple defects: its final answer contradicts the

known bounds and its Step 4 contains an unjustified claim false in general.

Nat Sothanaphan emphasized that the proposed $t(r)=2$ for all

$r\geq6$ is inconsistent with EHT91.

old-bielefelder recommended direct self-checking of generated proofs.
Nat Sothanaphan added similar meta-level checking advice.

(b) These comments document a rejected argument; the site itself still records zero proof claims. Nothing in them is used below.

1. Literature check

(b) The EHT91 paper and metadata are verified at the publisher page, DOI 10.1016/0097-3165(91)90074-Q90074-Q). Its official abstract formulates the general problem using subsystems “on at most $p$ elements” and says that the paper studies $s=1$. The official abstract does not expose the hypotheses or rounding attached to the displayed linear bounds.

(b) The original Er99 source exists as P. Erdős, A Selection of Problems and Results in Combinatorics, Combin. Probab. Comput. 8 (1999), 1–6, DOI 10.1017/S0963548398003496. The publisher exposes its metadata and abstract but not the relevant full text.

(b) Later primary papers found through title, DOI, phrase, and citation searches study a different local condition: every $k$ edges have a small cover. This distinction is explicit in:

M. Bucić, D. Korándi, and B. Sudakov,

Covering graphs by monochromatic trees and Helly-type results for hypergraphs, especially its definition of the $(k,\ell)$-covering property;

D. Bradač and M. Bucić,

Covering random graphs with monochromatic trees;

D. G. Fon-Der-Flaass, A. V. Kostochka, and D. R. Woodall,

Transversals in uniform hypergraphs with property $(7,2)$, DOI 10.1016/S0012-365X(99)00114-4.

Those results do not imply #616's condition, which bounds the number of vertices in the union of a subfamily.

(c) I found no later primary source that improves or settles this exact “at most $3r-3$ union vertices” specialization. This is a documented search miss, not a proof that no such paper exists. In particular, I could not retrieve the theorem pages of EHT91 from the publisher archive, so I do not guess the missing qualifier on its displayed bound.

A live-page consistency issue

(a) The displayed inequalities cannot apply literally and simultaneously for every integer $r\geq3$. Their lower endpoint is at most their upper endpoint only when

\frac{3r}{16}+\frac78\leq\frac r5 \quad\Longleftrightarrow\quad r\geq70.

More decisively, the proof below gives $t(3)=1$, whereas the displayed lower quantity is $23/16$, and gives a rank-6 example with $\tau=2$, whereas the displayed upper quantity at $r=6$ is $6/5$.

(c) Therefore the live page has omitted a range, congruence, asymptotic, or rounding qualification, or has a transcription error. I do not assert which one without the EHT91 theorem text. The current revision history repeats the same formula and supplies no clarification.

2. Notation

Let $t(r)$ denote the least integer that works in the live statement. Say that an $r$-graph has property $P_r$ if every edge subfamily whose union has at most $3r-3$ vertices has nonempty total intersection. This is equivalent to the required $\tau(G')\leq1$ for all nonempty such subhypergraphs.

3. A general explicit lower-bound construction

(a) Proposition. Let $s\geq1$, put

c=\left\lfloor\frac{s-1}{3}\right\rfloor,\qquad q=3s+c,\qquad R_s=5s+1+c.

Then for every $r\geq R_s$ there is an explicit $r$-uniform hypergraph with property $P_r$ and transversal number $s+1$. Consequently,

t(r)\geq 1+\max\left\{s\geq1: 5s+1+\left\lfloor\frac{s-1}{3}\right\rfloor\leq r\right\}.

Construction

Take a set $X$ of $3s+1$ vertices. For each $s$-subset $T\subset X$, take a private set $P_T$, all these private sets pairwise disjoint and disjoint from $X$, with

\[ |P_T|=q. \]

Define

A_T=(X\setminus T)\cup P_T.

Every edge has size $2s+1+q=R_s$. To reach a larger rank $r=R_s+e$, add $e$ further private vertices to every $P_T$.

Verification of the local property

(a) Consider a subfamily indexed by distinct $T_1,\ldots,T_\ell$. For $\ell\geq2$, disjointness of the private blocks gives

\bigcap_{i=1}^{\ell}A_{T_i} =X\setminus\bigcup_{i=1}^{\ell}T_i.

Thus empty intersection implies that the $T_i$ cover $X$. Since $|X|=3s+1$, this requires $\ell\geq4$.

(a) Suppose first that $\ell=4$, and write $d=|T_1\cap T_2\cap T_3\cap T_4|$. Counting incidences in the four $s$-sets gives

4s\geq \left|\bigcup_{i=1}^4T_i\right| +3\left|\bigcap_{i=1}^4T_i\right| =3s+1+3d.

Hence $d\leq c$, and therefore

\begin{aligned} \left|\bigcup_{i=1}^4 A_{T_i}\right| &=3s+1-d+4q\\ &\geq3s+1-c+4(3s+c)\\ &=15s+1+3c\\ &=3R_s-2. \end{aligned}

(a) If $\ell\geq5$, the union contains at least one core $X\setminus T_i$, of size $2s+1$, and five disjoint private blocks. Thus

\left|\bigcup_{i=1}^{\ell}A_{T_i}\right| \geq2s+1+5q =(3R_s-2)+(2s+2c)>3R_s-3.

Every empty-intersection subfamily therefore uses at least $3R_s-2$ vertices. Adding $e$ private vertices per edge raises such a union by at least $4e$, but raises the forbidden threshold by only $3e$, proving $P_r$ for every $r\geq R_s$.

Verification of the transversal number

(a) Any $s+1$ vertices of $X$ meet every $X\setminus T$, so $\tau\leq s+1$.

(a) Conversely, let a proposed cover $C$ have at most $s$ vertices, and put $h=|C\cap X|$, $k=s-h$. The core part of $C$ misses every edge whose omitted set $T$ contains $C\cap X$. There are

\binom{3s+1-h}{s-h} =\binom{2s+1+k}{k}>k

such edges. At most $k$ vertices of $C$ remain outside $X$, and each private vertex lies in only one edge. Hence at least one of those edges is uncovered. Thus $\tau=s+1$.

(a) The first thresholds are:

| guaranteed transversal number | minimum rank from the construction | |---:|---:| | $2$ | $6$ | | $3$ | $11$ | | $4$ | $16$ | | $5$ | $22$ | | $6$ | $27$ | | $7$ | $32$ | | $8$ | $38$ | | $9$ | $43$ | | $10$ | $48$ |

(a) On the subsequence $s=3a+1$, one has $R_s=16a+6$ and

s+1=3a+2=\frac{3R_s}{16}+\frac78.

Thus this fully explicit family recovers the displayed EHT lower expression on that infinite subsequence. I make no novelty claim for the construction; it is included to make the lower bound independently checkable.

4. Minimal empty-intersection core lemma

(a) Lemma. Let $G$ have $P_r$ and empty total intersection. There is a finite inclusion-minimal empty-intersection subfamily $\mathcal A=\{A_1,\ldots,A_m\}$, and

3\leq m\leq r+1,\qquad \left|\bigcup_{i=1}^m A_i\right| \leq m(r-m+2).

Proof. Finiteness causes no issue even if $G$ were infinite: fix one finite edge and, for each of its vertices, choose an edge omitting that vertex. This gives a finite empty-intersection subfamily, from which take an inclusion-minimal one.

For each $i$, minimality gives a vertex

x_i\in\bigcap_{j\ne i}A_j\setminus A_i.

The $x_i$ are distinct. Put $X=\{x_1,\ldots,x_m\}$. Each $A_i$ contains exactly the $m-1$ witnesses other than $x_i$, so $m-1\leq r$ and, writing $Q_i=A_i\setminus X$,

\[ |Q_i|=r-m+1. \]

Property $P_r$ makes every two edges intersect, since their union has at most $2r\leq3r-3$ vertices; hence $m\ne2$. Finally,

\left|\bigcup_iA_i\right| =\left|X\cup\bigcup_iQ_i\right| \leq m+\sum_i(r-m+1) =m(r-m+2).

This proves the lemma.

5. Exact small ranks

Ranks 3, 4, and 5

(a) For a minimal core, the envelope $m(r-m+2)$ is:

| $r$ | values for $m=3,\ldots,r+1$ | local threshold $3r-3$ | |---:|---|---:| | 3 | $6,4$ | 6 | | 4 | $9,8,5$ | 9 | | 5 | $12,12,10,6$ | 12 |

Every possible minimal core would therefore lie on at most $3r-3$ vertices, contradicting $P_r$. Thus every admissible hypergraph has a common vertex. A one-edge hypergraph shows that the maximum is not zero:

\boxed{t(3)=t(4)=t(5)=1}.

Rank 6

(a) Here the forbidden threshold is 15. The core envelope for $m=3,\ldots,7$ is

15,\ 16,\ 15,\ 12,\ 7.

A minimal core must therefore have $m=4$, union size exactly 16, and equality throughout the core lemma. Consequently

A_i=(X\setminus\{x_i\})\cup Q_i,\qquad |X|=4,\quad |Q_i|=3,

with the four $Q_i$ pairwise disjoint.

(a) Let $B$ be any edge of the ambient hypergraph and fix $i\ne j$. The edge $B$ meets $A_i$ and $A_j$. If $B\cap A_i\cap A_j=\varnothing$, those two meetings use distinct vertices, so

|A_i\cup A_j\cup B| \leq (4+3+3)+(6-2)=14\leq15.

That three-edge subfamily has empty intersection, contradicting $P_6$. Hence

B\cap A_i\cap A_j\ne\varnothing.

But $A_i\cap A_j=X\setminus\{x_i,x_j\}$. As $i,j$ vary, these are all two-subsets of $X$. Thus $B\cap X$ meets every two-subset of the four-set $X$, so $|B\cap X|\geq3$. Any fixed pair of $X$ consequently meets every edge $B$, proving $\tau(G)\leq2$.

(a) The $s=1$ private-block construction, equivalently the four edges

A_i=(X\setminus\{x_i\})\cup P_i,\qquad |P_i|=3,

has union 16, property $P_6$, and transversal number 2. Therefore

\boxed{t(6)=2}.

Rank 7

(a) The threshold is 18, and the core envelope for $m=3,\ldots,8$ is

18,\ 20,\ 20,\ 18,\ 14,\ 8.

Thus $m\in\{4,5\}$ and the core union has size 19 or 20. The total number of incidences in the $Q_i$ exceeds $|\bigcup Q_i|$ by at most one. Equivalently, either all $Q_i$ are disjoint, or exactly one vertex $y$ lies in exactly two of them, say $Q_a,Q_b$, and every other extra vertex is private.

(a) Pair constraint. For every ambient edge $B$ and every $i\ne j$,

B\cap A_i\cap A_j\ne\varnothing.

Indeed, $|A_i\cup A_j|\leq12$ for $m=4$, and at most 11 for $m=5$. If the triple intersection were empty, the separate meetings of $B$ with $A_i,A_j$ would imply

|A_i\cup A_j\cup B|\leq12+(7-2)=17\leq18,

again violating $P_7$.

Four-edge core

(a) If the $Q_i$ are disjoint, the pair constraint says that $B\cap X$ meets every two-subset of the four-set $X$, hence has size at least three. Any fixed witness pair covers $G$.

(a) If $y\in Q_a\cap Q_b$, the same conclusion holds for every two-subset of $X$ except possibly $X\setminus\{x_a,x_b\}$; for that exceptional pair, $B$ may use $y$. It follows that either $|B\cap X|\geq3$, or $\{x_a,x_b,y\}\subseteq B$. In both cases $\{x_a,x_b\}\cap B\ne\varnothing$. Thus $\{x_a,x_b\}$ covers $G$.

Five-edge core

(a) Here $|X|=5$. The pair constraint says that $B\cap X$ meets every three-subset of $X$, except that when $y\in Q_a\cap Q_b$, the set $X\setminus\{x_a,x_b\}$ may instead be met at $y$. Therefore either $|B\cap X|\geq3$, or the exceptional possibility is

B\cap X=\{x_a,x_b\},\qquad y\in B.

(a) The case $|B\cap X|=3$ is impossible. Let $I$ be the three indices of its witness vertices. The three core edges $A_i$, $i\in I$, have total intersection $X\setminus(B\cap X)$, which $B$ misses. Their union has at most 14 vertices, while $B$ already has three vertices in that union. Hence the four edges together use at most $14+(7-3)=18$ vertices and have empty intersection, contradicting $P_7$.

(a) The exceptional two-witness case is also impossible. Choose distinct $u,v\notin\{a,b\}$, and let the three core indices be $\{a,b\}$ together with the remaining fifth index. Those three core edges have common intersection $\{x_u,x_v\}$, missed by $B$. Their union has 13 vertices because $Q_a,Q_b$ share $y$, and $B$ already contains $x_a,x_b,y$ in that union. The four-edge union is at most 17, again a contradiction.

(a) Every ambient edge therefore contains at least four of the five witnesses. Any fixed witness pair meets every edge, so $\tau(G)\leq2$. The four-edge private-block construction at rank 7 has $\tau=2$, giving

\boxed{t(7)=2}.

Combining the cases:

\boxed{t(3),t(4),t(5),t(6),t(7)=1,1,1,2,2}.

6. Independent exact checker

The standalone checker is erdos616_wavew002_reverify.py. It uses only the Python standard library and bit-mask set arithmetic.

(d) In addition to checking the construction formulas, it explicitly builds the $s=1,2$ private-block examples, checks every critical four-edge subfamily, and brute-forces their transversal numbers.

(d) For the rank-6 and rank-7 upper arguments, it constructs every labelled core type permitted by the core lemma. For each core it enumerates every possible signature $B\cap V(\text{core})$ of an additional edge, adds the necessary number of fresh vertices, tests every subfamily consisting of $B$ and core edges, and verifies that the analytically chosen witness pair meets every locally admissible $B$.

Run:

python3 runs/erdos616_wavew002_reverify.py

The clean run took about 3.7 seconds and ended with:

private-block lower-bound thresholds:
  tau>=2: r>=6
  tau>=3: r>=11
  tau>=4: r>=16
  tau>=5: r>=22
  tau>=6: r>=27
  tau>=7: r>=32
  tau>=8: r>=38
  tau>=9: r>=43
  tau>=10: r>=48
  tau>=11: r>=54
minimal-core possibilities (m, maximum deficit):
  r=3: []
  r=4: []
  r=5: []
  r=6: [(4, 0)]
  r=7: [(4, 1), (5, 1)]
  r=8: [(4, 2), (5, 3), (6, 2)]
TOTAL: checked=1797797, locally_admissible=9415
VERIFIED: t(3)=t(4)=t(5)=1 and t(6)=t(7)=2

(d) The 1,797,797 count is the number of extension signatures tested across all labelled rank-6/rank-7 core types; 9,415 survived all local constraints, and every survivor met the asserted fixed pair.

7. Exact boundary of this method

(a) At rank 8 the core lemma permits precisely

(m,\text{overlap deficit})=(4,\leq2),(5,\leq3),(6,\leq2).

Unlike rank 7, the extra incidence patterns can contain a vertex shared by three $Q_i$, two separately shared vertices, or (at deficit three) further combinations. The one-overlap fixed-pair argument above no longer covers these cases without a new lemma.

(c) The exact next task is: classify those rank-8 overlap patterns and prove that all ambient extensions have a common two-transversal, or exhibit a compatible family of extensions with transversal number at least three. The naive labelled analogue has 589 core patterns and roughly $6.0\times10^5$ to $1.8\times10^6$ single-edge signatures per core, before checking compatibility between multiple extension edges. A direct Python scan would be tens of hours; an isomorph-reduced C++/SAT computation is plausibly a few core-hours. I did not run that heavier computation here.

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

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger