Skip to content

Erdős Problem #161

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: combinatorics, ramsey theory, discrepancy, hypergraphs.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Colour the edges of the complete \(t\) uniform hypergraph on \(n\) vertices red or blue. A vertex subset \(X\) is balanced at tolerance \(\alpha\) when at least an \(\alpha\) proportion of its \(\binom{|X|}{t}\) edges have each colour. Define \(F^{(t)}(n,\alpha)\) as the least threshold \(m\) for which some colouring makes every \(X\) with \(|X|\ge m\) balanced.

Erdős asked whether, for fixed \(t\), changing \(\alpha\) between zero and one half causes one abrupt change in the growth of this threshold or several. The distinction is asymptotic in \(n\), not mere continuity of a finite-valued step function. The original threshold and endpoint conventions require review, as explained below.

A small example

For \(t=2\), the hyperedges are ordinary graph edges. With \(n=4\), a colouring whose six edges are split three red and three blue may be balanced on the full vertex set at \(\alpha=1/3\); this does not guarantee the condition on any three-vertex subset. Every eligible subset must be tested.

At exactly \(\alpha=0\), however, the literal condition “at least zero edges of each colour” holds for every subset under every colouring, so the literal minimum threshold is one. It cannot be a Ramsey threshold. The catalogue's comparison with the ordinary Ramsey function therefore needs an explicit nonmonochromatic or positive-colour-count convention at zero.

What is known

The broad parameter-jump question remains OPEN. Conlon, Fox and Sudakov, Large almost monochromatic subsets in hypergraphs, Israel Journal of Mathematics 181 (2011), 423–432, prove a sharp square-root-logarithm scale for the three-uniform, fixed-positive-tolerance discrepancy problem. The maintained Erdős #161, edited January 2026, records \(F^{(3)}(n,\alpha)\ll_\alpha\sqrt{\log n}\) for fixed positive \(\alpha\), with matching order in the relevant regime; it says the jump pattern at positive \(\alpha\) is settled for triples, while the larger-uniformity problem remains.

Source-fidelity qualification: Conlon–Fox–Sudakov's paper concerns guaranteed almost-monochromatic subsets in every colouring, whereas the displayed problem is phrased as existence of a colouring making all large subsets balanced. These are complementary Ramsey/discrepancy perspectives; their exact quantifier relation must be proved rather than assumed. The literal zero-tolerance issue makes a direct theorem-to-statement transfer especially unsafe.

GCL's current state

The pinned catalogue lists #161 OPEN, with source issue #1430. The historical prize description does not authorize any award claim. The primary abstract and current catalogue were inspected. The zero-tolerance normalization remains a statement-capture risk, and no protected formal proof or campaign status was changed.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task is to enumerate two-colourings for \(n\le5\) and \(t=2,3\), compute the least threshold satisfying the literal definition for \(\alpha=0,1/4,1/3\), and formalize the complementarity between a balanced-all-large-subsets colouring and unavoidable nearly monochromatic subsets. Acceptance: report the trivial literal value at \(\alpha=0\), identify all empty-edge cases, preserve strict versus non-strict inequalities, and stop without claiming any resolution of the higher-uniformity asymptotic jump problem.

Sources and claim boundaries

No proof of the full conjecture, reconciled zero-parameter definition, or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1430 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction