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.

2. [(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_*\).

3. [(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](https://users.renyi.hu/~p_erdos/1971-09.pdf),

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}\).

2. [(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](https://arxiv.org/abs/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\).

3. [(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](https://arxiv.org/abs/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.

4. [(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.

5. [(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](https://arxiv.org/abs/2506.09620).

The newer paper

[X. Liu and D. Mubayi, *The number \(4/9\) is a non-jump for

3-graphs*, arXiv:2605.13567](https://arxiv.org/abs/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.

| regime/value | verified fact | consequence for \(A_3\) | label |

|---|---|---|---|

| \(0\) | jump plus empty-graph boundary obstruction | \(0\in A_3\) | (b) |

| \(0<\alpha<2/9\) | equality already forces density tending to \(2/9\) | no members | (b) |

| \(2/9\) | balanced tripartite flat construction; jump status open | member iff \(2/9\) is a jump | (a)+(b) |

| \(0.2299<\alpha<\alpha_*\) | Baber--Talbot finite-family bound gives a strong jump interval | no members | (b) |

| \(\alpha_*\) | explicit flat construction; endpoint jump not verified | member iff endpoint jump is proved | (a) |

| \(0.2871<\alpha<8/27\) | \(\pi(K_4^-)\leq0.2871\), \(\lambda(K_4^-)=8/27\) | no members | (b) |

| \(8/27\) | optimal \(K_4^-\) blow-ups are flat; endpoint jump not supplied by cited interval | conditional candidate | (a)+(d) |

| \(4/9\) | Liu--Mubayi prove it is a non-jump | not a member | (b) |

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.