Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
**Erdős Problem 70**: Let \(\mathfrak{c}\) be the order type of the real numbers, let \(\beta\) be a countable ordinal, and let \(2 \le n < \omega\). Is it true that \(\mathfrak{c} \to (\beta, n)^3_2\)? Note: The cases \(n \le 3\) are…
For every \(x \in \mathbb{R}\) let \(A_x \subset \mathbb{R}\) be a bounded set with outer measure \(< 1\). Must there exist an infinite independent set, that is, some infinite \(X \subseteq \mathbb{R}\) such that \(x \notin A_y\) for all…
Let \(α\) be the infinite ordinal \(\omega^{\omega}\). It was proved by Chang [Ch72] that any red/blue colouring of the edges of \(K_α\) there is either a red \(K_α\) or a blue \(K_3\).
Let \(α\) be the infinite ordinal \(\omega^{\omega^2}\). Is it true that any red/blue colouring of the edges of \(K_α\) there is either a red \(K_α\) or a blue \(K_3\)? This is true and was proved independently by Schipperus [Sc10] and…
Determine which countable ordinals \(β\) have the property that, if \(α = \omega^β\), then in any red/blue colouring of the edges of \(K_α\) there is either a red \(K_α\) or a blue \(K_3\).
**Erdős Problem 593 (\\(500)**: Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number \)> \aleph_0…
**Erdős Problem 594** (Erdős–Hajnal [ErHa66], [Er69b]): Does every graph \(G\) with chromatic number \(\geq \aleph_1\) contain all sufficiently large odd cycles? The answer is **Yes**, proved by Erdős, Hajnal, and Shelah [EHS74]. A graph…
**Erdős Problem 595 (\\(250)**: Is there an infinite graph \)G\( which contains no \)K_4$ and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal [Er87].
**Erdős Problem 596** (Erdős–Hajnal, [Er87]). For which graph pairs \((G_1, G_2)\) is it true that (1) for every \(n \geq 1\) there is a graph \(H\) without a \(G_1\) such that any \(n\)-colouring of \(H\)'s edges contains a monochromatic…
**Erdős Problem 598:** Let \(m\) be an infinite cardinal and \(\kappa\) be the successor cardinal of \(2^{\aleph_0}\). Can one colour the countable subsets of \(m\) using \(\kappa\) many colours so that every \(X \subseteq m\) with…
Erdős-Menger conjecture
**Erdős Problem 599** (the Erdős–Menger conjecture). Let \(G\) be a (possibly infinite) graph and let \(A, B\) be disjoint independent sets of vertices. Must there exist a family \(P\) of pairwise vertex-disjoint paths from \(A\) to \(B\),…
Property B
Does every almost-disjoint family of countably infinite sets whose pairwise intersections all have size ≠ 1 have Property B? Formally: let α be any type, let (A_i)_{i ∈ I} be a family of countably infinite subsets of α such that for all i…
Let \((A_i)\) be a family of countably infinite sets such that \(\lvert A_i\cap A_j\rvert \neq 2\) for all \(i\neq j\). Find the smallest cardinal \(C\) such that \(\cup A_i\) can always be coloured with at most \(C\) colours so that no…
Let \(X\) be a set of cardinality \(\aleph_\omega\) and \(f\) be a function from the finite subsets of \(X\) to \(X\) such that \(f(A)\not\in A\) for all \(A\). Must there exist an infinite \(Y\subseteq X\) that is independent - that is,…
Does every graph with chromatic number \(\aleph_1\) contain an infinitely connected subgraph with chromatic number \(\aleph_1\)? Komjáth [Ko13] proved that it is consistent that the answer is no. This was improved by Soukup [So15], who…
Does every graph with chromatic number \(\aleph_1\) contain a countable subgraph which is infinitely connected?
Let \(\mathfrak{m}\) be an infinite cardinal with \(\aleph_0 < \mathfrak{m} < \mathfrak{c} = 2^{\aleph_0}\). Let \(\{f_\alpha\}\) be a family of entire functions such that, for every \(z_0 \in \mathbb{C}\), there are at most…
**Prikry–Mills counterexample** (key lemma): There exists a 2-colouring \(f\) of a set of cardinality \(\aleph_1\) cubed such that no countable box \(A_1 \times B_1 \times C_1\) is monochromatic. This is the unpublished result of Prikry…
**Erdős Problem 1167.** Let \(r \geq 2\) be finite, \(\gamma \geq 2\), and \(\lambda\) be an infinite cardinal. Let \(\kappa_\alpha > r\) be cardinals for all \(\alpha < \gamma\). Is it true that \[2^\lambda \to (\kappa_\alpha + 1)_{\alpha…
Let \(\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\)? Shelah proved that a negative…
Let \(G\) be a graph with chromatic number \(\aleph_1\). Is it true that there is a colouring of the edges with \(\aleph_1\) many colours such that, in any countable colouring of the vertices, there exists a vertex colour containing all…
Let \(G\) be a finite \(3\)-uniform hypergraph, and let \(F_G(\kappa)\) denote the collection of \(3\)-uniform hypergraphs with chromatic number \(\kappa\) not containing \(G\). If \(F_G(\aleph_1)\) is not empty then there exists…
Let \((n_k)\) be an increasing sequence of integers such that \(2^{\aleph_{n_k}}\) is strictly increasing, and \(2^{\aleph_{n_0}} > \aleph_\omega\). Is it true that \[\sum_k 2^{\aleph_{n_k}} \to (\aleph_\omega)^2?\] Here…