SOLVED

If $G$ is a graph with infinite chromatic number and $a_1<a_2<\cdots $ are lengths of the odd cycles of $G$ then $\sum \frac{1}{a_i}=\infty$.

OPEN

Let $G$ be a graph with $n$ vertices and $kn$ edges, and $a_1<a_2<\cdots $ be the lengths of cycles in $G$. Is it true that
\[\sum\frac{1}{a_i}\gg \log k?\]
Is the sum $\sum\frac{1}{a_i}$ minimised when $G$ is a complete bipartite graph?

A problem of Erdős and Hajnal. Gyárfás, Komlós, and Szemerédi [GyKoSz84] have proved that this sum is $\gg \log k$. Liu and Montgomery [LiMo20] have proved the asymptotically sharp lower bound of $\geq (\tfrac{1}{2}-o(1))\log k$.

See also the entry in the graphs problem collection.

See also [57].

SOLVED

Let $r\geq 3$ and $k$ be sufficiently large in terms of $r$. Is it true that every $r$-uniform hypergraph with chromatic number $k$ has at least
\[\binom{(r-1)(k-1)+1}{r}\]
edges, with equality only for the complete graph on $(r-1)(k-1)+1$ vertices?

When $r=2$ it is a classical fact that chromatic number $k$ implies at least $\binom{k}{2}$ edges. Erdős asked for $k$ to be large in this conjecture since he knew it to be false for $r=k=3$, as witnessed by the Steiner triples with $7$ vertices and $7$ edges.

This was disproved by Alon [Al85], who proved, for example, that there exists some absolute constant $C>0$ such that if $r\geq C$ and $k\geq Cr$ then there exists an $r$-uniform hypergraph with chromatic number $\geq k$ with at most \[\leq (7/8)^r\binom{(r-1)(k-1)+1}{r}\] many edges.

In general, Alon gave an upper bound for the minimal number of edges using Turán numbers. Using known bounds for Turán numbers then suffices to disprove this conjecture for all $r\geq 4$. The validity of this conjecture for $r=3$ remains open.

If $m(r,k)$ denotes the minimal number of edges of any $r$-uniform hypergraph with chromatic number $>k$ then Akolzin and Shabanov [AkSh16] have proved \[\frac{r}{\log r}k^r \ll m(r,k) \ll (r^3\log r) k^r,\] where the implied constants are absolute. Cherkashin and Petrov [ChPe20] have proved that, for fixed $r$, $m(r,k)/k^r$ converges to some limit as $k\to \infty$.

SOLVED

Does there exist an absolute constant $c>0$ such that, for all $r\geq 2$, in any $r$-uniform hypergraph with chromatic number $3$ there is a vertex contained in at least $(1+c)^r$ many edges?

In general, determine the largest integer $f(r)$ such that every $r$-uniform hypergraph with chromatic number $3$ has a vertex contained in at least $f(r)$ many edges. It is easy to see that $f(2)=2$ and $f(3)=3$. Erdős did not know the value of $f(4)$.

This was solved by Erdős and Lovász [ErLo75], who proved in particular that there is a vertex contained in at least \[\frac{2^{r-1}}{4r}\] many edges.

OPEN

Does there exist a $3$-critical $3$-uniform hypergraph in which every vertex has degree $\geq 7$?

A problem of Erdős and Lovász.

They do not specify what is meant by $3$-critical. One definition in the literature is: a hypergraph is $3$-critical if there is a set of $3$ vertices which intersects every edge, but no such set of size $2$, and yet for any edge $e$ there is a pair of vertices which intersects every edge except $e$. Raphael Steiner observes that a $3$-critical hypergraph in this sense has bounded size, so this problem would be a finite computation, and perhaps is not what they meant.

An alternative definition is that a hypergraph is $3$-critical if it has chromatic number $3$, but its chromatic number becomes $2$ after deleting any edge or vertex.

OPEN

Does there exist a $k>2$ such that the $k$-sized subsets of $\{1,\ldots,2k\}$ can be coloured with $k+1$ colours such that for every $A\subset \{1,\ldots,2k\}$ with $\lvert A\rvert=k+1$ all $k+1$ colours appear among the $k$-sized subsets of $A$?

A problem of Erdős and Rosenfeld. This is trivially possible for $k=2$. They were not sure about $k=6$.

This is equivalent to asking whether there exists $k>2$ such that the chromatic number of the Johnson graph $J(2k,k)$ is $k+1$ (it is always at least $k+1$ and at most $2k$). The chromatic numbers listed at this website show that this is false for $3\leq k\leq 8$.

OPEN

Let $r\geq 2$ and $G$ be a $r$-uniform hypergraph with chromatic number $3$, such that any two edges have non-empty intersection. Must $G$ contain $O(r^2)$ many vertices? Must there be two edges which meet in $\gg r$ many vertices?

A problem of Erdős and Shelah. The Fano geometry gives an example where there are no two edges which meet in $r-1$ vertices. Are there any other examples?

Erdős and Lovász [ErLo75] proved that there must be two edges which meet in $\gg \frac{r}{\log r}$ many vertices.

OPEN

Let $k\geq 2$ and $A_k\subseteq [0,1]$ be the set of $\alpha$ such that there exists some $\beta(\alpha)>\alpha$ with the property that, if $G_1,G_2,\ldots$ is a sequence of $k$-uniform hypergraphs with
\[\liminf \frac{e(G_n)}{\binom{\lvert G_n\rvert}{k}} >\alpha\]
then there exist subgraphs $H_n\subseteq G_n$ such that $\lvert H_n\rvert \to \infty$ and
\[\liminf \frac{e(H_n)}{\binom{\lvert H_n\rvert}{k}} >\beta,\]
and further that this property does not necessarily hold if $>\alpha$ is replaced by $\geq \alpha$.

What is $A_3$?

A problem of Erdős and Simonovits. It is known that
\[A_2 = \left\{ 1-\frac{1}{k} : k\geq 1\right\}.\]