Open-problem statements, with their sources attached.

Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $\sqrt{n}$ edges?

Erdős Problem 252: irrationality of the sum for a given $k$.

Let $\mathfrak{m}$ be an infinite cardinal and $G$ be a graph with chromatic number $\mathfrak{m}$. Let $r\geq 1$. Must $G$ contain a subgraph of chromatic number $\mathfrak{m}$ which does not contain any odd cycle of length $\leq r$?

For a fixed k ≥ 5, is ∑ σ k n / n! irrational?.

Let $A\subseteq \mathbb{N}$ be such that $A+A$ has positive lower density. Can one always decompose $A=A_1\sqcup A_2$ such that $A_1+A_1$ and $A_2+A_2$ both have positive lower density?

Let $A\subseteq \mathbb{N}$ be such that $\lvert A\cap [1,2x]\rvert -\lvert A\cap [1,x]\rvert \to \infty\textrm{ as }x\to \infty$ and $\sum_{n\in A} \{ \theta n\}=\infty$ for every $\theta\in (0,1)$, where $\{x\}$ is the distance of $x$ from the nearest integer. Then every sufficiently large integer is the sum of distinct elements of $A$.

Murty-Simon Conjecture*

Let $G$ be a graph on $n$ vertices with diameter $2$ such that deleting any edge increases the diameter. Is it true that $G$ has at most $\lfloor n^2 / 4 \rfloor$ edges? Equality is conjectured to hold for the complete balanced bipartite graph $K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor}$.

The conjecture is resolved up to a finite check: Fan [Fa87] verified it for $n \leq 24$ and $n = 26$, and Füredi [Fü92] proved it for all sufficiently large $n$.

Let $A\subseteq\mathbb{N}$ be an infinite set. Is

irrational?

Is there a graph of chromatic number ℵ_ 1 with ℵ_ 1 vertices such that for all ε > 0, if n is sufficiently large and H is a subgraph on n vertices, then H contains an independent set of size > n ^ (1 - ε)?

Let $a_1 < a_2 < \cdots$ be an increasing sequence such that $\frac{a_n}{n} \to \infty$. Is the sum $\sum_{n}^{\infty} \frac{a_n}{2^{a_n}}$ irrational?

What is the supremum of the set of admissible numbers?

Is $a_n = 2^{2^n}$ an irrationality sequence in the above sense?

Is every proportionately dissociated (infinite) set the union of a finite number of dissociated sets?

Is $n!$ an example of an irrationality sequence?

Let $h(n)$ be maximal such that if $A\subseteq \mathbb{Z}$ with $\lvert A\rvert=n$ then there is $B\subseteq A$ with $\lvert B\rvert \geq h(n)$ such that if $a_1+\cdots+a_r=b_1+\cdots+b_s$ with $a_i,b_i\in B$ then $r=s$.

Estimate $h(n)$.

Let $F_1=F_2=1$ and $F_{n+1} = F_n + F_{n-1}$ be the Fibonacci sequence. Let $n_1 < n_2 < \dots$ be an infinite sequence with $\frac{n_{k+1}}{n_k} \ge c > 1$. Must $\sum_k \frac 1 {F_{n_k}}$ be irrational?

Let $h(n)$ be maximal such that if $A\subseteq \mathbb{Z}$ with $\lvert A\rvert=n$ then there is $B\subseteq A$ with $\lvert B\rvert \geq h(n)$ such that if $a_1+\cdots+a_r=b_1+\cdots+b_s$ with $a_i,b_i\in B$ then $r=s$.

Is $h(n) = \Theta(\sqrt{n})$?

Let $F_1=F_2=1$ and $F_{n+1} = F_n + F_{n-1}$ be the Fibonacci sequence. Let $n_1 < n_2 < \dots$ be an infinite sequence with $\frac {n_k}{k} \to \infty$. Must $\sum_k \frac 1 {F_{n_k}}$ be irrational?

By the solved variant erdos_789.variants.isBigO_sq, in order to prove erdos_789.variants.sq it suffices to show $\sqrt{n}=O(h(n))$.

Let $P$ be a finite set of primes with $|P| \ge 2$ and let $\{a_1 < a_2 < \dots\}$ be the set of positive integers whose prime factors are all in $P$. Is the sum $\sum_{n=1}^\infty \frac{1}{[a_1,\ldots,a_n]}$ rational?