Do there exist universal sequences for all mazes on the two-dimensional integer lattice? We will give background on this question, as well as some recent results. Joint work with Mariaclara Ragosta.

Semidefinite programming (SDP) is a powerful tool in the design of approximation algorithms. After providing a gentle introduction to the basics of this method, I will explore a different facet of SDP and show how it can be used to derive short and elegant proofs of both classical and new estimates related to the MaxCut problem and discrepancy theory in graphs and matrices.

Building on this, I will demonstrate how these results lead to an improved upper bound on the celebrated log-rank conjecture in communication complexity.

A matroid is frame if it can be extended such that it possesses a basis $B$ (a frame) such that every element is spanned by at most two elements of $B$. Frame matroids extend the class of graphic matroids and also have natural graphical representations. We characterise the inequivalent graphical representations of 3-connected frame matroids that have a fixed element $\ell$ in their frame $B$. One consequence is a polynomial time recognition algorithm for frame matroids with a distinguished frame element.

Joint work with Jim Geelen and Cynthia Rodríquez.

At most how many edge-disjoint Hamilton cycles does a given directed graph contain? It is easy to see that one cannot pack more than the minimum in-degree or the minimum out-degree of the digraph. We show that in the random directed graph $D(n,p)$ one can pack precisely this many edge-disjoint Hamilton cycles, with high probability, given that $p$ is at least the Hamiltonicity threshold, up to a polylog factor.

Based on a joint work with Asaf Ferber.

Graphs (and structures) which have a linear ordering of their vertices with given local properties have a rich spectrum of complexities. Some have full power of class NP (and thus no dichotomy) but for biconnected patterns we get dichotomy. This also displays the importance of Sparse Incomparability Lemma. This is a joint work with Gabor Kun (Budapest).