Scientists / Open questions

Paul Erdős

Number theory; combinatorics; graph theory

41 questions

Colouring number versus the complete bipartite graph $[[\omega_2,\omega]]$ on $\omega_{\omega+1}$ vertices under GCH (Erdős–Hajnal 1966, Problem 5.7)
Sums of integers with many divisors at the sharp threshold: pairwise-coprime summands and asymptotic representation counts (Erdős-Montgomery, 1999)
Decreasing the diameter of triangle-free graphs: the open problem of Erdős, Gyárfás and Ruszinkó (1998) on the edge-addition parameter h_d(G)
Independence in $K_4$ -free graphs with no degree repeated more than four times
The order function $F(n)$ : smallest triangle-free graphs with chromatic number $n$ and no degree repeated more than three times (Erdős–Fajtlowicz–Staton)
The minimal order of growth of an additive complement of the primes
Exact extremal theory of nearly equal distances in separated planar point sets (Erdős-Makai-Pach)
The leading constant in the Erdős–Kleitman asymptotic for families of subsets containing no 4-member Boolean algebra
The middle-exponent case of the Erdős–Larson matching partition relation: does $\omega^{\eta+jk} \to (\omega^{\eta+j},\ \omega^k\text{-matching})$ hold for every limit ordinal $\eta$ ?
Forcing densities $\sigma(m,f)$ for induced subgraphs of given sizes: existence of the limit and the remaining $r=3,4$ cases of the $1/r$ conjecture
The local density problem for triangles: exact determination of $\beta(\alpha)$ and the Erdős–Faudree–Rousseau–Schelp conjecture
Burr–Erdős (1981) open problems on the stability of completeness and subcompleteness of integer sequences under perturbation
Surviving instances of the Erdős–Pach–Pollack–Tuza diameter conjecture: sharp bounds for the diameter of connected $K_{k+1}$ -free graphs of given minimum degree for $k \le 6$
Existence and value of the limit of $(\log_2 n_k)/k^2$ for Erdős–Evans prime sets satisfying the divisibility condition (*)
ZFC status of the sharp free-set partition relation $\omega_{2}\cdot\alpha\nrightarrow[\omega_{1}^{\omega}+1,\omega_{2}\cdot\alpha]_{\aleph_{2}}$ without the hypothesis $2^{\aleph_{1}}=\aleph_{2}$ (Erdős–Hajnal–Milner, 1969)
Arrays of dots with distinct slopes or lengths in the square grid: extremal sizes and the existence of n-dot distinct-difference arrays
Erdős's 1954 conjectures on independent sets for set mappings of the real line with nondense, bounded-measure pictures

Back to open problems

Colouring number versus the complete bipartite graph [[ω2,ω]][[\omega_2,\omega]][[ω2​,ω]] on ωω+1\omega_{\omega+1}ωω+1​ vertices under GCH (Erdős–Hajnal 1966, Problem 5.7)

Sums of integers with many divisors at the sharp threshold: pairwise-coprime summands and asymptotic representation counts (Erdős-Montgomery, 1999)

Decreasing the diameter of triangle-free graphs: the open problem of Erdős, Gyárfás and Ruszinkó (1998) on the edge-addition parameter h_d(G)

Independence in K4K_4K4​-free graphs with no degree repeated more than four times

The order function F(n)F(n)F(n): smallest triangle-free graphs with chromatic number nnn and no degree repeated more than three times (Erdős–Fajtlowicz–Staton)

The minimal order of growth of an additive complement of the primes

Exact extremal theory of nearly equal distances in separated planar point sets (Erdős-Makai-Pach)

The leading constant in the Erdős–Kleitman asymptotic for families of subsets containing no 4-member Boolean algebra

The middle-exponent case of the Erdős–Larson matching partition relation: does ωη+jk→(ωη+j, ωk-matching)\omega^{\eta+jk} \to (\omega^{\eta+j},\ \omega^k\text{-matching})ωη+jk→(ωη+j, ωk-matching) hold for every limit ordinal η\etaη?

Forcing densities σ(m,f)\sigma(m,f)σ(m,f) for induced subgraphs of given sizes: existence of the limit and the remaining r=3,4r=3,4r=3,4 cases of the 1/r1/r1/r conjecture

The local density problem for triangles: exact determination of β(α)\beta(\alpha)β(α) and the Erdős–Faudree–Rousseau–Schelp conjecture

Burr–Erdős (1981) open problems on the stability of completeness and subcompleteness of integer sequences under perturbation

Surviving instances of the Erdős–Pach–Pollack–Tuza diameter conjecture: sharp bounds for the diameter of connected Kk+1K_{k+1}Kk+1​-free graphs of given minimum degree for k≤6k \le 6k≤6

Existence and value of the limit of (log⁡2nk)/k2(\log_2 n_k)/k^2(log2​nk​)/k2 for Erdős–Evans prime sets satisfying the divisibility condition (*)

Arrays of dots with distinct slopes or lengths in the square grid: extremal sizes and the existence of n-dot distinct-difference arrays

Erdős's 1954 conjectures on independent sets for set mappings of the real line with nondense, bounded-measure pictures

Colouring number versus the complete bipartite graph $[[\omega_2,\omega]]$ on $\omega_{\omega+1}$ vertices under GCH (Erdős–Hajnal 1966, Problem 5.7)

Independence in $K_4$ -free graphs with no degree repeated more than four times

The order function $F(n)$ : smallest triangle-free graphs with chromatic number $n$ and no degree repeated more than three times (Erdős–Fajtlowicz–Staton)

The middle-exponent case of the Erdős–Larson matching partition relation: does $\omega^{\eta+jk} \to (\omega^{\eta+j},\ \omega^k\text{-matching})$ hold for every limit ordinal $\eta$ ?

Forcing densities $\sigma(m,f)$ for induced subgraphs of given sizes: existence of the limit and the remaining $r=3,4$ cases of the $1/r$ conjecture

The local density problem for triangles: exact determination of $\beta(\alpha)$ and the Erdős–Faudree–Rousseau–Schelp conjecture

Surviving instances of the Erdős–Pach–Pollack–Tuza diameter conjecture: sharp bounds for the diameter of connected $K_{k+1}$ -free graphs of given minimum degree for $k \le 6$

Existence and value of the limit of $(\log_2 n_k)/k^2$ for Erdős–Evans prime sets satisfying the divisibility condition (*)