Logo
Tags Prizes
More
FAQ Problem Lists Definitions Links How to help
All Random Solved Random Open
3 solved out of 8 shown (show only solved or open)
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$.
Conjectured by Erdős and Hajnal, and solved by Liu and Montgomery [LiMo20]. In [Er81] Erdős asks whether the $a_i$ must in fact have positive upper density. The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.

See also [65].

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

Additional thanks to: Zach Hunter
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.

Additional thanks to: Noga Alon and Zach Hunter
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.

Additional thanks to: Raphael Steiner
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$.

Additional thanks to: Bhavik Mehta
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\}.\]