Erdős Problems

Let $1 \leq a_1 < a_2 < \cdots < a_k \leq n$ be a sequence of integers for which all the subset sums $\sum_{i=1}^{k} \varepsilon_i a_i$ ($\varepsilon_i = 0$ or $1$) are distinct. T…

A system of congruences … is called a covering system if every integer satisfies at least one of the congruences in (3). The simplest covering system is $0 \pmod 2$, $0 \pmod 3$,…

I conjectured long ago that if … then the $a_i$'s contain arbitrarily long arithmetic progressions. If true this of course implies that there are arbitrarily long arithmetic progre…

Let $2 = p_1 < p_2 < \cdots$ be the sequence of consecutive primes. [...] $p_{n+1} - p_n = d_n$. [...] Sharpening previous results of Backlund, Brauer-Zeitz, and Westzynthius, I pr…

Let $2 = p_1 < p_2 < \cdots$ be the sequence of consecutive primes. [...] $p_{n+1} - p_n = d_n$. [...] It seems likely that $d_n/\log n$ is everywhere dense in $(0, \infty)$. Ricci…

Let $2 = p_1 < p_2 < \cdots$ be the sequence of consecutive primes. [$p_{n+1} - p_n = d_n$.] Turán and I [15] proved that the inequalities $d_{n+1} > d_n$ and $d_{n+1} < d_n$ both…

Many further unsolved problems can be asked about covering systems. Selfridge and I asked: Is there a covering system all whose moduli are odd?

A family of residue classes $a_i \pmod{n_i}$ with $1 < n_1 < \ldots < n_r$ is called a system of covering congruences if every integer belongs to at least one of the residue classe…

Crocker [16] proved that there are infinitely many odd integers not of the form $2^{k_1} + 2^{k_2} + p$, but his proof only gives that the number of integers $\leq x$ not of the fo…

One could ask the following (probably unattackable) problem. Is it true that there is an $r$ so that every integer is the sum of a prime and $r$ or fewer powers of 2.

Are there infinitely many odd integers $n$ for which $n - 2^u$, $1 \le 2^u \le n$ is never squarefree? In fact is there any such an integer?

Let $a_1 < \cdots$ be an infinite sequence of integers where no $a_i$ divides the sum of two greater $a$'s. Sárközi and I proved that the $a$'s then have density $0$ and this resul…

Let $a_1 < \cdots < a_k \leq x$ be a sequence of integers where no $a$ divides the sum of two larger $a$'s. Probably …

Now I state a few problems of Nathanson and myself : Let $a_1 < a_2 < \cdots$ be an infinite sequence of integers; denote by $f(n)$ the number of solutions of $n = a_i + a_j$. Deno…

I just discovered in it a forgotten conjecture of mine, which might still be of interest. Let $\{p_n\}$ be the sequence of consecutive primes. Is it true that…

Perhaps the following rather silly conjecture could be added. Is it true that the set of odd integers not of the form $2^k + p$ is the not necessarily disjoint union of an infinite…

A purely computational problem (this problem cannot be attacked by other means at present). Call a prime $p$ good if every even number $2r \leq p - 3$ can be written in the form…

I proved long ago that every $m < n!$ is the distinct sum of $n - 1$ or fewer divisors of $n!$. Let $h(m)$ be the smallest integer, if it exists, for which every integer less than…

Conjecture of Faber, Lovász and myself. Let $G_1, \ldots, G_n$ be $n$ edge-disjoint complete graphs on $n$ vertices. We conjectured more than 20 years ago that the chromatic number…

A family of sets $A_i$, $i = 1, 2, \ldots,$ is called a strong $\Delta$-system if all the intersections $A_i \cap A_j$ ($i \neq j$) are identical, i.e., if…

Problem of Lovász and myself, [32]. Let $f(n)$ be the smallest integer with the following property: There is a family $A_k$, $1 \leqq k \leqq f(n)$ satisfying $|A_k| = n$,…

There remains the following problem. Does there exist a $G(n, [n^2/8])$ without a $K_4$ and at most $o(n)$ independent points? (As usual, $G(n, m)$ denotes a graph with $n$ points…

Is it true that every graph of $5n$ vertices which contains no triangle can be made two-chromatic by the omission of at most $n^2$ edges? It is easy to see that if this is true it…

4. In Problem 6 I ask (among other questions) whether it is true that every graph of $(2k+1)n$ vertices, the smallest odd cycle of which has size $\geq 2k+1$, can be made bipartite…

Let $n_1 < n_2 < \ldots$ be an arbitrary sequence of integers. Now the following question is perhaps of interest: Exclude one or several residues mod $n_i$ (where only the integers…