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
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
- Erdős #162, live displayed definition.
- Source discussion, April 2026, explicit defects and preceding wording corrections.
- Original GCL issue #1431.
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.