Skip to content

Erdős Problem #162

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

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 graph \(K_n\) red and blue. Erdős #162 asks for a sharp logarithmic constant in a balanced large-subsets threshold: the smallest \(k\) for which there exists a colouring such that every induced subgraph on at least \(k\) vertices has more than \(\alpha\) of its edges in each colour.

For a fixed \(0\le\alpha<1/2\), the intended research question is whether this threshold satisfies

\[ F(n,\alpha)\sim c_\alpha\log n \]

for some positive constant \(c_\alpha\). This is a sharpening of known \(\Theta_\alpha(\log n)\) estimates, not an instruction to maximize \(k\).

A small example

The current maintained page prints “largest \(k\)”. Read literally, the statement is undefined: every \(k>n\) is admissible because there are no induced subgraphs on at least \(k\) vertices. Even if one artificially restricts \(k\le n\), any sufficiently balanced colouring makes \(k=n\) admissible when \(\alpha<1/2\), so the largest threshold is \(n\), not logarithmic.

The printed range also includes \(\alpha=1/2\) with strictly more than half of all edges required of each colour. That is impossible for a nonempty edge set, because the red and blue proportions sum to one. These are independent quantifier and endpoint defects.

What is known

OPEN as an intended corrected asymptotic problem; ill-posed literally. The maintained Erdős #162 discussion contains an explicit April 2026 observation identifying the “largest” versus “smallest” error and the forbidden endpoint. Earlier comments in December 2025 clarified that the colouring quantifier should be existential and \(H\) should be induced.

The site attributes upper and lower bounds of the form \(c_1(\alpha)\log n<F(n,\alpha)<c_2(\alpha)\log n\) to the probabilistic method. These can only be statements about the corrected minimum threshold at \(0<\alpha<1/2\), not the literal maximum.

A closely related 2011 hypergraph discrepancy theorem of Conlon, Fox and Sudakov applies to three-uniform hypergraphs, with different exponents. It does not determine the sharp two-colour graph constant \(c_\alpha\) asked for here. At \(\alpha=0\) with strict “more than,” the condition becomes nonmonochromaticity and also needs separate treatment.

GCL's current state

The pinned source task #1431 records #162 as OPEN, but current source semantics require STATUS_CONFLICT / statement-capture before formal research. The displayed mathematical problem cannot be used verbatim as a well-defined extremal function. No conjecture or theorem has been silently rewritten in the protected register.

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 successor implements both literal and proposed corrected thresholds for \(n\le6\) and rational \(\alpha=1/4,1/3,1/2\). Verify by exhaustive colourings that all \(k>n\) are vacuously admissible, the largest admissible \(k\le n\) equals \(n\) whenever a balanced full-graph colouring exists, and the minimum threshold behaves differently. Acceptance: a formally separate corrected definition, a counterexample to the original wording, and primary-source inspection of Erdős [Er90b, p.21]; stop before any asymptotic proof attempt.

Sources and claim boundaries

The literal statement is defective; the intended corrected sharp constant remains unproved. No protected-source substitution or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1431 — 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