Open-problem statements, with their sources attached.

For every positive integer $n$ divisible by $4$, there is an $n\times n$ matrix $H$ with entries in $\{\pm1\}$ and $HH^{\mathsf T}=nI$.

$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$.

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$.

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).

Infinite-target case.* When all $\kappa_\alpha \geq \aleph_0$ are infinite and bounded by $\lambda$, $\kappa_\alpha + 1 = \kappa_\alpha$, so the hypothesis simplifies to a "pure" stepping-down lemma:

$r = 2$ case.* The stepping-down from 3-uniform to 2-uniform partition relations: $2^\lambda \to (\kappa_\alpha + 1)_{\alpha<\gamma}^3$ implies $\lambda \to (\kappa_\alpha)_{\alpha<\gamma}^2$. Generalises the classical Erdős–Rado stepping-up/down theorem for pairs.