Tue, 26 Nov 2024

15:30 - 16:30
Online

Optimizing the Campos-Griffiths-Morris-Sahasrabudhe upper bound on Ramsey numbers

Sergey Norin
(McGill University)
Further Information

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

Abstract

In a recent breakthrough Campos, Griffiths, Morris and Sahasrabudhe obtained the first exponential improvement of the upper bound on the classical Ramsey numbers since 1935. I will outline a reinterpretation of their proof, replacing the underlying book algorithm with a simple inductive statement. In particular, I will present a complete proof of an improved upper bound on the off-diagonal Ramsey numbers and describe the main steps involved in improving their upper bound for the diagonal Ramsey numbers to $R(k,k)\le(3.8)^k$ for sufficiently large $k$.

Based on joint work with Parth Gupta, Ndiame Ndiaye, and Louis Wei.

Thu, 13 Jun 2024
16:00
L5

The Gross--Kohnen--Zagier theorem via $p$-adic uniformization

Martí Roset Julià
(McGill University)
Abstract

Let $S$ be a set of rational places of odd cardinality containing infinity and a rational prime $p$. We can associate to $S$ a Shimura curve $X$ defined over $\mathbb{Q}$. The Gross--Kohnen--Zagier theorem states that certain generating series of Heegner points of $X$ are modular forms of weight $3/2$ valued in the Jacobian of $X$. We will state this theorem and outline a new approach to proving it using the theory of $p$-adic uniformization and $p$-adic families of modular forms of half-integral weight. This is joint work with Lea Beneish, Henri Darmon, and Lennart Gehrmann.

Tue, 16 Jan 2024

14:00 - 15:00
L4

Heights of random trees

Louigi Addario-Berry
(McGill University)
Abstract

A rooted tree $T$ has degree sequence $(d_1,\ldots,d_n)$ if $T$ has vertex set $[n]$ and vertex $i$ has $d_i$ children for each $i$ in $[n]$. 

I will describe a line-breaking construction of random rooted trees with given degree sequences, as well as a way of coupling random trees with different degree sequences that also couples their heights to one another. 

The construction and the coupling have several consequences, and I'll try to explain some of these in the talk.

First, let $T$ be a branching process tree with criticalmean oneoffspring distribution, and let $T_n$ have the law of $T$ conditioned to have size $n$. Then the following both hold.
1) $\operatorname{height}(T_n)/\log(n)$ tends to infinity in probability. 
2) If the offspring distribution has infinite variance then $\operatorname{height}(T_n)/n^{1/2}$ tends to $0$ in probability. This result settles a conjecture of Svante Janson.

The next two statements relate to random rooted trees with given degree sequences. 
1) For any $\varepsilon > 0$ there is $C > 0$ such that the following holds. If $T$ is a random tree with degree sequence $(d_1,\ldots,d_n)$ and at least $\varepsilon n$ leaves, then $\mathbb{E}(\operatorname{height}(T)) < C \sqrt{n}$. 
2) Consider any random tree $T$ with a fixed degree sequence such that $T$ has no vertices with exactly one child. Then $\operatorname{height}(T)$ is stochastically less than $\operatorname{height}(B)$, where $B$ is a random binary tree of the same size as $T$ (or size one greater, if $T$ has even size). 

This is based on joint work with Serte Donderwinkel and Igor Kortchemski.

Wed, 20 Oct 2021

16:00 - 17:00

Proper CAT(0) actions of unipotent-free linear groups

Sami Douba
(McGill University)
Abstract

Button observed that finitely generated linear groups containing no nontrivial unipotent matrices behave much like groups admitting proper actions by semisimple isometries on complete CAT(0) spaces. It turns out that any finitely generated linear group possesses an action on such a space whose restrictions to unipotent-free subgroups are in some sense tame. We discuss this phenomenon and some of its implications for the representation theory of certain 3-manifold groups.

Mon, 17 May 2021

15:45 - 16:45
Virtual

Tail equivalence of unicorn paths

Piotr Przytycki
(McGill University)
Abstract

Let S be an orientable surface of finite type. Using Pho-On's infinite unicorn paths, we prove the hyperfiniteness of the orbit equivalence relation coming from the action of the mapping class group of S on the Gromov boundary of the arc graph of S. This is joint work with Marcin Sabok.

Thu, 28 Jan 2021
14:00
Virtual

Spontaneous periodic orbits in the Navier-Stokes flow via computer-assisted proofs

Jean-Philippe Lessard
(McGill University)
Abstract
In this talk, we introduce a general method to obtain constructive proofs of existence of periodic orbits in the forced autonomous Navier-Stokes equations on the three-torus. After introducing a zero finding problem posed on a Banach space of geometrically decaying Fourier coefficients, a Newton-Kantorovich theorem is applied to obtain the (computer-assisted) proofs of existence. As applications, we present proofs of existence of spontaneous periodic orbits in the Navier-Stokes equations with Taylor-Green forcing.

 

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact @email.

Tue, 17 Jun 2014

14:30 - 15:30
L6

Growing random trees, maps, and squarings

Louigi Addario-Berry
(McGill University)
Abstract

We use a growth procedure for binary trees due to Luczak and Winkler, a bijection between binary trees and irreducible quadrangulations of the hexagon due to Fusy, Poulalhon and Schaeffer, and the classical angular mapping between quadrangulations and maps, to define a growth procedure for maps. The growth procedure is local, in that every map is obtained from its predecessor by an operation that only modifies vertices lying on a common face with some fixed vertex. The sequence of maps has an almost sure limit G; we show that G is the distributional local limit of large, uniformly random 3-connected graphs.
A classical result of Brooks, Smith, Stone and Tutte associates squarings of rectangles to edge-rooted planar graphs. Our map growth procedure induces a growing sequence of squarings, which we show has an almost sure limit: an infinite squaring of a finite rectangle, which almost surely has a unique point of accumulation. We know almost nothing about the limit, but it should be in some way related to "Liouville quantum gravity".
Parts joint with Nicholas Leavitt.

Tue, 03 Dec 2013

14:30 - 15:30
C2

How many edges are needed to force an $H$-minor?

Bruce Reed
(McGill University)
Abstract

We consider the parameter $a(H)$, which is the smallest a such that if $|E(G)|$ is at least/exceeds $a|V(H)|/2$ then $G$ has an $H$-minor. We are especially interested in sparse $H$ and in bounding $a(H)$ as a function of $|E(H)|$ and $|V(H)|$. This is joint work with David Wood.

Thu, 05 Jan 2012

11:30 - 12:30
Gibson 1st Floor SR

Orthogonality and stability in large matrix iterative algorithms

Professor Chris Paige
(McGill University)
Abstract

Many iterative algorithms for large sparse matrix problems are based on orthogonality (or $A$-orthogonality, bi-orthogonality, etc.), but these properties can be lost very rapidly using vector orthogonalization (subtracting multiples of earlier supposedly orthogonal vectors from the latest vector to produce the next orthogonal vector). Yet many of these algorithms are some of the best we have for very large sparse problems, such as Conjugate Gradients, Lanczos' method for the eigenproblem, Golub and Kahan bidiagonalization, and MGS-GMRES.

\\

\\

Here we describe an ideal form of orthogonal matrix that arises from any sequence of supposedly orthogonal vectors. We illustrate some of its fascinating properties, including a beautiful measure of orthogonality of the original set of vectors. We will indicate how the ideal orthogonal matrix leads to expressions for new concepts of stability of such iterative algorithm. These are expansions of the concept of backward stability for matrix transformation algorithms that was so effectively developed and applied by J. H. Wilkinson (FRS). The resulting new expressions can be used to understand the subtle and effective performance of some (and hopefully eventually all) of these iterative algorithms.

Subscribe to McGill University