Erdős problem #837 — wave 7o

Access date: 2026-07-27 UTC.

Outcome

I do not solve for all of \(A_3\). I obtain two verifiable partial results and one precise audit finding:

1. [(b) rigorous modulo Erdős's complete-partite embedding theorem]

\[ \boxed{A_3\cap[0,2/9)=\{0\}.} \] This is a sharp classification of the whole regime below the first hypergraph jump barrier.

1. [(a) elementary-rigorous, independently checked] Among all nonempty

3-graphs on at most five vertices, the smallest Lagrangian strictly greater than \(2/9\) is \[ \alpha_*=\frac{189+15\sqrt5}{961} =0.2315723409599342824621619\ldots , \] attained by \[ F_*=\{123,124,125,345\}. \] Optimal blow-ups of \(F_*\) give an explicit boundary obstruction at \(\alpha_*\).

1. [(a)+(d) exact source/arithmetic audit] A tempting argument that

\(\alpha_*\in A_3\) does not verify. Baber--Talbot's displayed jump interval ends at the rounded decimal \(0.2316\), but the strict Lagrangian condition used in their proof ends at the smaller exact number \(\alpha_*<0.2316\). Their argument proves jumps below \(\alpha_*\), not at \(\alpha_*\). The exact missing lemma is therefore: prove that \(\alpha_*\) itself is a jump for 3-graphs. I found no later primary source that supplies that endpoint argument.

The standalone checker is erdos837_wave7o_reverify.py.

Claim labels

• (a) elementary-rigorous;
• (b) rigorous modulo the explicitly named theorem;
• (c) plausible/structural-unverified;
• (d) computational-only or machine-observed.

No claim below is promoted from (c) or (d) to a theorem.

Step 0: live-page gate

[(d) machine-observed] I fetched both the live problem page and its LaTeX-source view through the Bright Data browser path:

• live problem #837;
• live LaTeX-source view.

The live page showed:

• status: OPEN;
• comments: 0;
• claimed proofs: 0;
• “Interested in collaborating”: None;
• “Currently working on this problem”: None;
• “I am working on formalising the results”: None.

Thus the mandatory no-collision gate passed.

Verbatim live statement

Let \(k\geq 2\) and \(A_k\subseteq [0,1]\) be the set of \(\alpha\) such that there exists some \(\beta(\alpha)>\alpha\) with the property that, if \(G_1,G_2,\ldots\) is a sequence of \(k\)-uniform hypergraphs with \[ > \liminf \frac{e(G_n)}{\binom{\lvert G_n\rvert}{k}} >\alpha > \] then there exist subgraphs \(H_n\subseteq G_n\) such that \(\lvert H_n\rvert \to \infty\) and \[ > \liminf \frac{e(H_n)}{\binom{\lvert H_n\rvert}{k}} >\beta, > \] and further that this property does not necessarily hold if \(>\alpha\) is replaced by \(\geq \alpha\).

What is \(A_3\)?

The only listed known result is, verbatim:

A problem of Erdős and Simonovits. It is known that \[ > A_2 = \left\{ 1-\frac{1}{k} : k\geq 1\right\}. > \]

The page expands its citation as:

[Er74d] Erdős, Paul, Unsolved Problems. (1974), 278--297. MR 360350.

Necessary order convention

[(a)] The displayed statement omits the hypothesis \(\lvert G_n\rvert\to\infty\). Read literally, one may repeat a fixed complete \(k\)-graph, and then no \(H_n\) can have growing order. That would make every \(A_k\) empty, contradicting the same page's nonempty formula for \(A_2\). I therefore use the forced intended convention

Every result in this report uses that convention.

Primary-source literature audit

The following are the only external mathematical results used.

1. [(b)] Erdős's complete-partite embedding theorem. In

P. Erdős, On some extremal problems on \(r\)-graphs, Discrete Math. 1 (1971), 1--6, Erdős proves in particular that every \(r\)-partite \(r\)-graph has Turán density zero. Equivalently for the use here: for every \(\eta>0\) and fixed \(t\), every sufficiently large 3-graph of density at least \(\eta\) contains \(K^{(3)}_{t,t,t}\).

1. [(b)] Frankl--Rödl's jump criterion. The finite-family/Lagrangian

characterization is Theorem 1.2 as quoted and used in R. Baber and J. Talbot, Hypergraphs do jump, arXiv:1004.3733, published in Combinatorics, Probability and Computing 20 (2011), 161--171, DOI 10.1017/S0963548310000222. It requires the strict inequality \(\min_{F\in\mathcal F}\lambda(F)>\alpha\).

1. [(b)] Strong/weak jumps. Johnston--Lu prove that non-strong-jump

values are exactly densities of suitable hereditary properties and characterize them by flat admissible sequences: T. Johnston and L. Lu, Strong Jumps and Lagrangians of Non-Uniform Hypergraphs, arXiv:1403.1220. This explains the standard terminology: the values sought here are the boundary, or weak-jump, values rather than interiors of jump intervals. My low-density proof below is direct and does not depend on identifying every nuance of the page wording with their definition.

1. [(b)] Exact irrational Turán density. Baber--Talbot later proved

that \(\alpha_*\) is the Turán density of a finite family and gave the same extremal blow-up: New Turán densities for 3-graphs, arXiv:1110.4287, Electronic J. Combin. 19(2) (2012), P22, DOI 10.37236/2360. Being a Turán density supplies a boundary obstruction, but does not by itself prove that the number is a jump.

1. [(b) current-state check] Shaw's 2025 paper still states that

\(2/9\) being a jump is open and safely records the first numerical interval only through \(0.2315\): B. R. Shaw, Minimal hypergraph non-jumps, arXiv:2506.09620. The newer paper X. Liu and D. Mubayi, The number \(4/9\) is a non-jump for 3-graphs, arXiv:2605.13567 proves that \(4/9\) is a non-jump and describes the remaining picture as largely open. Neither paper supplies the missing endpoint proof at \(\alpha_*\).

[(d) literature-search result] Searches by the exact algebraic number, the decimal \(0.2315723409\ldots\), “weak jump,” and the endpoint \(2/9\) found no primary source proving that \(\alpha_*\) is a jump and no correction resolving the rounding issue below. This is a reported search miss, not a proof that no such source exists.

Fixed-order jumps versus the page's sequence formulation

[(a)] The usual fixed-order definition of a jump is equivalent to the strict-\(>\alpha\) sequence property on the live page (under the necessary order convention above). If a standard jump has constant \(c>0\), take \(\beta=\alpha+c/2\) and diagonalize the required fixed subgraph order \(t\to\infty\). Conversely, suppose the page property holds with \(\beta>\alpha\). If the fixed-order property failed with \(c=(\beta-\alpha)/2\), there would be some \(\varepsilon>0\), some fixed \(t\), and arbitrarily large counterexamples of density at least \(\alpha+\varepsilon\). The page property would give growing subgraphs of density eventually greater than \(\beta\); averaging their induced \(t\)-vertex subgraphs would produce a \(t\)-vertex subgraph of density greater than \(\alpha+c\), a contradiction.

The low-density classification

Write

and let \(B_t=K^{(3)}_{t,t,t}\), the complete 3-partite 3-graph with three classes of order \(t\).

Lemma 1: the \(2/9\) ceiling of complete tripartite blow-ups

[(a)]

More generally, if a subgraph of a complete tripartite 3-graph uses \(x,y,z\) vertices from its three classes and \(m=x+y+z\), then

AM--GM gives \(xyz\leq(m/3)^3\), and hence, whenever \(m\to\infty\),

Thus no sequence of growing subgraphs of balanced complete tripartite 3-graphs has limiting density strictly greater than \(2/9\).

Lemma 2: positive density forces growing \(B_t\)

[(b), modulo Erdős 1971] Fix \(\eta>0\). Erdős's theorem says that, for every fixed \(t\), every sufficiently large 3-graph of density at least \(\eta\) contains \(B_t\). A standard diagonal choice of \(t=t(n)\) therefore gives \(t(n)\to\infty\) along any sequence whose orders tend to infinity and whose densities are eventually at least \(\eta\).

Theorem

[(b), with all other steps elementary]

Proof that \(0\in A_3\). If \(\liminf d(G_n)>0\), choose \(\eta>0\) below this liminf. Lemma 2 produces \(H_n=B_{t(n)}\subseteq G_n\), with \(t(n)\to\infty\), and \(d(H_n)\to2/9\). Consequently every fixed

witnesses the strict-\(>0\) part of the page's property. If \(>0\) is replaced by \(\geq0\), the sequence of empty 3-graphs is a counterexample for every \(\beta>0\). Hence \(0\in A_3\).

Proof that \(0<\alpha<2/9\) is not in \(A_3\). First, any \(\beta\) that could witness the strict-\(>\alpha\) property must satisfy \(\beta<2/9\): take \(G_n=B_n\), whose density tends to \(2/9>\alpha\); equation (1) rules out every \(\beta\geq2/9\).

Now suppose only that \(\liminf d(G_n)\geq\alpha\). Eventually \(d(G_n)\geq\alpha/2>0\), so Lemma 2 again supplies growing \(B_{t(n)}\)'s of density tending to \(2/9\). Therefore the property continues to hold at equality for every possible witness \(\alpha<\beta<2/9\). The page's required failure at equality cannot occur. Thus \(\alpha\notin A_3\). \(\square\)

This proof also isolates the first undecided boundary:

[(a)+(b)] Balanced tripartite blow-ups show failure at equality for \(\alpha=2/9\), while membership of \(2/9\) in \(A_3\) is equivalent to the famous still-open assertion that \(2/9\) is a jump for 3-graphs.

Exact five-vertex Lagrangian gap

For a 3-graph \(F\) on \([v]\), use the normalized Lagrangian

Pair-cover lemma

[(a)] There is an optimal weighting of minimum support in which every pair of support vertices lies together in an edge contained in the support.

Indeed, if support vertices \(i,j\) never occur together in such an edge, the Lagrangian polynomial has no \(x_ix_j\) term. Holding all other weights and \(x_i+x_j\) fixed makes it affine in \(x_i\). Moving to the better endpoint sets one of \(x_i,x_j\) to zero without decreasing the value, contradicting minimal support.

Five-vertex classification

[(a), with an exhaustive exact check in the script] Let \(F\) be a nonempty 3-graph on at most five vertices.

• If \(F\) contains \(K_4^-=\{123,124,134\}\), then

\(\lambda(F)\geq\lambda(K_4^-)=8/27\). For completeness, if \(x_1\) is the weight of the degree-three vertex and \(s=1-x_1\), then \[ 6x_1(x_2x_3+x_2x_4+x_3x_4) \leq 2x_1s^2\leq 8/27, \] with equality at \(x_1=1/3\) and \(x_2=x_3=x_4=2/9\).

• If \(F\) has at least five edges, uniform weights give

\(\lambda(F)\geq6\cdot5/5^3=6/25\).

• It remains to consider at most four edges, no \(K_4^-\). Unless four

edges cover every pair of five vertices, the pair-cover lemma reduces an optimum to at most four vertices. A \(K_4^-\)-free 3-graph on four vertices has at most two edges, whose 2-shadow is not complete; another reduction leaves one edge and value \(2/9\).

• There is exactly one four-edge, five-vertex exception with complete

2-shadow. To see this without trusting enumeration, take the complements of its four triples; these form a four-edge ordinary graph \(Q\) on five vertices. Complete 2-shadow is equivalent to \(Q\) having no two-vertex cover, i.e. \(\alpha(Q)\leq2\). Thus \(\overline Q\) is a triangle-free five-vertex graph with six edges. Equality in Mantel's theorem forces \(\overline Q=K_{2,3}\), so \(Q=K_2\sqcup K_3\). Complementing its edges gives, up to isomorphism, \[ F_*=\{123,124,125,345\}. \]

The checker independently enumerates all \(2^{10}=1024\) labelled 3-graphs and all 34 isomorphism classes and confirms that this is the unique exception.

Exact optimization of \(F_*\)

[(a)] Put \(s=x_3+x_4+x_5\) and \(p=x_1+x_2=1-s\). Then

Both inequalities are simultaneously sharp at \(x_1=x_2=p/2\) and \(x_3=x_4=x_5=s/3\). Write \(b=s/3\), so \(a=p/2=(1-3b)/2\). The one-variable polynomial is

with

The two critical points are

Checking \(0,b_-,b_+,1/3\) gives the global maximum at \(b_-\):

It follows that every nonempty 3-graph on at most five vertices has

and equality in the second alternative first occurs at \(F_*\).

The checker also verifies exactly that

and

Explicit flat construction at \(\alpha_*\)

[(a)] Blow up the five vertices of \(F_*\) into classes with limiting proportions

and insert all cross-class triples prescribed by \(F_*\). Call the result \(G_n\). Then

If a subgraph \(H\subseteq G_n\) takes \(m_i\) vertices from class \(i\) and \(m=\sum m_i\), then

Putting \(y_i=m_i/m\) and using the Lagrangian calculation gives

Thus every sequence \(H_n\subseteq G_n\) with \(|H_n|\to\infty\) has \(\limsup d(H_n)\leq\alpha_*\). This is an explicit, from-scratch counterexample to the equality version for every \(\beta>\alpha_*\).

Consequently:

[(a)]

The right side of (4) is exactly the missing uniform statement; finite blow-up calculations alone cannot establish it.

The \(0.2316\) rounding audit

Baber--Talbot's Theorem 1.1 is printed as:

Their proof uses a finite family \(\mathcal F'\) containing \(F_*\), the bound

and the Frankl--Rödl requirement

The same paper explicitly computes

The last proof step writes this exact number as \(0.2316\). But (2) shows that, as exact real numbers,

Therefore the displayed argument rigorously yields

but it does not yield \(\alpha_*\), nor the tiny interval \((\alpha_*,0.2316)\). This strictness is not cosmetic: at \(\alpha=\alpha_*\), the hypothesis \(\lambda(F_*)>\alpha\) becomes equality, and construction (3) is exactly the obstruction that prevents replacing it by a non-strict inequality.

[(d) audit conclusion, not a literature theorem] I therefore do not count \(\alpha_*\) as a verified member of \(A_3\), despite the rounded published interval. A proof of the endpoint would require a different finite family \(\mathcal G\) satisfying

or some equivalent uniform argument.

Additional exact exclusions and boundary points

These statements are not a classification of all \(A_3\); they show what the standard machinery actually certifies.

For the two “no members” numerical intervals, the direct logic is the same as below \(2/9\): the upper-end template bounds how large any witness \(\beta\) can be, while supersaturation above the lower Turán bound makes the equality hypothesis force growing blow-ups approaching that upper Lagrangian.

Reproduction

Run:

python runs/erdos837_wave7o_reverify.py

Observed output:

PASS: exact Q(sqrt(5)) identities and comparisons
alpha = (189+15*sqrt(5))/961 = 0.231572340959934282462161919907356028648917040
minimal polynomial: 961*x^2 - 378*x + 36
exact audit: 0.2315 < alpha < 0.2316
five-vertex census: 1024 labelled, 34 unlabelled, 1 exceptional four-edge class
grid check through order 30: max 6e/m^3 = 3618/15625 at counts (8, 8, 3, 3, 3), always <= alpha
F_* blow-ups from optimal limiting weights (finite densities may approach from above):
  n= 25 sizes=(7, 7, 3, 3, 5) density=0.253913043478
  n= 50 sizes=(15, 15, 6, 6, 8) density=0.244285714286
  n=100 sizes=(31, 31, 12, 12, 14) density=0.238305504020
  n=200 sizes=(63, 63, 24, 24, 26) density=0.235025125628
  n=500 sizes=(158, 158, 60, 60, 64) density=0.232937006543
ALL CHECKS PASSED

The checker uses only the Python standard library. It:

• implements exact arithmetic in \(\mathbb Q(\sqrt5)\);
• checks the weights, critical points, value, minimal polynomial, and all

rational endpoint comparisons;

• enumerates the 1024 labelled five-vertex 3-graphs and canonicalizes

them under all 120 vertex permutations;

• confirms the unique four-edge full-shadow exception;
• exhaustively checks every five-class integer profile through order 30;
• recomputes finite members of the obstruction blow-up sequence.

The finite grid is marked (d) and is only a sanity check. The uniform inequality (3) is the elementary proof.

Exact wall and computation cost

[(a)+(b)] The full problem asks for the weak/boundary jumps inside a largely unknown hypergraph Turán-density set. The first missing uniform lemma is already the famous question whether \(2/9\) is a jump. The next small-template boundary isolated here requires proving that \(\alpha_*\) is a jump. Neither follows from any finite census without a finite-family Turán certificate satisfying a strict Lagrangian gap.

[(d) order-of-magnitude cost estimate] A naive seven-vertex census has \(2^{\binom73}=2^{35}=34,359,738,368\) labelled 3-graphs. Bare bit tests are feasible in roughly \(1\)--\(10\) core-hours in optimized native code, but isomorphism reduction plus repeated exact Lagrangian or SDP work realistically raises a broad search to \(10^2\)--\(10^3\) core-hours. At eight vertices the labelled space is \(2^{56}\approx7.21\times10^{16}\); even an unrealistic 50 million masks per second costs about \(4.0\times10^5\) core-hours before optimization. More importantly, such a census still lacks the finiteness/uniformity step required by Frankl--Rödl. I did not run it.

PARTIAL: Proved \(A_3\cap[0,2/9)=\{0\}\), certified the exact five-vertex Lagrangian gap at \((189+15\sqrt5)/961\), and isolated the unproved endpoint-jump lemma hidden by the published \(0.2316\) rounding.