Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 75

claims/: The 1 claim page of Problem 75, one per claimant's result; the problem's standing derives from them.

Statement. Is there a graph of chromatic number $\aleph_1$ with $\aleph_1$ vertices such that for all $\epsilon>0$ if $n$ is sufficiently large and $H$ is a subgraph on $n$ vertices then $H$ contains an independent set of size $>n^{1-\epsilon}$ ?

What about an independent set of size $\gg n$ ?

Status. Open, the site's label. The first question has a pending partial claim, the Specker graph answers the n^(1-epsilon) question.

Source. erdosproblems.com/75, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #75, https://www.erdosproblems.com/75.

References.

[EHS82] Erdős, P. and Hajnal, A. and Szemerédi, E., On almost bipartite large chromatic graphs. Theory and practice of combinatorics (1982), 117-123.
[Er95] Erdős, Paul, Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas (1995), 165-186.
[Er95d] Erdős, Paul, On some problems in combinatorial set theory. Publ. Inst. Math. (Beograd) (N.S.) 57(71) (1995), 61-65.

Formalization. Statement in formal-conjectures.

Current assessment

The site's formulation (page last edited 29 January 2026) asks for a graph of chromatic number $\aleph_1$ on $\aleph_1$ vertices whose subgraphs on $n$ vertices, for $n$ large, contain independent sets of size above $n^{1-\epsilon}$ for every $\epsilon>0$ , and then asks the same with $\gg n$ in place of $n^{1-\epsilon}$ . The site attributes the question to Erdős, Hajnal and Szemerédi [EHS82] and records that Erdős's 1995 wording in [Er95] omitted the $\aleph_1$ -vertex condition by oversight, since [EHS82] already gives such a construction; the paper Semi-Autonomous Mathematics Discovery with Gemini: A Case Study on the Erdős Problems (arXiv:2601.22401, Appendix A) reports that its agent Aletheia solved the problem as the site then stated it, before experts found that wording not to be the intended one.

Claims. One claim page, pending. The first question has a positive answer in a note by Przemek Chojecki, obtained with GPT-5.4 Pro and posted in the site's discussion thread on 12 April 2026 (claim page): the Specker graph $G_1(\omega_1,3)$ has chromatic number and size $\aleph_1$ , and its finite subgraphs on $n$ vertices have independent sets of size at least $n/(C\log_2 n)$ , by the chromatic-number bound for finite type-graphs of Avart, Kay, Reiher and Rödl (2017). A commenter's check with GPT-5.4 Thinking found one minor issue and noted the stronger bound $\gg n/\log n$ ; the curator replied that the construction was already studied in [EHS82] and that the lower bound was perhaps known but unpublished. The note is unrefereed and the site labels the problem OPEN, so the claim is partial and pending, and the problem's standing is open. The second question, an independent set of size $\gg n$ , has no claim: [EHS82, Theorem 2] bounds the least independence number over $m$ -vertex subsets of the countable Specker graph by $O(m\log\log m/\log m)$ , so no Specker graph answers it. The site's proof-claims tab lists no claim.

Search scope, 2026-10-07: the site's page and remarks, its discussion thread (three comments of 12 April 2026) and proof-claims tab, the note itself, the formal-conjectures statement file (erdos_75, tagged research open, with no formal proof) and the Gemini case-study paper. Erdős's prize offer in [Er95d] for a complete solution to all problems of this type, with Problem 74 as an example, is recorded by the site; the vertex-deletion relative is Problem 750. The library's card for the original source is erdos_1982_almost_bipartite_large_chromatic_graphs; its proofs are not compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (18)

The Specker graph answers the n^(1-epsilon) question problems/graph_coloring/E0075/claims Problem 750 Erdős and Hajnal's graphs with independence density near one half Graph Coloring distance_problems/feng_2026_semi_autonomous_mathematics_discovery_gemini_case Theorem 14: under CH, an aleph_1-chromatic shift graph whose n-vertex subgraphs have independent sets of size n/4 Graph Coloring A note on the n^{1-epsilon} version of an Erdos problem Lemma 1 (p. 1): the finite Specker graph G_1(r,3) is the type-graph G(r,112122)Theorem 1 (p. 1): the Specker graph G_1(omega_1,3) has size and chromatic number aleph_1 and every finite n-vertex subgraph has independence number at least n/(C log_2 n)graph_coloring/erdos_1967_kromatikus_grafokrol_chromatic_graphs Partial result (p. 3): for every m, an m-chromatic graph on 2^m vertices with property T_c for every c < 1/4 graph_coloring/erdos_1982_almost_bipartite_large_chromatic_graphs Problem 2: an aleph_1-chromatic graph on aleph_1 vertices whose n-vertex subgraphs have independent sets of size cn Theorem 2: the Specker graph G_1(omega,3) has m-vertex subgraphs with independence number O(m log log m / log m)graph_coloring/erdos_1995_problems_combinatorial_set_theory Section 3 (pp. 62–63): the Erdős–Hajnal–Szemerédi problems on almost bipartite graphs of large chromatic number

Graph