Skip to content

Erdős Problem #1176

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: not disprovable (not automatically the live result).
Subject areas: set theory, ramsey theory.

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.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Erdős Problem #1176 asks the following. The maintained status is NOT DISPROVABLE.

Let \(G\) have vertex chromatic number \(\aleph_1\). Can one assign \(\aleph_1\) colors to its edges so that, under every subsequent countable vertex coloring, some vertex-color class contains edges in every edge color? The two colorings have different domains and palettes. The statement requires the distinguished class to see every edge color, not merely one color or every vertex color class to work.

A small example

On the one-edge graph \(K_2\), proper two-coloring of the vertices gives two independent singleton classes. Neither contains any edge, so neither contains the edge's assigned color. This checks a simple finite chromatic-two obstruction but says nothing about a graph of chromatic number \(\aleph_1\).

What is known

https://www.erdosproblems.com/1176 reports NOT DISPROVABLE, citing Vardi [Va99,7.93] and a relative-consistency theorem of Hajnal and Komjáth. This is model-relative evidence, not an unconditional ZFC theorem. The formalization badge is not a mathematical kernel proof. The original forcing hypotheses and surjectivity of edge coloring need primary-source review.

GCL's current state

Authenticated original-issue RESULT/1 research return. GCL independently replayed only the exact bounded fixture in ci/erdos_compendium_007_phase21_checks.py. The general theorem statements above are attributed to their external sources rather than independently certified. This is a locally authored and unaccepted draft.

What remains

Read Vardi §7.93 and the original Hajnal–Komjáth theorem to establish exact forcing assumptions, edge-color surjectivity and vertex-class quantifiers. Keep relative consistency distinct from ZFC provability.

Protected V2 admission requires source fidelity, manuscript QA and any mandatory independent critic reviews; none is inferred from this finite example.

Sources and claim boundaries

https://www.erdosproblems.com/1176 ; [Va99,7.93], Hajnal–Komjáth.

Finite evidence receipt: governance/erdos_compendium/batches/EC-BULK-007_FINITE_CHECKS_PHASE21.json. Original GitHub source issue identities unchanged; source-fidelity adjudication, public deployment and V2 editorial acceptance PENDING.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2447 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned 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