CanaDAM 2021
On-line, May 25 - 28, 2021

Extremal Combinatorics
Org: Natasha Morrison (University of Victoria)

MARCELO CAMPOS, Instituto de Matemática Pura e Aplicada
Singularity of random symmetric matrices revisited  [PDF]

Let $M_n$ be drawn uniformly from all $\pm 1$ symmetric $n \times n$ matrices. I'll describe recent work where we show that the probability that $M_n$ is singular is at most $\exp(-\Omega (\sqrt{n \log n}))$. This represents a natural barrier in recent approaches to this problem and improves the best-known previous bound by Campos, Mattos, Morris and Morrison of $\exp(-\Omega (\sqrt{n}))$ on the singularity probability. In particular I'll show a new Inverse Littlewood-Offord type theorem, which is simpler and stronger in some ways than previous theorems of this type.

This is joint work with Matthew Jenssen, Marcus Michelen, Julian Sahasrabudhe.

SHOHAM LETZTER, University College London
Chi-boundedness of graphs with no cycle with exactly k chords  [PDF]

A family of graph $\mathcal{H}$ is called $\chi$-bounded if there is a function $f$ such that for every graph $H \in \mathcal{H}$, the following holds: $\chi(H) \le f(\omega(H))$, where $\chi(H)$ is the chromatic number of $H$ and $\omega(H)$ is the clique number of $H$.

We show that the family of graphs with no cycle with exactly $k$ chords is $\chi$-bounded, for every sufficiently large $k$.

This is joint work with Joonkyung Lee and Alexey Pokrovskiy.

ROB MORRIS, Instituto de Matemática Pura e Aplicada
Flat Littlewood Polynomials Exist  [PDF]

A polynomial $P(z) = \sum_{k=0}^n \varepsilon_k z^k$ is a Littlewood polynomial if $\varepsilon_0,\ldots,\varepsilon_n \in \{-1,1\}$. We will describe a proof that, for every $n \geqslant 2$, there exist 'flat' Littlewood polynomials of degree $n$, that is, with $$\delta\sqrt{n} \, \leqslant \, |P(z)| \, \leqslant \, \Delta\sqrt{n}$$ for all $z \in \mathbb{C}$ with $|z| = 1$, for some absolute constants $\Delta > \delta > 0$. This answers a question of Erdos, and confirms a conjecture of Littlewood. The proof is entirely combinatorial, and uses probabilistic ideas from discrepancy theory.

Joint work with Paul Balister, Béla Bollobás, Julian Sahasrabudhe and Marius Tiba.

WOJCIECH SAMOTIJ, Tel Aviv University
Sharp thresholds for Ramsey properties  [PDF]

Given graphs $G$ and $H$ and an integer $r \ge 2$, write $G \to (H)_r$ if every $r$-colouring of the edges of $G$ contains a monochromatic copy of $H$. Ramsey's theorem states that, when $n$ is sufficiently large, $G \to (H)_r$ is a nontrivial, monotone property of subgraphs of $K_n$. The celebrated work of Rödl and Ruciński located the threshold for this property in the random graph $G_{n,p}$ for all $H$ and $r$. We prove that this threshold is sharp when $H$ is a clique or a cycle.

Joint work with Ehud Friedgut, Eden Kuperwasser, and Mathias Schacht.

KATHERINE STADEN, University of Oxford
Ringel's tree packing conjecture  [PDF]

The graph decomposition (or packing) problem asks when the edge set of a host graph can be decomposed into copies of a given guest graph. I will present the following theorem on tree decomposition (joint work with Peter Keevash): given any tree $T$ with $r$ edges, any dense quasirandom graph $G$ with $n$ vertices and $rn$ edges can be decomposed into $n$ copies of $T$. The special case when $G$ is the complete graph is Ringel's tree packing conjecture from 1963. An independent proof of the original conjecture was also obtained by Montgomery, Pokrovskiy and Sudakov.