Open-problem statements, with their sources attached.

To prove erdos_539.variants.sq it suffices to show $h(n)\ll n^{1/2}$.

Let $h(n)$ be maximal such that, for any set $A\subseteq \mathbb{N}$ of size $n$, the set$\left\{ \frac{a}{(a,b)}: a,b\in A\right\}$has size at least $h(n)$. Is $h(n) = \Theta(n^{2/3})$?

To prove erdos_539.variants.sq_cube_root it suffices to show $n^{2/3}\ll h(n)$.

From [Er73]: The determination of

will perhaps be not too difficult.

Let $R_r(n)$ denote the $r$-uniform hypergraph Ramsey number: the minimal $m$ such that if we $2$-colour all edges of the complete $r$-uniform hypergraph on $m$ vertices then there must be some monochromatic copy of the complete $r$-uniform hypergraph on $n$ vertices.

Prove that, for $r \ge 3$, $\log_{r-1} R_r(n) \asymp_r n,$ where $\log_{r-1}$ denotes the $(r-1)$-fold iterated logarithm.

Let $R_3(n)$ be the minimal $m$ such that if the edges of the $3$-uniform hypergraph on $m$ vertices are $2$-coloured then there is a monochromatic copy of the complete $3$-uniform hypergraph on $n$ vertices.

Is there some constant $c>0$ such that $R_3(n) \geq 2^{2^{cn}}?$

Let $G$ be such that any subgraph on $k$ vertices has at most $2k-3$ edges. Is it true that, if $H$ has $m$ edges and no isolated vertices, then $\hat{r}(G,H) \ll m$?

In other words: if $G$ is sparse (every induced subgraph on $k$ vertices has $≤ 2k-3$ edges), is $G$ Ramsey size linear?

Erdős Problem 567 (Q3)*

Is $Q_3$ (the 3-dimensional hypercube) Ramsey size linear?

Erdős Problem 567 (K33)*

Is $K_{3,3}$ Ramsey size linear?

Erdős Problem 567 (H5)*

Is $H_5$ ($C_5$ with two vertex-disjoint chords) Ramsey size linear?

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

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.

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.

*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].

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

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.

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

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

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.