Open-problem statements, with their sources attached.

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 edge colours?

A problem of Erdős, Galvin, and Hajnal. The consistency of this was proved by Hajnal and Komjáth.

$F(n) \leq n^{3/2}$.

Conjecture 1.6 (Even case).* For a nonempty isolate-free graph $G$ on $n$ vertices, if $D$ is even, then $(D + 2)^2 \cdot i(G) \leq (D^2 + 4) \cdot n$.

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 $|X| = \kappa$ contains subsets of all possible colours?

Conjecture 1.6 (Odd case).* For a nonempty isolate-free graph $G$ on $n$ vertices, if $D$ is odd, then $(D + 1)(D + 3) \cdot i(G) \leq (D^2 + 3) \cdot n$.

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 ≠ j, the intersection A_i ∩ A_j is finite and |A_i ∩ A_j| ≠ 1. Does there exist a 2-colouring f : α → Fin 2 such that no A_i is monochromatic?

This is an open question about Property B for almost-disjoint families with a forbidden intersection size of 1. Note:* This generalises the formulation in which the ground set is ℕ. Since every countably infinite set is in bijection with ℕ, the two formulations are equivalent, but working over an arbitrary ground type makes the statement apply immediately to, e.g., almost-disjoint families of countable subsets of an uncountable space.

For $n > 8$, $2^n$ is not the the sum of distinct powers of $3$. Expressed here in terms of the base $3$ digits of $n$.

This conjecture is equivalent to the halting of a $15$-state $2$-symbol Turing Machine.

TODO(lezeau): Formalize the Turing Machine version of this problem.

Source: Hardness of Busy Beaver Value BB(15): https://link.springer.com/chapter/10.1007/978-3-031-72621-7_9 This is also https://arxiv.org/abs/2107.12475.

If $A\subseteq\{1, ..., N\}$ with $|A| = n$ is such that the subset sums $\sum_{a\in S}a$ are distinct for all $S\subseteq A$ then

A generalisation of the problem to sets $A \subseteq (0, N]$ of real numbers, such that the subset sums all differ by at least $1$ is proposed in [Er73] and [ErGr80].

[Er73] Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138.

[ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).

Is there some $k$ such that every integer is the sum of a prime and at most $k$ powers of $2$?

Granville and Soundararajan [GrSo98] have conjectured that at most $3$ powers of $2$ suffice for all odd integers, and hence at most $4$ powers of $2$ suffice for all even integers.

Ref: Granville, A. and Soundararajan, K., A Binary Additive Problem of Erdős and the Order of $2$ mod $p^2$

Bogdan Grechuk has observed that $1117175146$ is not the sum of a prime and at most $3$ powers of $2$, and pointed out that parity considerations, coupled with the fact that there are many integers not the sum of a prime and $2$ powers of $2$ suggest that there exist infinitely many even integers which are not the sum of a prime and at most $3$ powers of $2$).

Does every graph with chromatic number $\aleph_1$ contain a countable subgraph which is infinitely connected?

For every r ≥ 4 and k ≥ 2 is there some finite f(k,r) such that every graph of chromatic number ≥ f(k,r) contains a subgraph of girth ≥ r and chromatic number ≥ k?

Are there infinitely many binomial coefficients with deficiency 1?

Are there only finitely many binomial coefficients with deficiency > 1?

Let $A=\{1\leq a_1 < a_2 < \cdots\}$ and $B=\{1\leq b_1 < b_2 < \cdots\}$ be sets of integers with $a_n/b_n\to 1$.

If $A+B$ contains all sufficiently large positive integers then is it true that $\limsup 1_A\ast 1_B(n)=\infty$?

A conjecture of Erdős and Sárközy.

Erdős Problem 1167.* Let $r \geq 2$ be finite, $\gamma \geq 2$, and $\lambda$ be an infinite cardinal. Let $\kappa_\alpha$ be cardinals for all $\alpha < \gamma$. Is it true that $2^\lambda \to (\kappa_\alpha + 1)_{\alpha < \gamma}^{r+1}$ implies $\lambda \to (\kappa_\alpha)_{\alpha < \gamma}^r?$ Here $+$ means cardinal addition, so that $\kappa_\alpha + 1 = \kappa_\alpha$ if $\kappa_\alpha$ is infinite.

A problem of Erdős, Hajnal, and Rado.

Finite-target case.* When all $\kappa_\alpha$ are finite, $\kappa_\alpha + 1$ is the ordinary natural-number successor. Special case of erdos_1167.

Binary-color case.* The $\gamma = 2$ specialization (two color classes).