SeMINAR

## TUESDAY 22nD November 2022

**15:00-15:50**

Serte Donderwinkel (McGillUniversity)

Enumerating graphic sequences

A graphic sequence is a non-increasing sequence of natural numbers that can occur as the degree sequence of a graph. We show that the number of graphic sequence of length n grows like cn^{-3/4}4^n for some constant c. The foundation of our proof consists of a few reformulations, that turn our problem into a question about the lazy simple symmetric random walk bridge. To be precise, we calculate the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge never goes negative. Our reformulation also yields a new, efficient algorithm for exact enumeration of graphic sequences, with which we are able to calculate many more exact values than previously known. This talk is based on joint work with Paul Balister, Carla Groenland, Tom Johnston and Alex Scott.

## Wednesday 24th November 2021

**15:00-16:00**

Roberto Imbuzeiro Oliveira (IMPA)

The contact process over a switching random d-regular graph

## Wednesday 27th OCTOBER 2021

**14:00-15:00**

Martin Balko (Charles University in Prague)

On the expected number of holes in random point sets

## Wednesday 29th September 2021

**16:00-17:00**

Louigi Addario-Berry (McGill)

Height bounds for random trees

## Wednesday 30th JuNE 2021

**15:00-15:50**

Maya Stein (Universidad de Chile)

Monochromatic partitions of graphs and random graphs

Given a graph G whose edges are colored with r colours, how many monochromatic trees, paths or cycles do we need to cover all the vertices of G? This type of question goes back to the 1960’s and was first studied for the case of G being a complete graph. Modern variants replace the complete graph G with a graph of high minimum degree, or a complete bipartite graph, or a random graph, or other types of graphs. I will give a survey on known results and open questions in the area, with the main focus on trees and paths.

**16:10-17:00**

James Martin (Oxford)

Games on random graphs, on Bienaymé trees, and on percolation clusters.

## Wednesday 26th May 2021

**15:00-15:50**

Lutz Warnke (GATECH)

The Density of Costas Arrays Decays Exponentially

## Wednesday 28th April 2021

**16:10-17:00**

Rui M. Castro (TU/e-Eindhoven)

Detecting a planted community in an inhomogeneous random graph

## Wednesday 24th March 2021

**15:00-15:50**

Benedikt Stufler (TUWien, Vienna)

Random planar graphs - results and conjectures

**16:10-17:00**

Eric Fusy (LIX-Polytechnique)

Maps of unfixed genus and blossoming trees

This is joint work with Emmanuel Guitter.

## Wednesday 24th February 2021

**15:00-15:50**

Gábor Lugosi (UPF, Barcelona)

Network archeology: a few results and many questions

**16:10-17:00**

Élie de Panafieu (Nokia/Bell Labs, Paris)

The design of algorithms for the production of training data