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

Erdős problem #643 — wave w004

Access date: 2026-07-28 UTC Live page: <https://www.erdosproblems.com/643> Standalone verifier: runs/erdos643_wavew004_verify.py

Claim labels used throughout:

(a) elementary-rigorous: proved here from definitions, or a direct documentary observation;
(b) rigorous-modulo-named-theorem: the named theorem is stated explicitly;
(c) plausible/structural-unverified: useful evidence or a non-exhaustive literature conclusion;
(d) computational-only: exact only conditional on the enumerator and exact solver implementations.

0. Mandatory live-page gate

I fetched both the problem page and its separate discussion page through the Bright Data browser path, not through direct curl.

Verbatim current statement

Let $f(n;t)$ be minimal such that if a $t$-uniform hypergraph on $n$ vertices contains at least $f(n;t)$ edges then there must be four edges $A,B,C,D$ such that \[ > A\cup B=C\cup D > \] and \[ > A\cap B=C\cap D=\emptyset. > \] Estimate $f(n;t)$ - in particular, is it true that for $t\geq 3$ \[ > f(n;t)=(1+o(1))\binom{n}{t-1}? > \]

Status, known results, comments, and activity markers

(a) Direct page observation. The page was marked OPEN, last edited 26 October 2025. It displayed:

2 comments on this problem;
0 claimed proofs for this problem;
Interested in collaborating — None;
Currently working on this problem — None;
all displayed “looks difficult”, “looks tractable”, and formalisation-work markers — None.

Thus the mandatory collision/claimed-resolution stop condition did not fire.

(a) Results listed on the page.

For $t=2$, the page identifies the question with the $C_4$-free graph problem and states

\[ f(n;2)=(1/2+o(1))n^{3/2}. \]

It attributes to Füredi [Fu84] that $f(n;3)\ll n^2$, that $f(n;3)>\binom n2$ for infinitely many $n$, and the general bounds

\[ \binom{n-1}{t-1}+\left\lfloor\frac{n-1}{t}\right\rfloor \leq f(n;t)<\frac72\binom n{t-1}. \] It says Füredi conjectured the lower bound to be sharp for $t\geq4$.

It attributes to Pikhurko–Verstraëte [PiVe09]

\[ f(n;3)\leq\frac{13}{9}\binom n2 \] for all $n$, and \[ 1\leq\limsup_{n\to\infty} \frac{f(n;t)}{\binom n{t-1}} \leq\min\left(\frac74,1+\frac2{\sqrt t}\right) \quad(t\geq3). \]

It says Füredi proved convergence of $f(n;3)/\binom n2$, while existence of the corresponding limit for $t\geq4$ is unknown.

(a) The two comments. Both are by Quanyu Tang on 26 October 2025, and both say that the site has already been updated to incorporate them. The 07:24 comment supplies the Pikhurko–Verstraëte limsup and $13/9$ bounds. The 07:21 comment corrects the graph-case constant to $1/2$, and “$n=2$” to “$t=2$”. The discussion page warns that user comments are unverified.

Finite-value convention warning

(a) Elementary-rigorous. The live statement defines a forcing threshold. The primary papers instead use $f_t(n)$ for the maximum avoiding size. To prevent finite off-by-one errors, define

g_t(n):=\max\{|\mathcal F|:\mathcal F\subseteq\tbinom{[n]}t \text{ has no stated four-edge configuration}\}.

Then the live statement implies the exact identity

\boxed{f(n;t)=g_t(n)+1.}

The distinction disappears asymptotically, but it matters in every exact value below. In particular, PiVe09 Theorem 2 literally bounds its maximum-size $f_3(n)$, not the live page's forcing threshold.

1. Primary-source literature check

Sources actually inspected

(a) Documentary verification.

Erdős 1977 [Er77b]. I inspected the scan of P. Erdős, “Problems and results in combinatorial analysis,” Congressus Numerantium XIX (1977), 3–12, at <https://combinatorica.hu/~p_erdos/1977-24.pdf>. Section II.6 states the $r$-tuple generalisation and explicitly asks for four triples with the two pairs disjoint and with equal unions. SHA-256 of the inspected 10-page PDF:

80523f2239bd25fd2bad0ce17df68f4fff41177ce442a6149f98073f1ca8909a.

Füredi 1984 [Fu84]. Z. Füredi, “Hypergraphs in which all disjoint pairs have distinct unions,” Combinatorica 4 (1984), 161–168, DOI <https://doi.org/10.1007/BF02579216>. The paper defines $f_r(n)$ as the maximum avoiding size, gives the star-plus-matching construction used below, proves the $7/2$ upper bound, and proves convergence in the triple case. SHA-256 of the inspected 8-page scan:

8dc3b2d74b95b6ed52187d6b2289bd60b07ec0563c153c6ff063a3dfb92c129f.

Pikhurko–Verstraëte 2009 [PiVe09]. O. Pikhurko and J. Verstraëte, “The maximum size of hypergraphs without generalized 4-cycles,” JCTA 116 (2009), 637–649, DOI <https://doi.org/10.1016/j.jcta.2008.09.002>; author manuscript at <https://mathweb.ucsd.edu/~jverstra/generalizedc4.pdf>. Its abstract and Theorems 1–2 state

\[ \phi_t\leq\min(7/4,1+2/\sqrt t),\qquad f_3(n)\leq(13/9)\binom n2, \] with $f_t(n)$ explicitly defined as the maximum avoiding size. SHA-256 of the inspected 18-page PDF: fffc7225d5d903d7060b92d9dea39e9b2b9e396e53a929ee92c8c681b4007edf.

A later adjacent result, not an edge-count improvement. E. Marchant, “The Largest Minimum Codegree of a 3-Graph Without a Generalized 4-Cycle,” DOI <https://doi.org/10.1017/S0963548312000430>, proves the sharp minimum-codegree threshold $4$. Its parameter is minimum pair-codegree, not the ordinary maximum number of edges in problem #643.

(c) Non-exhaustive negative literature result. Exact-title/exact-phrase searches and the OpenAlex citing-work query for PiVe09 (work W2103078247) returned 14 citing records. The later records I could identify concern minimum codegree, all two-regular subgraphs, hypergraph bipartite Turán problems, relative Turán numbers, or other variants. I found no primary source claiming an improvement of the ordinary $g_t(n)$ bounds above. This is a documented search miss, not a proof that no such paper exists. I did not rely on the content of the page's 1997 Erdős citation [Er97d].

2. An exact all-$t$ boundary regime

Theorem

(a) Elementary-rigorous. For every integer $t\geq1$,

\boxed{ g_t(n)=\binom nt\quad(0\leq n<2t) }

and

\boxed{ g_t(2t)=\frac12\binom{2t}{t}+1. }

Equivalently, in the live forcing-threshold convention,

\boxed{ f(n;t)=\binom nt+1\quad(n<2t),\qquad f(2t;t)=\frac12\binom{2t}{t}+2. }

Proof

If $n<2t$, no two $t$-sets are disjoint. Hence even the complete $t$-graph avoids the configuration, proving the first formula.

Let $n=2t$. Complementation partitions the $\binom{2t}{t}$ possible edges into

q=\frac12\binom{2t}{t}

unordered complementary pairs. A forbidden configuration is exactly two distinct complementary pairs whose four members were all selected. Therefore an avoiding family can complete at most one complementary pair. It can select two members from that pair and at most one member from each of the other $q-1$ pairs, so

|\mathcal F|\leq2+(q-1)=q+1.

Selecting both members of one pair and one arbitrary member of every other pair attains $q+1$. This proves the result.

3. Explicit general lower construction

(a) Elementary-rigorous. Fix a vertex $0$. Take every $t$-set containing $0$, and add a matching of $\lfloor(n-1)/t\rfloor$ pairwise disjoint $t$-sets outside $0$. This gives

|\mathcal F|= \binom{n-1}{t-1}+\left\lfloor\frac{n-1}{t}\right\rfloor.

To check the avoiding property, note first that a disjoint pair cannot consist of two star edges, because both contain $0$. If a disjoint pair consists of two matching blocks, its union excludes $0$; any competing pair with the same union must again consist of the same two matching blocks. If its union contains $0$, the pair consists of one matching block and one star edge. Two distinct matching blocks have union of size $2t$, so they cannot both lie inside the common union with $0$ removed, which has size $2t-1$. Thus a competing pair must use the same matching block, and then the same star edge. No repeated union occurs.

The standalone program constructs these families independently and checks every pair of disjoint edges directly from the displayed union/intersection definition.

4. Exact small triple-system computation

Exact reduction to a finite 0–1 problem

(a) Elementary-rigorous reduction. For each $2t$-set $U$, let

\mathcal P_U= \bigl\{\{A,U\setminus A\}:A\in\tbinom Ut\bigr\}

with duplicate unordered pairs removed. Thus $|\mathcal P_U|=\frac12\binom{2t}{t}$. The family is avoiding if and only if at most one member of $\mathcal P_U$ has both endpoints selected, for every $U$.

With a binary variable $x_A$ for every $t$-set, this is encoded without relaxation: for every two distinct complementary pairs $\{A,B\},\{C,D\}\in\mathcal P_U$,

x_A+x_B+x_C+x_D\leq3.

For $t=3$, each 6-set has ten complementary pairs and hence $\binom{10}{2}=45$ forbidden quadruples. The total is $45\binom n6$.

Symmetry reduction for $n=8$

(b) Rigorous modulo Erdős–Ko–Rado. EKR gives

\alpha(KG(8,3))=\binom72=21.

Any triple family of size at least $23$ therefore contains a disjoint pair. All disjoint pairs of triples are equivalent under a relabelling of the eight vertices. Since the construction below already has size 23, the global optimum can be computed after fixing

\{0,1,2\},\{3,4,5\}\in\mathcal F.

No symmetry assumption is used for $n=7$.

Results

Let $g_3(n)$ denote maximum avoiding size and $f(n;3)=g_3(n)+1$ the live forcing threshold.

| $n$ | all triples | forbidden quadruples | $g_3(n)$ | live $f(n;3)$ | certification | |---:|---:|---:|---:|---:|:---| | 3 | 1 | 0 | 1 | 2 | (a), $n<2t$ | | 4 | 4 | 0 | 4 | 5 | (a), $n<2t$ | | 5 | 10 | 0 | 10 | 11 | (a), $n<2t$ | | 6 | 20 | 45 | 11 | 12 | (a), $n=2t$ | | 7 | 35 | 315 | 17 | 18 | (d), full exact search | | 8 | 56 | 1260 | 23 | 24 | (b)+(d), EKR symmetry + exact search |

(a) Lower witnesses.

$n=7$: all 15 triples through $0$, plus $123$ and $456$;
$n=8$: all 21 triples through $0$, plus $123$ and $456$.

Both are instances of the proved star-plus-matching construction.

(d) Computational-only upper certification. The constraint set was generated afresh twice and optimized independently:

OR-Tools CP-SAT 9.15.6755;
SciPy 1.17.1 / HiGHS mixed-integer optimization.

Both returned matching integer primal and certified upper bounds:

Direct construction/boundary checks: PASS
OR-Tools CP-SAT 9.15.6755: (n,t)=(7,3), variables=35,
  forbidden=315, fixed=none, optimum=17, bound=17
OR-Tools CP-SAT 9.15.6755: (n,t)=(8,3), variables=56,
  forbidden=1260, fixed=[(0,1,2),(3,4,5)], optimum=23, bound=23
SciPy 1.17.1 / HiGHS MILP: (n,t)=(7,3), optimum=17, bound=17
SciPy 1.17.1 / HiGHS MILP: (n,t)=(8,3), optimum=23, bound=23
Independent CP-SAT/HiGHS objectives agree: PASS

The returned witnesses were then checked separately by enumerating all unordered pairs of selected edges and comparing the unions of disjoint pairs. No solver-produced witness is accepted without that definition-level check.

5. Code and reproduction

The complete, standalone source is runs/erdos643_wavew004_verify.py. It:

generates all $t$-sets;
generates complementary pairs inside every $2t$-set;
generates every forbidden four-edge set;
constructs and directly checks the lower witnesses;
recomputes the elementary $n\leq2t$ formulas for $1\leq t\leq7$;
solves the $n=7,8,\ t=3$ models with both exact backends;
checks objective = certified bound and rechecks each witness from the original definition.

Run:

python runs/erdos643_wavew004_verify.py

The full run completed in about 34 seconds wall time on this VM. --quick omits the independent HiGHS run.

The core obstruction generator is:

for U in combinations(range(n), 2*t):
    pairs = []
    for A in combinations(U, t):
        B = tuple(sorted(set(U) - set(A)))
        if A < B:
            pairs.append((index[A], index[B]))
    for p, q in combinations(pairs, 2):
        forbidden.add(tuple(sorted(p + q)))

Each resulting quadruple receives the exact inequality sum(x[i] for i in quadruple) <= 3.

6. What this does and does not resolve

(a) Clean exact reduction. The complementary-pair formulation isolates the whole condition: every $2t$-set carries a perfect matching on its $t$-subsets, and an avoiding family may fully occupy at most one matching edge.

(a) Why a purely local count stalls. On each $2t$-set $U$, the $n=2t$ theorem gives

|\mathcal F\cap\tbinom Ut| \leq \frac12\binom{2t}{t}+1.

Double-counting pairs $(A,U)$, where $A\in\mathcal F$ and $A\subseteq U$, yields only

|\mathcal F| \leq \left(\frac12+\frac1{\binom{2t}{t}}\right)\binom nt.

This is order $n^t$, one full power of $n$ weaker than the desired order $n^{t-1}$. Thus treating the $2t$-set constraints independently cannot approach the conjecture.

(c) Exact missing structural ingredient. A successful asymptotic proof must exploit coherence between the complementary matchings belonging to many overlapping $2t$-sets. In quantified form, what remains is: for each fixed $t\geq3$ and each $\varepsilon>0$, prove that for sufficiently large $n$, every family of more than $(1+\varepsilon)\binom n{t-1}$ $t$-sets fully occupies two complementary pairs in one common $2t$-set. PiVe09 supplies global link/decomposition machinery strong enough for the constants $13/9$, $7/4$, and $1+2/\sqrt t$, but the inspected sources do not supply the stability/coherence lemma needed to make the constant $1$ for a fixed $t$.

(d) Scope warning. The exact values at $n=7,8$ and the elementary $n\leq2t$ regime do not give a uniform-in-$n$ estimate and therefore do not close the live asymptotic question.

PARTIAL: proved the exact boundary formula for every t at n<=2t and independently certified g_3(7)=17, g_3(8)=23 (live thresholds f(7;3)=18, f(8;3)=24); the asymptotic problem remains open.

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