Erdős Problems

Tags Prizes

All Random Solved Random Open

2 solved out of 3 shown (show only solved or open)

OPEN

Any graph on $n$ vertices can be decomposed into $O(n)$ many cycles and edges.

#184: [EGP66][Er71][Er76][Er81][Er83b]

graph theory, cycles

Conjectured by Erdős and Gallai, who proved that $O(n\log n)$ many cycles and edges suffices.

The best bound available is due to Bucić and Montgomery [BM22], who prove that $O(n\log^*n)$ many cycles and edges suffice, where $\log^*$ is the iterated logarithm function.

Conlon, Fox, and Sudakov [CFS14] proved that $O_\epsilon(n)$ cycles and edges suffice if $G$ has minimum degree at least $\epsilon n$, for any $\epsilon>0$.

See also [583].

SOLVED

For any $g\geq 2$, if $n$ is sufficiently large and $\equiv 1,3\pmod{6}$ then there exists a 3-uniform hypergraph on $n$ vertices such that

every pair of vertices is contained in exactly one edge (i.e. the graph is a Steiner triple system) and
for any $2\leq j\leq g$ any collection of $j$ edges contains at least $j+3$ vertices.

#207: [Er76]

combinatorics, hypergraphs

Proved by Kwan, Sah, Sawhney, and Simkin [KSSS22b].

SOLVED

Suppose $n\geq kr+(t-1)(k-1)$ and the edges of the complete $r$-uniform hypergraph on $n$ vertices are $t$-coloured. Prove that some colour class must contain $k$ pairwise disjoint edges.

#780: [Er76]

combinatorics, hypergraphs, chromatic number

In other words, this problem asks to determine the chromatic number of the Kneser graph. This would be best possible: if $n=kr-1+(t-1)(k-1)$ then decomposing $[n]$ as one set $X_1$ of size $kr-1$ and $t-1$ sets $X_2,\ldots,X_{t}$ of size $k-1$, a colouring without $k$ pairwise disjoint edges is given colouring all subsets of $X_0$ in colour $1$ and assigning an edge with colour $2\leq i\leq t$ if $i$ is minimal such that $X_i$ intersects the edge.

When $k=2$ this was conjectured by Kneser and proved by Lovász [Lo78]. The general case was proved by Alon, Frankl, and Lovász [AFL86].