Erdős problem #161, wave 5k

Date: 2026-07-26 (UTC)

Claim labels

• (a) elementary-rigorous: proved from first principles in this report.
• (b) rigorous-modulo-named-theorem/source: a cited theorem or a statement directly checked in a primary source.
• (c) plausible/structural-unverified: a conjectural route or a literature-search inference, not used as a theorem.
• (d) computational-only: a browser observation or finite computation; never promoted here to an infinite theorem.

Step 0: authoritative live-page audit

I fetched the rendered live page, its LaTeX endpoint, and the complete discussion thread through the Bright Data browser on 2026-07-26. The page displayed OPEN - $500, 0 claimed proofs for this problem, Interested in collaborating: None, and Currently working on this problem: None. It had been edited on 16 January 2026. Thus neither mandatory stop condition applied. (d)

Verbatim current statement

Let $\alpha\in[0,1/2)$ and $n,t\geq 1$. Let $F^{(t)}(n,\alpha)$ be the smallest $m$ such that we can $2$-colour the edges of the complete $t$-uniform hypergraph on $n$ vertices such that if $X\subseteq [n]$ with $\lvert X\rvert \geq m$ then there are at least $\alpha \binom{\lvert X\rvert}{t}$ many $t$-subsets of $X$ of each colour.

For fixed $n,t$ as we change $\alpha$ from $0$ to $1/2$ does $F^{(t)}(n,\alpha)$ increase continuously or are there jumps? Only one jump?

Everything else presently listed on the page

The page says that at \(\alpha=0\) this is the usual Ramsey function. It attributes the following assertions to the indicated literature:

• \(F^{(t)}(n,0)\asymp \log_{t-1}n\) would follow from the Erdős–Hajnal–Rado conjecture. (b)
• As printed, it says Erdős–Spencer imply

\[ F^{(t)}(n,\alpha)\gg_\alpha(\log n)^{1/(t-1)} \quad\text{for every }\alpha>0, \]

and that a similar upper bound holds when \(\alpha\) is close to \(1/2\). This exact printed claim is recorded here, but §2 explains an internal inconsistency in it. (d)

• Conlon–Fox–Sudakov prove, for every fixed \(\alpha>0\),

\[ F^{(3)}(n,\alpha)\ll_\alpha\sqrt{\log n}, \]

and the page says this gives only one asymptotic jump for \(t=3\), at \(0\). (b)

• For every \(\alpha>0\), the page also gives the weaker general lower bound

\[ F^{(t)}(n,\alpha)\gg_t(\log n)^{c_\alpha}. \]

(b)

• It links problem #563 for \(t=2\), and identifies this as problem #40 in the Ramsey Theory graph-problem collection. (d)

There are exactly three comments. Neel Somani (16 January 2026) observed that the earlier wording “largest \(m\)” was trivial and asked whether it should say “smallest \(m\)”; Thomas Bloom immediately confirmed the typo and the live statement now says “smallest.” Zach Hunter (18 October 2025) proposed a conditional route via a hypergraph analogue of Nikiforov’s blow-up theorem: dense copies of a fixed \(r\)-graph \(H\) should force an \(H\)-blow-up of order \(\delta(\log n)^{1/(r-1)}\). He contrasted this with the standard bound whose exponent depends on \(|V(H)|-1\). The site expressly marks comments as unverified; there is no proof claim in any comment. (d)/(c)

1. Two literal-definition defects

The endpoint \(\alpha=0\)

With the live phrase “at least,” every colouring has at least

\(0\binom{|X|}{t}=0\) edges of each colour on every \(X\). Under the natural convention \(m\geq1\), the literal definition therefore gives

not the usual inverse Ramsey function. If \(m\) is not required to be positive, there is no smallest \(m\) at all. (a)

The original Erdős chapter, p. 21, uses “more than”

\(\alpha\binom{|X|}{t}\), as does §6.2 of Conlon–Fox–Sudakov’s 2010 paper. Strict positivity at \(\alpha=0\) does recover the inverse Ramsey function. The original source also contained the now-corrected “largest” typo. The live edit appears to have fixed “largest/smallest” while changing the strict inequality and thereby breaking the endpoint. This source comparison was checked against the original scan and is machine-checked by the companion script’s --sources mode. (b)

All new finite results below are consequently stated only for

\(0<\alpha<1/2\), where “more than” versus “at least” affects only critical endpoints and the live at least convention is used exactly. (a)

“For fixed \(n,t\), continuously”

For finite \(n,t\), all relevant colour densities have the form

Thus \(F^{(t)}(n,\alpha)\), when defined, is an integer-valued step function of \(\alpha\); it cannot increase continuously in the literal analytic sense. The original source’s surrounding formulas compare orders of growth as \(n\to\infty\), so that asymptotic phase-transition question is plainly the substantive open interpretation. (a)/(b)

The live wording does not restrict \(m\leq n\). That is necessary: for some \(\alpha<1/2\), parity prevents even the full \(n\)-set from being sufficiently balanced, and then \(m=n+1\) is the first (vacuous) threshold. The exact theorem below adopts this necessary convention. (a)

2. A source-level inconsistency in the displayed known results

Let \(\delta=1/2-\alpha>0\), and colour every \(t\)-edge independently and fairly. For a fixed \(s\)-set \(X\), Hoeffding gives

Since \(\binom ns\leq(en/s)^s\) and

\(\binom{s}{t}\geq(s/t)^t\), a union bound over all \(s\geq C_{\alpha,t}(\log n)^{1/(t-1)}\) is less than \(1\) when

\(C_{\alpha,t}\) is sufficiently large. Hence, for every fixed

\(0<\alpha<1/2\),

(a)

If the live page’s earlier displayed lower bound with exponent

\(1/(t-1)\) really held for every \(\alpha>0\), (2.1) would already put every positive \(\alpha\) in the same asymptotic scale for every \(t\). That contradicts both the page’s later weaker \((\log n)^{c_\alpha}\) remark and its OPEN status. (a)/(d)

The primary sources resolve what was intended. Conlon–Fox–Sudakov state the matching \(1/(t-1)\) lower and upper estimates only when \(\alpha\) is sufficiently close to \(1/2\). Their general theorem gives merely a positive exponent depending on \(\alpha\). For \(t=3\), their later sharp almost-monochromatic theorem supplies exponent \(1/2\) for every fixed positive \(\alpha\). Thus the live page’s first \(\gg_\alpha\) assertion appears to have a reversed direction or misplaced quantifier. I do not silently use that inconsistent line as a theorem. (b)/(c)

3. New exact result for the complete regime \(n=t+2\)

For a colouring \(\chi\), write \(e_\chi(X)\) for the number of red

\(t\)-edges contained in \(X\). Define

Then, for \(\alpha>0\),

(a)

Theorem

Let \(N=t+2\geq3\), \(M=\binom N2\), and

For the live at least convention and every \(0<\alpha<1/2\),

with empty intervals omitted. (a)

Proof

If \(m\leq t=N-2\), an \(X\) of size \(t\) contains exactly one

\(t\)-edge, so one colour occurs zero times. Hence \(F>N-2\) for every \(\alpha>0\). Only thresholds \(N-1,N,N+1\) remain. (a)

Every \(t=N-2\) edge \(E\) has a complementary pair

\([N]\setminus E\). Declare that pair to be an edge of an ordinary graph \(G\) exactly when \(E\) is red. This is a bijection between the hypergraph colourings and graphs on \(N\) vertices. (a)

For \(X=[N]\setminus\{v\}\), its \(N-1\) many \(t\)-edges correspond exactly to the graph pairs incident with \(v\). Thus its red count is \(d_G(v)\). On the full set, the red count is \(e(G)\). Consequently

(a)

If \(N\) is even, \(N-1\) is odd, so every vertex contributes at most

\((N-2)/(2(N-1))\) to (3.4). If \(N\equiv1\pmod4\), the trivial upper bound is \(1/2\). If \(N\equiv3\pmod4\), put \(r=(N-1)/2\), which is odd. A value strictly larger than \((r-1)/(2r)\) would force \(d_G(v)=r\) at every vertex. But \(Nr\) is odd, contradicting the handshake lemma. These are exactly the three upper bounds \(q_N\) in (3.2). (a)

They are all attained explicitly:

1. If \(N\) is even, take any \((N-2)/2\)-regular graph. A circulant is obtained by joining cyclic offsets \(\pm1,\ldots\), adding the antipodal matching when the desired degree is odd. Every star has minority \((N-2)/2\), and the whole-graph minority has the same density \(q_N\). (a)

2. If \(N\equiv1\pmod4\), the degree \((N-1)/2\) is even. Joining the corresponding positive and negative cyclic offsets gives an \((N-1)/2\)-regular graph on \(\mathbb Z_N\), balancing every star and the whole graph exactly. (a)

3. Let \(N=4a+3\). On \(\mathbb Z_{4a+2}\), start with the \((2a+1)\)-regular circulant using offsets \(\pm1,\ldots,\pm a\) and the antipodal matching. Delete \(a\) disjoint antipodal edges, introduce a new vertex \(\infty\), and join \(\infty\) to all \(2a\) endpoints of the deleted edges. Every old vertex still has degree \(2a+1\), while \(d(\infty)=2a\). The total edge count is \((N(2a+1)-1)/2=\lfloor M/2\rfloor\), so (3.4) equals

\[ \frac{2a}{4a+2}=\frac{N-3}{2(N-1)}=q_N. \]

(a)

This proves \(Q_{N-1}=q_N\). For \(m=N\), only the full set is tested, so splitting its \(M\) edges as evenly as possible gives and proves

\(Q_N=p_N\). For \(m=N+1\) the condition is vacuous. Equation (3.3) now follows from (3.1). (a)

Smallest literal multi-jump examples

For \(t=4,N=6\),

so

Thus the literal fixed-\(n,t\) function has two distinct jumps inside

\((0,1/2)\). (a)

An explicit witness for the first interval is the six-cycle on complementary pairs

Equivalently, colour the six \(4\)-sets

red and the other nine blue. Every \(5\)-set has two red and three blue edges. For the middle interval, any \(7\)-versus-\(8\) split works because only the full \(6\)-set is tested. (a)

For \(t=5,N=7\), the two critical values are \(1/3\) and \(10/21\), giving the three values \(6,7,8\). (a)

These examples answer the live question negatively if “for fixed \(n,t\)” is taken literally. They do not settle Erdős’s intended asymptotic phase-transition question. (a)

4. Independent verification

The standalone checker is erdos161_wave5k_verify.py. It uses only the Python standard library and exact Fraction arithmetic. (d)

It performs independent checks rather than merely replaying the proof:

1. It constructs the three residue-class graph witnesses for every

\(3\leq N\leq40\), translates complementary pairs back to

\((N-2)\)-edges, and directly recounts every relevant \(N-1\) and \(N\) subset. (d)

2. It Gray-code enumerates all \(2^{\binom N2}\) graphs for every

\(3\leq N\leq7\), recomputing \(Q_{N-1}\) and \(Q_N\) without assuming the formulas. This includes all \(2^{21}=2{,}097{,}152\) colourings at \(N=7\). (d)

3. With --sources, it independently downloads the arXiv TeX and asserts the exact literature phrases used below, checks the original Google Books p. 21 OCR phrase “every class contains more than,” and checks the Erdős and Rödl–Schacht DOI metadata through Crossref. (d)

Reproduction:

$ python runs/erdos161_wave5k_verify.py --sources
Constructive/direct checks passed for 3 <= N <= 40.
N=3, t=1: exhaustive Q_(N-1)=0, Q_N=1/3; F=3 for 0<alpha<=1/3; F=4 for 1/3<alpha<1/2
N=4, t=2: exhaustive Q_(N-1)=1/3, Q_N=1/2; F=3 for 0<alpha<=1/3; F=4 for 1/3<alpha<1/2
N=5, t=3: exhaustive Q_(N-1)=1/2, Q_N=1/2; F=4 for 0<alpha<1/2
N=6, t=4: exhaustive Q_(N-1)=2/5, Q_N=7/15; F=5 for 0<alpha<=2/5; F=6 for 2/5<alpha<=7/15; F=7 for 7/15<alpha<1/2
N=7, t=5: exhaustive Q_(N-1)=1/3, Q_N=10/21; F=6 for 0<alpha<=1/3; F=7 for 1/3<alpha<=10/21; F=8 for 10/21<alpha<1/2
ALL CHECKS PASSED
PRIMARY-SOURCE TEXT CHECKS PASSED.

The displayed run rounds away only elapsed wall time; all mathematical comparisons in the program are exact. (d)

5. Primary-literature audit through July 2026

1. Paul Erdős, “Problems and Results on Graphs and Hypergraphs: Similarities and Differences,” Mathematics of Ramsey Theory (1990), pp. 12–28, DOI 10.1007/978-3-642-72905-8_2, poses the question on p. 21. The accessible book scan confirms the strict “more than” convention and the asymptotic discussion. (b)

2. David Conlon, Jacob Fox, and Benny Sudakov, “Hypergraph Ramsey numbers,” JAMS 23 (2010), 247–266, arXiv:0808.3760, §6.2, explicitly restate this \(F^{(k)}(N,\alpha)\) problem. Their Theorem 6.1 proves that for every uniformity and every target error there is some positive exponent \(\beta\), yielding the page’s \((\log N)^{c_\alpha}\) lower bound. (b)

3. The same authors’ “Large almost monochromatic subsets in hypergraphs,” Israel J. Math. 181 (2011), 423–432, arXiv:0901.3912, proves that every colouring of triples has an \(s=c_\epsilon\sqrt{\log N}\) set with at least a \(1-\epsilon\) fraction in one colour. Together with the random upper bound, this settles the growth scale for \(t=3\). (b)

4. Vojtěch Rödl and Mathias Schacht, “Complete Partite Subgraphs in Dense Hypergraphs,” Random Structures & Algorithms 41 (2012), 557–573, DOI 10.1002/rsa.20441, formulate the required hypergraph Nikiforov statement as their Problem 2 and note that even special \(3\)-graph cases are open. (b)

5. Pavel Pudlák and Vojtěch Rödl, “Colorings of \(k\)-sets with low discrepancy on small sets,” JCTB 178 (2026), 79–103, arXiv:2402.05286v3, explicitly call Erdős’s transition problem “still open in full generality.” Their theorem concerns growing uniformity with \(m-k\ll k\); they expressly say it gives no dependence on \(m\), so it does not resolve fixed \(t\) here. (b)

6. Jacob Fox, Yuval Wigderson, and Yunkun Zhou, “Finding blowups one vertex at a time,” arXiv:2605.23301, submitted 22 May 2026, improve the graph Nikiforov theorem but explicitly state that its extension to hypergraphs “remains an outstanding open problem.” This is the newest directly relevant primary source I found. (b)

I searched exact \(F^{(t)}(n,\alpha)\) phrases, arXiv, Crossref, the citation graph of the 2011 CFS paper, and recent work citing Nikiforov/Rödl–Schacht. I found no primary source proving the fixed-\(t\geq4\) positive-\(\alpha\) exponent \(1/(t-1)\). This is an honest search miss, not a proof that no unindexed result exists. (c)

6. Exact asymptotic reduction and the wall

Here is a precise sufficient missing lemma.

> Hypergraph Nikiforov hypothesis. For every fixed \(r\)-uniform

> hypergraph \(H\) on \(h\) vertices and every \(c>0\), there are

> \(\delta,n_0>0\) such that every \(r\)-graph \(G\) on \(n\geq n_0\)

> vertices containing at least \(cn^h\) copies of \(H\) contains a

> balanced \(s\)-blow-up \(H(s)\) with

> \[ > s\geq\delta(\log n)^{1/(r-1)}. > \]

This hypothesis is open for \(r\geq3\). (c)

It would give the missing lower bound for #161 as follows. Fix

\(t,\alpha>0\), and choose \(d\) so large that

In every red/blue colouring, Ramsey averaging gives

\(\Omega_{t,d}(n^d)\) monochromatic copies of \(K_d^{(t)}\) in one colour: every \(R_t(d;2)\)-set contains one, and double-counting over those sets proves the density. (a)

Apply the hypothesis to that colour and \(H=K_d^{(t)}\). The resulting blow-up has \(ds\) vertices and

monochromatic \(t\)-edges. Its density among all \(\binom{ds}{t}\)

edges tends to the left side of (6.1), so for large \(n\) the other colour has density below \(\alpha\). Therefore every colouring has a bad set of size

\(\Omega_{\alpha,t}((\log n)^{1/(t-1)})\), proving

Together with (2.1), this would put every fixed \(\alpha>0\) in the same scale. The implication is elementary; its hypothesis is the unproved step. (a)/(c)

Standard dense-hypergraph machinery applied to the auxiliary

\(d\)-uniform copy hypergraph produces only a blow-up of order roughly

\((\log n)^{1/(d-1)}\). Since \(d\) must grow as the requested error

\(\alpha\) shrinks, this yields only an exponent \(c_\alpha\), exactly the known general result. The missing improvement is to replace the auxiliary exponent \(1/(d-1)\) by the ambient-uniformity exponent \(1/(t-1)\). The May 2026 Fox–Wigderson–Zhou method achieves the graph case but does not yet cross this hypergraph barrier. (b)/(c)

This is not a finite-computation wall: no table at bounded \(n\) can establish the uniform \(n\to\infty\) blow-up statement. For scale, the first nearby unhandled brute-force instance \(t=4,n=7\) already has \(2^{35}\) colourings, while \(t=4,n=8\) has \(2^{70}\); such searches may give additional finite data but cannot supply the missing uniform lemma. (a)/(d)

Bottom line

The work gives a uniform closed form for every live finite instance

\(n=t+2\), explicit constructions, exhaustive confirmation through \(t=5\), and literal examples with two positive-\(\alpha\) jumps. It also isolates two transcription defects and the exact asymptotic blow-up lemma still missing. It does not claim to resolve the intended fixed-\(t\geq4\), \(n\to\infty\) prize problem. (a)/(b)/(d)

PARTIAL: proved the exact closed form for all n=t+2 (including literal two-jump examples t=4,n=6 and t=5,n=7), verified it exhaustively, and isolated hypergraph Nikiforov as the current asymptotic wall.