In this talk, we will present some ideas behind our recent proofs of three long-standing problems of Erdős from the 70s.

(a)

The Erdős-Faber-Lovász conjecture (1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. We prove this conjecture for every large n.

(b)

What is the maximum number of edges that an n-vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set? In the nearly 50 years since Erdős posed this problem, it has been reiterated several times in the literature, including by Bollobás (1978), by Pyber, Rödl and Szemerédi(1995) and by Chen, Erdős, and Staton (1996). We resolve this problem up to a polylogarithmic factor by showing that the answer is n polylog(n). Our proof combines a variety of techniques including sublinear expanders, absorption and a novel tool for regularisation, which is of independent interest.

(c)

What is the maximum number of edges that an n-vertex graph can have without containing a cycle with all diagonals? In 1975, Erdős observed that the upper bound O(n^{5/3}) holds since the complete bipartite graph K_{3,3} can be viewed as a cycle of length six with all diagonals. We resolve this problem by proving that there exists a constant C such that every n-vertex with Cn^{3/2} edges contains a cycle with all diagonals. This bound is best possible. Our proof involves a novel lemma about finding an almost-spanning robust expander.