Title and Abstracts

Natalie Behague (University of Victoria)

Title: Subgraphs in Semi-random Graphs (and Hypergraphs)

Abstract: The semi-random graph process can be thought of as a one player game. Starting with an empty graph on n vertices, in each round a random vertex u is presented to the player, who chooses a vertex v and adds the edge uv to the graph. Given a graph property, the objective of the player is to force the graph to satisfy this property in as few rounds as possible.

We will consider the property of constructing a fixed graph G as a subgraph of the semi-random graph. Ben-Eliezer, Gishboliner, Hefetz and Krivelevich proved that the player can asymptotically almost surely construct G given n^{1 – 1/d}w rounds, where w is any function tending to infinity with n and d is the degeneracy of the graph G. We have proved a matching lower bound. I will talk about this result, and also discuss a generalisation of our approach to semi-random hypergraphs. I will finish with some open questions.

This is joint work with Trent Marbach, Pawel Pralat and Andrzej Rucinski.

Andrea Ottolini (U Washington)

Title: Rates of convergence for a Gibbs sampler on the hypercube

Abstract: In his work on partial exchangeability, de Finetti introduced a family of truncated Gaussian measures on $[0,1]^d$. One easy-to-implement procedure to get approximate samples from these measures is to run the Gibbs sampler, a Markov chain that suitably updates one (randomly chosen) coordinate at each step. In this talk, I will present some results and open questions concerning its mixing time. This is based on joint work with B. Gerencsér.

Delphin Sénizergues (UBC)

Title: Mesoscopic limit for the minimal spanning tree of the complete graph

Abstract: We consider the complete graph on n vertices endowed with i.i.d. weights on its edges and construct the associated minimal spanning tree M_n.

The local and global behaviour of this random object as n tends to infinity can respectively be described by its local weak limit, which is an infinite discrete tree, and by its scaling limit, which is a compact continuum random tree.

In an ongoing project with Omer Angel, we introduce a third limiting object, which is an infinite continuum tree, which encodes the mesoscopic behaviour of M_n around a typical vertex, when n is large. I will present a construction of this new object, its relation with the two other limiting objects mentioned above, as well as some elements of proof that explain its structure.