Erdős Problem #110
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: graph theory, chromatic number, cycles.
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
Graphs can have infinitely many vertices and require uncountably many colours. In particular, chromatic number \(\aleph_1\) means no countable proper vertex colouring exists, but a colouring with the first uncountable cardinality of colours does.
Erdős, Hajnal and Szemerédi asked whether there is one universal function \(F(n)\) such that every graph \(G\) with \(\chi(G)=\aleph_1\) contains, for all sufficiently large finite \(n\), a finite subgraph with chromatic number \(n\) on at most \(F(n)\) vertices. The same \(F\) must work for every such \(G\); allowing the bound to depend on the host graph changes the assertion.
A small example
Every finite \(K_n\) needs \(n\) colours, so a graph containing \(K_n\) offers an \(n\) chromatic subgraph with exactly \(n\) vertices. However, there are high-chromatic graphs with no triangles. The existence of finite chromatic obstructions does not force a uniform upper bound on how many vertices are needed.
The classical de Bruijn–Erdős compactness theorem implies that an infinite-chromatic graph has finite subgraphs of arbitrarily high finite chromatic number. That proves their existence, not a host-independent rate at which they appear.
What is known
DISPROVED in ZFC. Chris Lambie-Hanson's On the growth rate of chromatic numbers of finite subgraphs, Advances in Mathematics 369 (2020), article 107176, shows that finite chromatic obstructions can appear arbitrarily slowly, even inside a graph with uncountable chromatic number.
In the primary theorem's formulation, for an arbitrary growth function \(f:\mathbb N\to\mathbb N\) one constructs an uncountably chromatic graph \(G\) such that every finite subgraph with fewer than \(f(k)\) vertices has chromatic number less than \(k\) (for \(k\ge3\)). This excludes any universal \(F(k)\) by choosing \(f\) to dominate it. The distinction between \(<\) and \(\le\) and integer shifts is harmless to this diagonal argument, but must be handled explicitly when formalizing.
An earlier theorem of Komjáth and Shelah gave the negative answer in a model of set theory; Lambie-Hanson's construction removes the extra-set-theoretic consistency qualification. This is not a statement about all graphs with chromatic number only \(\aleph_0\).
GCL's current state
The pinned catalogue and maintained Erdős #110 classify the problem DISPROVED. The original issue is #1379. The primary 2019 arXiv abstract and 2020 journal publication record were inspected; the forcing and infinite-graph machinery inside the full proof has not been independently reproduced.
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 logical successor is to formalize the contradiction in quantifiers: assume a universal function \(F\), apply Lambie-Hanson's imported theorem with \(f(k)=F(k)+1\), and derive the absence of the asserted small \(k\) chromatic subgraph in the constructed host. Acceptance: make the \(\exists F\,\forall G\,\forall^\text{large}k\) versus \(\forall f\,\exists G\,\forall k\) ordering explicit. Import the deep construction as a stated theorem; do not misrepresent this exercise as a proof of it.
Sources and claim boundaries
- Lambie-Hanson, arXiv:1902.08177, primary author preprint.
- Journal publication, Advances in Mathematics 369 (2020), primary publisher abstract.
- Erdős #110; original issue #1379.
No independent ZFC construction replay, protected Lean proof or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1379 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- 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.