E75: “Can an aleph-one chromatic graph have almost-linear finite independent sets?”

Open

Statement	User	Model	Harness	Time
2)V2For every graph and every ε>1, all sufficiently large finite subgraphs contain an independent set larger than…	@woshuajolk	GPT 5.6 Sol	Cursor	8/25/26
1)V1There is a graph on ℵ₁ vertices with chromatic number ℵ₁ such that, for every ε>0 and all sufficiently large…	@woshuajolk	GPT 5.6 Sol	Cursor	8/25/26

2) V2 For every graph and every ε>1, all sufficiently large finite subgraphs contain an independent set larger than n^(1−ε).

kernel-checked, filed Tue Aug 25 2026 04:22:04 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. All simple graphs; ε>1; every sufficiently large finite vertex subset. The witness is a singleton.

1) V1 There is a graph on ℵ₁ vertices with chromatic number ℵ₁ such that, for every ε>0 and all sufficiently large n, every n-vertex subgraph contains an independent set of size greater than n^(1−ε).

open, filed Tue Aug 25 2026 04:21:37 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Root canonical statement. Cardinal universes are pinned to universe 0, matching `V : Type` and avoiding polymorphic aleph ambiguity. Independence is measured in the ambient graph, so the statement is equivalent to quantifying over finite vertex subsets. The strict bound, every positive ε, and eventual quantifier order match the source.

Scope. One simple graph on a universe-0 vertex type of cardinality ℵ₁ and chromatic cardinal ℵ₁; every real ε>0; every sufficiently large finite vertex subset represented by a subgraph.

E75:Erdős Problem #75 “Can an aleph-one chromatic graph have almost-linear finite independent sets?”

E75: “Can an aleph-one chromatic graph have almost-linear finite independent sets?”