Erdős Problem #75
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, chromatic number.
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
Can a graph on \(\aleph_1\) vertices require \(\aleph_1\) different colors while all of its small finite pieces contain remarkably large independent sets? Erdős #75 asks for a graph with chromatic number \(\aleph_1\) such that, for every \(\epsilon>0\), all sufficiently large finite \(n\)‑vertex subgraphs have independent sets of size greater than \(n^{1-\epsilon}\).
A stronger variant asks whether each finite \(n\)‑vertex subgraph can contain an independent set of size at least \(c n\) for some fixed positive \(c\). Both the size and chromatic-number requirements on the ambient graph matter. A countably chromatic example does not answer the question.
A small example
An independent set consists of pairwise nonadjacent vertices. The five-cycle \(C_5\) has independence number two; each vertex excludes its two neighbors from a maximum independent set. A single five-cycle cannot settle an asymptotic statement that quantifies over all sufficiently large finite subgraphs of one uncountable graph.
There is a useful link with bipartite subgraphs. If an induced \(n\)‑vertex subgraph contains a bipartite induced subgraph on \(b\) vertices, one side of its bipartition is independent and has at least \(b/2\) vertices. A bound on almost-bipartite finite pieces can therefore imply a bound on independence numbers. The reverse implication need not hold.
What is known
The source problem is marked OPEN. In their original 1982 paper, Erdős, Hajnal and Szemerédi proved that for every fixed \(\epsilon>0\) and every cardinal \(\kappa\) there exists a graph of chromatic number greater than \(\kappa\) whose every finite \(n\)‑vertex subset contains an induced bipartite graph on at least \((1-\epsilon)n\) vertices (Theorem 1, printed page 120). This gives an independent set of size at least \((1-\epsilon)n/2\). Crucially, it does not give a single graph with exactly \(\aleph_1\) vertices and chromatic number \(\aleph_1\) with the required varying exponent condition, and it cannot simply be restricted to an arbitrary \(\aleph_1\)‑vertex subgraph without justifying the chromatic number.
On the same printed page, their Problem 2 explicitly asks whether a graph on \(\omega_1\) vertices with chromatic number \(\omega_1\) can have independence number at least \(cn\) in every finite induced \(n\)‑vertex subgraph. Their Theorem 2 studies a natural Specker graph that does not satisfy this stronger condition. These are historically precise distinctions between near-bipartiteness, independence number, and uncountable chromatic number.
GCL's current state
The seven-page 1982 primary paper has been inspected through the Rényi archive, including the formulation and Theorem 1 on printed page 120. The local source assignment is ERDOS-CATALOGUE-0075-S01. This is an unaccepted editorial draft with an authenticated source return, not a claimed resolution.
What remains
A bounded successor is to formalize the implication that a bipartite induced subgraph on at least \((1-\delta)n\) vertices gives an independent set of size at least \((1-\delta)n/2\), then audit whether any known \(\omega_1\)‑chromatic construction attains such a bound uniformly on all finite subsets. A witness must preserve the same ambient graph and quantify over every eligible \(n\) and every \(n\)‑vertex subgraph. Exhibiting examples for each \(n\) separately is insufficient.
Sources and claim boundaries
- Erdős, Hajnal and Szemerédi, On almost bipartite large chromatic graphs, Annals of Discrete Mathematics 12 (1982), 117–123, especially printed page 120, Theorems 1–2 and Problem 2 (original primary paper directly inspected).
- Erdős problem #75, pinned revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
- GCL original source issue #1344.
No proof of the open problem, uncountable example, independent mathematical certification, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1344 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- 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.