All Random Solved Random Open
2 solved out of 3 shown (show only solved or open)
Any graph on $n$ vertices can be decomposed into $O(n)$ many cycles and edges.
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.

See also [583].

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.
Proved by Kwan, Sah, Sawhney, and Simkin [KSSS22b].
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.
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].