Combinatorial Theory Seminar

In this talk I will discuss a new lower bound for the off-diagonal Ramsey numbers $R(3,k)$. For this, we develop a version of the triangle-free process that is significantly easier to analyse than the original process. We then 'seed' this process with a carefully chosen graph and show that it results in a denser graph that is still sufficiently pseudo-random to have small independence number.

This is joint work with Marcelo Campos, Matthew Jenssen and Marcus Michelen.

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).

The class of $t$-perfect graphs consists of graphs whose stable set polytopes are defined by their non-negativity, edge inequalities, and odd circuit inequalities. These were first studied by Chvátal in 1975, motivated by the related and well-studied class of perfect graphs. While perfect graphs are easy to colour, the same is not true for $t$-perfect graphs; numerous questions and conjectures have been posed, and even the most basic, on whether there exists some $k$ such that every $t$-perfect graph is $k$-colourable, has remained open since 1994. I will talk about joint work with Maria Chudnovsky, Linda Cook, James Davies, and Sang-il Oum in which we establish the first finite bound and show that a little less than 200 000 colours suffice.

The normal covering number $\gamma(G)$ of a finite group $G$ is the minimal size of a collection of proper subgroups whose conjugates cover the group. This definition is motivated by number theory and related to the concept of intersective polynomials. For the symmetric and alternating groups we will see how these numbers are closely connected to some elementary (as in "relating to basic concepts", not "easy") problems in additive combinatorics, and we will use this connection to better understand the asymptotics of $\gamma(S_n)$ and $\gamma(A_n)$ as $n$ tends to infinity.