Skip to content

Erdős Problems

1,217 source-owned questions · 604 with a formal statement · searchable by statement, number, topic and source status.

Add a contributionCollection details
Full distribution

Collection coverage

Source status, exact formal material, and reviewed Results are separate signals.

  • Open per source608
  • Resolved per source556
  • Other source status53
Exact formal statement available604 / 1,217
With Repository-reviewed evidence2 / 1,217
More filters

Coverage is source-observation coverage, not Problem completeness. Inspect coverage

Problems

61 Problems

2/2

SelectNumberQuestionOpen
#921No statement retained — open to read what the source holdsSource says provedNo formal declaration
#922No statement retained — open to read what the source holdsSource says provedNo formal declaration
#923Is it true that, for every kk, there is some f(k)f(k) such that if GG has chromatic number ≥f(k)\geq f(k) then GG contains a triangle-free subgraph with chromatic number ≥k\geq k?Source says proved (Lean)Formalized
#944Let k≥4k \ge 4 and r≥1r\ge 1. Must there exist a graph GG with chromatic number kk such that every vertex is critical, yet every critical set of edges has size >r>r?Source says openFormalized
#1032No statement retained — open to read what the source holdsSource says openNo formal declaration
#1068Does every graph with chromatic number ℵ1\aleph_1 contain a countable subgraph which is infinitely connected?Source says openFormalized
#1091No statement retained — open to read what the source holdsSource says solvedNo formal declaration
#1092Is it true that f2(n)≫nf_2(n) \gg n? Disproved by Rödl, who showed fr(n)=o(n)f_r(n) = o(n) for all fixed r≥2r \geq 2. A conjecture of Erdős, Hajnal, and Szemerédi.Source says disprovedFormalized
#1104Lower bound (Hefty–Horn–King–Pfender 2025). There exists a constant c1∈(0,1]c_1 \in (0,1] such that, for sufficiently large nn, c1nlog⁡n≤f(n), c_1 \sqrt{\frac{n}{\log n}} \le f(n), where f(n)f(n) denotes the maximum chromatic number of a triangle-free graph on nn vertices, formalized as triangleFreeMaxChromatic n.Source says openFormalized
#1156No statement retained — open to read what the source holdsSource says openNo formal declaration
#1175Let κ\kappa be an uncountable cardinal. Must there exist a cardinal λ\lambda such that every graph with chromatic number λ\lambda contains a triangle-free subgraph with chromatic number κ\kappa?Source says openFormalized
#1176Let GG be a graph with chromatic number ℵ1\aleph_1. Is it true that there is a colouring of the edges with ℵ1\aleph_1 many colours such that, in any countable colouring of the vertices, there exists a vertex colour containing all edge colours?Source says not disprovableFormalized
#1177No statement retained — open to read what the source holdsSource says openNo formal declaration