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