Open-problem statements, with their sources attached.

Let $\delta > 0$. If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_{2,2,2}$ (the octahedron) and at least $\delta n^2$ edges, must $G$ contain an independent set of size $\gg_\delta n$?

This is a problem of Erdős, Hajnal, Sós, and Szemerédi [EHSS83]. It is open; they proved the statement for $\delta > 1/8$ (see erdos_579.variants.ehss_large_delta), and the difficulty is to push the edge-density threshold down to an arbitrary $\delta > 0$.

Here $K_{2,2,2}$ is the complete tripartite graph with all parts of size $2$, encoded as completeMultipartiteGraph (fun _ : Fin 3 => Fin 2); "contains no $K_{2,2,2}$" is expressed via SimpleGraph.Free.

Erdős Problem 17.* Are there infinitely many cluster primes?

*Erdős Problem 593 ($500)**: Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number$> \aleph_0$.

A natural conjectural characterization, recorded here, is that the obligatory finite 3-uniform hypergraphs are exactly the 2-colorable ones (Property B). The forward direction (IsObligatory → IsTwoColorable) and converse (IsTwoColorable → IsObligatory) are stated as separate variants below; in the graph case ($r = 2$), Erdős–Galvin–Hajnal [EGH75] proved the analogous result (obligatory ⇔ bipartite).

Conjecture 1.* Are there infinitely many practical numbers $m$ such that $h(m) < (\log \log m)^{O(1)}$?

More precisely: does there exist a constant $C > 0$ such that for infinitely many practical numbers $m$, we have $h(m) < (\log \log m)^C$?

Erdős Problem 593 , Necessary direction*: Every obligatory finite 3-uniform hypergraph is 2-colorable.

This is the natural necessary condition for the conjectural characterization in erdos_593: if a finite 3-uniform hypergraph F is not 2-colorable, one expects to construct a hypergraph with large chromatic number that contains no copy of F.

Conjecture 2.* Is it true that $h(n!) < n^{o(1)}$? That is, for all $\varepsilon > 0$, is $h(n!) < n^\varepsilon$ for sufficiently large $n$?

Erdős Problem 593 , Sufficient direction*: Every finite 2-colorable 3-uniform hypergraph is obligatory.

This is the converse direction of the erdos_593 characterization: if 2-colorability matches the graph-case characterization (bipartite ⇔ obligatory), then every 2-colorable finite 3-uniform hypergraph must appear in every 3-uniform hypergraph of chromatic number $> \aleph_0$.

Together with erdos_593.variants.obligatory_implies_two_colorable, this implies erdos_593.

Conjecture 3.* Or perhaps even $h(n!) < (\log n)^{O(1)}$?

Erdős offered $250 for a proof or disproof.

*Erdős Problem 595 ($250)**: Is there an infinite graph$G$which contains no$K_4$ and is not the union of countably many triangle-free graphs?

A problem of Erdős and Hajnal [Er87].

Let $s_1 < s_2 < \dots$ be the sequence of squarefree numbers. Is it true that for any $\epsilon > 0$ and large $n$, $s_{n+1} - s_n \ll_\epsilon s_n^\epsilon$?

Erdős Problem 596* (Erdős–Hajnal, [Er87]). For which graph pairs $(G_1, G_2)$ is it true that

(1) for every $n \geq 1$ there is a graph $H$ without a $G_1$ such that any $n$-colouring of $H$'s edges contains a monochromatic $G_2$, and yet (2) for every graph $H$ without a $G_1$ there is an $\aleph_0$-colouring of $H$'s edges with no monochromatic $G_2$?

Erdős and Hajnal originally conjectured that no such pair exists; but $(C_4, C_6)$ witnesses it (Nešetřil–Rödl + Erdős–Hajnal). The full question is to characterise the class of all such pairs, recorded here as answer(sorry).

See Problem 595 for the specific case $(G_1, G_2) = (K_4, K_3)$.

Let $s_1 < s_2 < \dots$ be the sequence of squarefree numbers. Is it true that $s_{n + 1} - s_n \le (1 + o(1)) \cdot (\pi^2 / 6) \cdot \log (s_n) / \log (\log (s_n))$?

Whether $(K_4, K_3)$ is Erdős–Hajnal exceptional is precisely the content of Erdős Problem 595. The finite Ramsey property holds (Folkman 1970, Nešetřil–Rödl [NeRo75]); the open part is whether every $K_4$-free graph is a countable union of triangle-free graphs.

In [Er79] Erdős says perhaps $s_{n+1} - s_n \ll \log s_n$, but he is 'very doubtful'.

[Er79] Erdős, Paul, Some unconventional problems in number theory. Math. Mag. (1979), 67-70.

Let $r \geq 2$. Is it true that $e(n,r+1) - e(n,r) \to \infty$ as $n \to \infty$?

The set of indices $n$ for which a prime gap is followed by a larger or equal prime gap has a natural density of $\frac 1 2$.

Let $r \geq 2$. Is it true that $\frac{e(n,r+1)}{e(n,r)} \to 1$ as $n \to \infty$?

The set of indices $n$ for which a prime gap is preceeded by a larger or equal prime gap has a natural density of $\frac 1 2$.

The Erdős–Hajnal Conjecture states that there is a constant $c(H) > 0$ for each $H$ such that we can take $f(n) = n^{c(H)}$ in the above formulation.

There are infintely many indices $n$ such that the prime gap at $n$ is equal to the prime gap at $n+1$. This is equivalent to the existence of infinitely many arithmetic progressions of length $3$, see erdos_141.variants.infinite_three.