Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?

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 $\alpha$ ranges from $0$ to $1/2$, does $F^{(t)}(n,\alpha)$ increase continuously, or are there jumps? Is there only one jump? (erdosproblems.com/161, citing [Er90b, p.21])

Facts

- Prize $500; status open on erdosproblems.com as a whole statement ("cannot be resolved with a finite computation," it is a claim about growth rates for all $n,t$), though the $t=3$ special case is fully settled (see Literature state) — we mark this page partially-resolved to reflect that split honestly. - Falsifiable: no for the general/all-$t$ statement (an asymptotic growth-rate/continuity claim). The $t=3$ sub-case has already been settled by a genuine proof, not a finite computation. - Origin: Erdős [Er90b, p.21] ("Some of my favourite problems and results"); Erdős's own words quoted on the page: "If I can hazard a guess completely unsupported by evidence, I am afraid that the jump occurs all in one step at $0$. It would be much more interesting if my conjecture would be wrong and perhaps there is some hope for this for $t>3$." - Known results / best bounds (all read directly from erdosproblems.com/161's remarks, cross-checked against the CFS abstracts): - $\alpha=0$: $F^{(t)}(n,0)$ is the usual hypergraph Ramsey function; the Erdős–Hajnal–Rado conjecture (Erdős #562 — Erdős–Hajnal–Rado hypergraph Ramsey growth rate: SOLVED at the ≥4-colour endpoint via the stepping-up lemma (2-colour case still open)) implies $F^{(t)}(n,0)\asymp\log_{t-1}n$ ($(t-1)$-fold iterated log — a tower-type growth rate). - Lower bound for all $\alpha>0$ (Erdős–Spencer, via the probabilistic method): $F^{(t)}(n,\alpha)\gg_\alpha(\log n)^{1/(t-1)}$, with a matching-shape upper bound near $\alpha=1/2$. - $t=3$ is resolved: Conlon, Fox, Sudakov [CFS11] = arXiv:0901.3912 prove that for any fixed $\alpha>0$, $F^{(3)}(n,\alpha)\ll_\alpha\sqrt{\log n}$. Combined with the Erdős–Spencer lower bound $(\log n)^{1/(t-1)}=(\log n)^{1/2}$ at $t=3$, this pins $F^{(3)}(n,\alpha)$ to $\Theta_\alpha((\log n)^{1/2})$ for every fixed $\alpha>0$ — a single order of magnitude for all $\alpha\in(0,1/2)$, strictly separated from the tower-type $F^{(3)}(n,0)$. This proves: for $t=3$, there is exactly one jump, at $\alpha=0$ — i.e. the $t=3$ case of Erdős's problem is answered (in favor of his own guess). - For general $t\geq4$, only $F^{(t)}(n,\alpha)\gg_t(\log n)^{c_\alpha}$ is known (no matching upper bound of the CFS type) — genuinely open, continuity/single-jump unresolved for $t\geq4$. - See also Erdős #563 — the graph (t=2) discrepancy-Ramsey function F(n,α) has order Θ_α(log n) for the $t=2$ (graph) analogue, where $F(n,\alpha)\asymp_\alpha\log n$ is known via the probabilistic method but the *exact* constant $c_\alpha$ in $F(n,\alpha)\sim c_\alpha\log n$ remains open. - This problem is #40 in "Ramsey Theory" in the graphs problem collection (mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/GeneralizedHypergraphRamsey.html). - Related problems: Erdős #562 — Erdős–Hajnal–Rado hypergraph Ramsey growth rate: SOLVED at the ≥4-colour endpoint via the stepping-up lemma (2-colour case still open) — the $\alpha=0$ growth-rate conjecture this problem's $\alpha=0$ endpoint depends on; Erdős #563 — the graph (t=2) discrepancy-Ramsey function F(n,α) has order Θ_α(log n) — the $t=2$ graph case, open only for the sharp constant.

Literature state

Partially resolved in the literature, and this is the single most important finding: the $t=3$ case of Erdős's question is already fully answered by Conlon, Fox, and Sudakov, "Large almost monochromatic subsets in hypergraphs," arXiv:0901.3912 (Israel J. Math. 181 (2011), 423-432). Their abstract states directly that they answer "an open question of Erdős and Hajnal from 1989 on discrepancy in hypergraphs," proving that every 2-colouring (more generally $\ell$-colouring) of the triples of an $N$-set contains a subset of size $c\sqrt{\log N}$ that is $(1-\epsilon)$-monochromatic — the bound underlying erdosproblems.com's cited $F^{(3)}(n,\alpha)\ll_\alpha\sqrt{\log n}$. A companion paper by the same three authors, "Erdős-Hajnal-type theorems in hypergraphs," arXiv:1104.5544 (JCTB 102 (2012), 1142-1154), independently reproves the unconditional $c(\log n)^{1/2}$ bound for ALL 3-uniform hypergraphs (not just $H$-free ones) and, crucially, proves that no analogous statement can hold for $k$-uniform hypergraphs with $k>3$ in the Erdős–Hajnal (induced-subgraph) sense — a structural obstruction that plausibly explains why the general-$t$ case of #161 has resisted the same technique.

For $t\geq4$ nothing beyond the old Erdős–Spencer lower bound $F^{(t)}(n,\alpha)\gg_t(\log n)^{c_\alpha}$ was found in any source searched (Mubayi–Suk survey homepages.math.uic.edu/~mubayi/papers/HypRamSurvey_050618.pdf, which cites the CFS paper as [20] but does not report any $t\geq4$ discrepancy-jump improvement; general arXiv/OpenAlex/WebSearch sweeps for "$F^{(t)}(n,\alpha)$", "hypergraph discrepancy jump $t$-uniform", "quasi-Ramsey $k$-uniform" turned up related-but-distinct results — e.g. Kang–Patel–Regts, "Discrepancy and large dense monochromatic subsets," arXiv:1610.06359, which generalizes *quasi-Ramsey numbers* (degree-based, not the same $F^{(t)}$) to multiple colours/uniform hypergraphs and reports $c_1(\log\log\cdots\log n)^{1/4}\leq f^{(k)}_{s,s+1}(n)\leq c_2(\log n)^{1/(k-2)}$ for $k\geq4$ — a large, unclosed gap in that adjacent problem, consistent with $t\geq4$ genuinely being open here too).

A distinct but confusingly similarly-named problem — Erdős's "jumping constant conjecture" for hypergraph Turán densities (is every $\alpha\in[0,1)$ a Turán-density jump for $r$-uniform hypergraphs, $r\geq3$?) — was disproved by Frankl and Rödl (giving explicit non-jump densities); see arXiv:1004.3733 "Hypergraphs do jump" for a survey of that separate line. This is NOT the same "jump" as #161's discrepancy-Ramsey jump (different function, different notion of "jump" — one is about Turán density thresholds, the other about the two-colour discrepancy function $F^{(t)}(n,\alpha)$) and should not be conflated with it, though both trace to Erdős-era hypergraph extremal questions.

On erdosproblems.com's own forum for #161 (fetched directly, 3 comments): Zach Hunter (18 Oct 2025) proposes that a full resolution for general $t$ would follow from a "hypergraph Nikiforov" conjecture: for any $r$-uniform hypergraph $H$ and $c>0$, there is $\delta>0$ such that any $n$-vertex hypergraph $G$ with $\geq cn^{|V(H)|}$ copies of $H$ contains a $t$-blow-up of $H$ with $t>\delta(\log n)^{1/(r-1)}$ — and notes explicitly that "the partial result of Conlon, Fox, and Sudakov works by observing that standard hypergraph Turán finds a $t$-blow-up with $t>\delta(\log n)^{1/(|V(H)|-1)}$," i.e. the CFS $t=3$ proof is a special case of exactly this scheme with $H=K_3^{(3)}$ (so $|V(H)|=3$, giving the observed exponent $1/2$). This is a genuine, named-in-the-wild attack route, not something we invented. No AI-system attempt (GPT/Aristotle/DeepMind) on #161 specifically was found in any searched source.

Attack surface

- Mode: literature-resolution (for $t=3$, already done — the correct move is to formally register #161 as resolved-for-$t=3$) + derivation+formalization (for the genuinely open $t\geq4$ / continuity-for-all-$t$ statement). - Concrete first experiment: (1) Write up the $t=3$ resolution cleanly (Erdős–Spencer lower bound $\Omega_\alpha(\sqrt{\log n})$ + CFS upper bound $O_\alpha(\sqrt{\log n})$ $\Rightarrow$ single jump at $\alpha=0$) as a standalone derivation, citing arXiv:0901.3912 and the Erdős–Spencer bound, and submit it as a comment/partial-solution on erdosproblems.com/161 — this is a zero-computation, high-confidence literature contribution the site does not currently register as "partial." (2) For $t=4$: attempt to instantiate Zach Hunter's "hypergraph Nikiforov" scheme with $H=K_4^{(4)}$ (or the relevant complete 4-uniform hypergraph used in the CFS $t=3$ proof) via the dependent-random-choice / counting-to-blow-up machinery of Fox–Sudakov (arXiv:0909.3271) and Nikiforov's original 2008 graph-counting blow-up theorem, to see whether the $(\log n)^{1/(t-1)}=(\log n)^{1/3}$ exponent (matching the Erdős–Spencer lower bound shape) is reachable, or whether the $k>3$ obstruction proved in arXiv:1104.5544 (no Erdős–Hajnal analogue for $k>3$) also blocks this route. - Oracle: for the $t=3$ literature-resolution sub-claim, mechanically checkable by reading the two cited theorem statements and confirming the asymptotic orders match ($\Theta(\sqrt{\log n})$ both directions) — already done above. For any candidate $t\geq4$ proof, the oracle is a standard extremal-combinatorics proof check (no finite search possible, per the site's own falsifiability note); no computational oracle exists for the general-$t$ case. - Feasibility: the $t=3$ case is not open — this is the single highest-value, cheapest action: register it as resolved on erdosproblems.com, citing arXiv:0901.3912. The $t\geq4$ case is famous-and-hard: it sits exactly at a boundary (arXiv:1104.5544 shows the natural Erdős–Hajnal-style generalization structurally fails for $k>3$), so a full resolution likely requires new ideas beyond the CFS machinery, not a routine extension. Realistic near-term contribution: formalize/replicate the "hypergraph Nikiforov" reduction sketch from the forum comment as a precise conjecture statement (it does not appear to exist as a citable paper — WebSearch found no arXiv paper titled or describing this exact hypergraph-blow-up-from-counting generalization) and check whether it is already implicit in any $k$-uniform Turán/blow-up paper (e.g. Fox–Luo "Extremal and Ramsey results on graph blowups" arXiv:1912.08328, though that is graph- not hypergraph-uniform).

Related

- Erdős #562 — Erdős–Hajnal–Rado hypergraph Ramsey growth rate: SOLVED at the ≥4-colour endpoint via the stepping-up lemma (2-colour case still open) — Erdős–Hajnal–Rado hypergraph Ramsey growth-rate conjecture ($F^{(t)}(n,0)\asymp\log_{t-1}n$); the $\alpha=0$ endpoint of #161's jump question. - Erdős #563 — the graph (t=2) discrepancy-Ramsey function F(n,α) has order Θ_α(log n) — the $t=2$ (graph) discrepancy-Ramsey analogue; $F(n,\alpha)\asymp_\alpha\log n$ known (probabilistic method), exact constant $c_\alpha$ open; structurally the $t=2$ sibling of the same $F^{(t)}$ family. - Hypergraph discrepancy and the Erdős–Spencer/Erdős–Hajnal function F^(t)(n,α) — the Erdős–Spencer notion underlying $F^{(t)}(n,\alpha)$, and the $(\log n)^{1/(t-1)}$ lower bound. - Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts — the Fox–Sudakov technique (arXiv:0909.3271) underlying the CFS proofs of the $t=3$ upper bound and the broader hypergraph-Ramsey program (arXiv:0808.3760, arXiv:1104.5544). - Nikiforov's counting-to-blowup theorem — a graph with a constant fraction of the possible copies of H contains a genuine blow-up H[t] with t = Θ(log n), and the open 'hypergraph Nikiforov' generalization — the 2008 graph-counting-to-logarithmic-blowup theorem whose hypothesized hypergraph generalization ("hypergraph Nikiforov," per Zach Hunter's forum comment) is the proposed route to resolving #161 for general $t$. - Erdős–Hajnal conjecture: forbidding one induced subgraph forces polynomial-size cliques/independent sets — the induced-subgraph Ramsey conjecture whose hypergraph analogue arXiv:1104.5544 proves fails for $k>3$-uniform hypergraphs, marking a structural boundary relevant to why $t\geq4$ of #161 is hard. - Jumps and non-jumps of hypergraph Turán densities (Erdős's jumping constant conjecture, disproved by Frankl–Rödl) — a *different*, already-resolved (Frankl–Rödl disproved it; see arXiv:1004.3733) Erdős "jump" problem about Turán densities, terminologically adjacent but not the same object as #161's $F^{(t)}(n,\alpha)$ jump — kept here explicitly to prevent future conflation.

PRIOR-ART SCAN (2026-07-03)

Verdict: ACTIVELY-WORKED (split verdict, confirms prior page content, no new resolution found) — $t=3$ remains RESOLVED-IN-LITERATURE (CFS11, unchanged since our 2026-07-02 pass); $t\geq4$ remains HARD-OPEN, with one live, unexecuted attack route on record (Zach Hunter's Oct-2025 "hypergraph Nikiforov" forum comment) and no successful AI or human attempt found anywhere. Nothing in this scan changes the page's prior claims or confidence.

erdosproblems.com/161 + forum, re-fetched verbatim (curl, browser UA)

byte-identical in substance to the 2026-07-02 fetch. Still "OPEN … cannot be resolved with a finite computation," still 3 forum comments (Neel Somani's "largest→smallest $m$" typo report, Thomas Bloom's fix confirmation, Zach Hunter's 18-Oct-2025 "hypergraph Nikiforov" conjecture comment), still "Additional thanks to: Zach Hunter and Neel Somani." Page last-edited timestamp unchanged (16 Jan 2026). No new remarks, no new comments, no claimed partial/complete solution.

GitHub prior-art scan (the #64 lesson — checked ALL branches/data files)

- teorth/erdosproblems wiki pages "AI contributions to Erdős problems" and "Notable cases of AI contributions to Erdős problems" (fetched directly) — no mention of #161 anywhere, in any of the tables (1a–1d, 2a–2d) covering problems #11–#1217. #161 is not a recorded AI success, partial, or notable-failure case on this wiki. ("Wiki is no longer updated. Latest data as of Jun 30, 2026.") - neelsomani/gpt-erdos (2 branches: main, grok_answers) — scanned both branches' data/ trees, not just the default branch: - data/unsolved.jsonl (both branches, identical blob): entry {"number": "161", ...} contains the pre-fix problem statement (still says "largest $m$" — the typo Neel Somani reported), i.e. this is a stale scrape from before the site's 16-Jan-2026 correction. No solution content, just the cached problem text. - data/gpt54_pro_verdicts.jsonl (grok_answers branch only): {"number": "161", "status": "failed", "reason": "RuntimeError: Responses API request failed: The read operation timed out", "run_started_at": "2026-04-18T06:15:14Z"} — GPT-5.4 Pro's automated run on #161 crashed with a timeout, no verdict was ever produced. - data/solutions/161/candidate_solution.md and data/solutions/161/grok_output.md (present on both branches, same blob) — two LLM-generated attempts (candidate model + Grok) that both misread the problem as a fixed-finite-$n$ combinatorics puzzle (computing $F$ for literal small $n=3,4,5,6$ and concluding "at most one jump" / "can have multiple jumps" from finite case analysis) rather than engaging the actual asymptotic-growth-rate question the site states is "open, cannot be resolved with a finite computation." Neither file cites CFS11, addresses $t\geq4$, or produces anything checkable against the real problem. These are dead-end/off-target attempts, not progress — confirmed by directly reading both files in full. - No other GitHub repository found referencing F^{(t)}(n,\alpha), "hypergraph discrepancy jump," or Erdős #161 by number.

arXiv / Semantic Scholar sweep for 2023–2026 work (citations of CFS11 = arXiv:0901.3912, plus direct search): - Semantic Scholar citation list for arXiv:0901.3912 pulled in full (~mid-2020s citing papers) — nothing found that extends the CFS $t=3$ upper bound to $t\geq4$ or otherwise resolves the general-$t$ case. - Pudlák–Rödl, "Colorings of $k$-sets with low discrepancy on small sets," arXiv:2402.05286 (v1 Feb 2024, v3 Dec 2025, still arXiv-only, math.CO) — closest adjacent recent result found. Defines $R_k(m;\delta)$, a discrepancy-Ramsey number generalizing $R_k(m)$, and proves a tower-type lower bound $R_k(k+n; 2^{-\epsilon n}) \geq \mathrm{tw}_{\lfloor k/n\rfloor}(2)$ for $k\to\infty$ with $m=k+n$ close to $k$ (near-diagonal regime, $k$-uniformity itself growing). This is a different asymptotic regime from #161: Erdős's problem fixes $t$ and lets $n\to\infty$ with $\alpha\in[0,1/2)$ fixed; Pudlák–Rödl let the uniformity $k\to\infty$ with $m$ pinned near $k$. Read directly (abstract + submission history); does not cite or address #161, does not close the $t\geq4$ gap. - Girão–Hunter–Wigderson, "Blowups of triangle-free graphs" (arXiv:2408.12913) and Fox–Wigderson–Zhou, "Finding blowups one vertex at a time" (arXiv:2605.23301, submitted May 2026) — both improve the classical (graph, not hypergraph) Nikiforov blow-up theorem's constant, which is exactly the underlying machinery Zach Hunter's forum comment proposes generalizing to hypergraphs. Read both abstracts directly: neither paper is about hypergraphs, neither mentions #161 or a hypergraph generalization. They are evidence the *graph*-level Nikiforov theorem is an active research target in 2026, but nobody has yet lifted this activity to the hypergraph statement Hunter's comment needs. - No arXiv paper titled or describing "hypergraph Nikiforov" was found — Hunter's proposed conjecture (18 Oct 2025) still does not exist as a citable paper, confirming the page's existing note.

Conclusion

the page's existing split (partially-resolved, $t=3$ resolved / $t\geq4$ open) is correct and current as of 2026-07-03. No prior-art gap was found that we previously missed; no new claim needs walking back (unlike #64). The one concrete, unclaimed opportunity remains exactly what the page already identifies: (1) formally registering the $t=3$ resolution as a comment on erdosproblems.com/161 (zero-computation, citing arXiv:0901.3912 — cheap and currently un-registered by the site itself), and (2) attempting to instantiate Zach Hunter's "hypergraph Nikiforov" conjecture for $t=4$, for which the graph-level machinery (arXiv:2408.12913, arXiv:2605.23301) is being actively improved in 2026 but has not yet been lifted to hypergraphs by anyone.

Sources read directly in this pass: erdosproblems.com/161 (curl re-fetch), erdosproblems.com/forum/discuss/161 (curl re-fetch), github.com/teorth/erdosproblems/wiki/AI-contributions-to-Erdős-problems, github.com/teorth/erdosproblems/wiki/Notable-cases-of-AI-contributions-to-Erdős-problems, github.com/teorth/erdosproblems/wiki/Disclaimers-and-caveats, github.com/neelsomani/gpt-erdos (branches main + grok_answers: data/unsolved.jsonl, data/gpt54_pro_verdicts.jsonl, data/solutions/161/candidate_solution.md, data/solutions/161/grok_output.md), arxiv.org/abs/2402.05286 (Pudlák–Rödl), arxiv.org/abs/2408.12913 (Girão–Hunter–Wigderson), arxiv.org/abs/2605.23301 (Fox–Wigderson–Zhou), Semantic Scholar citation graph for arXiv:0901.3912.