Many fundamental questions and results in graph theory, from Dirac's and Turán's theorems to the Erdős–Hajnal and Gyárfás–Sumner conjectures, can be phrased as graph embedding problems: showing that a certain graph can be embedded into any other graph satisfying certain natural properties. Over the past decades, a number of powerful techniques have been developed to address such problems.

In this talk, I will focus on one such technique, the dependent random choice method. I will discuss some new variations on this technique, and show how they can be used to resolve a number of embedding questions about graphs and digraphs, such as a "higher-dimensional" generalization of Rédei's theorem on Hamiltonian paths in tournaments.

Based on joint works with Zach Hunter, António Girão, and Patryk Morawski.