SeMINAR

We run a monthly seminar. All the indicated times are in the CET time zone. If you would like to receive email updates, please contact Guillem Perarnau at guillem.perarnau@upc.edu.

TUESDAY 22nD November 2022

Google Meet link   

Wonder room

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

Zoom link: https://us02web.zoom.us/j/87332597754?pwd=amlhS0dVdTRHN1ArSjJUbWVRRjVaZz09

Video

15:00-16:00


Roberto Imbuzeiro Oliveira (IMPA)


The contact process over a switching random d-regular graph


The contact process is a crude model for the spread of an epidemic in a graph. In this model, each “sick” vertex spreads the infection to a neighboring vertex at rate lambda>0 and becomes healthy at rate 1. This model undergoes a “metastability transition” over certain large finite graphs. For instance, in a large random d-regular graph with d>2 and n>>1 vertices, if all vertices are initially "sick”, there exists a lambda_c such that the epidemic dies out in log n time when lambda<lambda_c, and survives for exp(Cn) time when lambda>lambda_c. This behavior is related to the phase transition of the model over the infinite d-regular tree, which provides a “local model” for the random d-regular graph. 

This talk discusses what happens to the contact process over a time-evolving random graph. Specifically, we assume we have a dynamic graph evolving according to the “edge switching” Markov chain over d-regular graphs on n vertices. Assuming each edge changes at rate v>0, we show that exponential survival time still holds for lambda> lambda_c(v); however, the new critical parameter lambda_c(v) is strictly smaller than that of the static graph. At the heart of our proof is a “local model” for our process – that is, a contact process over a growing family of trees – that is of independent interest. 

This is joint work with Gabriel Leite Baptista da Silva and Daniel Valesin (who are both at Groningen).

Wednesday 27th OCTOBER 2021

Zoom link: https://us02web.zoom.us/j/87332597754?pwd=amlhS0dVdTRHN1ArSjJUbWVRRjVaZz09

14:00-15:00


Martin Balko (Charles University in Prague)


On the expected number of holes in random point sets


For a positive integer d, let S be a finite set of points in R^d with no d+1 points on a common hyperplane. A set H of k points from S is a k-hole in S if all points from H lie on the boundary of the convex hull conv(H) of H and the interior of conv(H) does not contain any point from S. 

We study the expected number of holes in sets of n points drawn uniformly and independently at random from a convex body of unit volume. We provide several new bounds and show that they are tight. In many cases, we are even able to determine the leading constants precisely, improving several previous results. 

 This is based on two joint works with Pavel Valtr and Manfred Scheucher.

Wednesday 29th September 2021

Zoom link: https://us02web.zoom.us/j/87332597754?pwd=amlhS0dVdTRHN1ArSjJUbWVRRjVaZz09

Video Slides

16:00-17:00


Louigi Addario-Berry (McGill)


Height bounds for random trees


I will present new, non-asymptotic bounds on the heights of random combinatorial trees and conditioned Bienaymé trees, as well as stochastic inequalities relating the heights of combinatorial trees with different degree sequences. The tool for most of the proofs is a new approach to coding rooted trees by sequences, based on a new proof of Cayley's formula.

Joint work with Serte Donderwinkel, Mickaël Maazoun and James Martin.

Wednesday 30th JuNE 2021

Zoom link: https://us02web.zoom.us/j/87332597754?pwd=amlhS0dVdTRHN1ArSjJUbWVRRjVaZz09

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.


Puzzle: let G be a finite graph and v any vertex. Consider the following two-player combinatorial game. A token starts at v. The players take turns to move, and each move of the game consists of moving the token along an edge of G, to a vertex that has not been visited before. A player who is unable to move loses the game. When does the first player have a winning strategy? 

I'll discuss various models with a related flavour, where the underlying graph is the tree of a Bienaymé(-Galton-Watson) branching process, a random graph drawn from the configuration model, or a cluster of directed or undirected percolation on Z^d. Themes arising include maximum-size matchings, the hard-core model, and endogeny for recursive distributional equations. 

 (Joint work with several co-authors including Roman Stasiński, Alexander Holroyd, Irène Marcovici, Riddhipratim Basu, and Johan Wästlund)

Wednesday 26th May 2021

Zoom link: https://us02web.zoom.us/j/87332597754?pwd=amlhS0dVdTRHN1ArSjJUbWVRRjVaZz09

15:00-15:50


Lutz Warnke (GATECH)


The Density of Costas Arrays Decays Exponentially


Costas arrays arise in radar and sonar engineering: formally they are simply permutation matrices with the extra property that vectors joining pairs of ones are all distinct. In this talk we shall use ideas from random graph theory to prove that the density of Costas arrays among permutation matrices decays exponentially, solving a core theoretical problem for Costas arrays. We shall also discuss related open problems at the intersection of combinatorics, probability and enumeration that might be suitable for RandNET collaborations.
Based on joint work in progress with B. Correll and C. Swanson.

Wednesday 28th April 2021

Zoom link: https://us02web.zoom.us/j/87332597754?pwd=amlhS0dVdTRHN1ArSjJUbWVRRjVaZz09

16:10-17:00


Rui M. Castro (TU/e-Eindhoven)


Detecting a planted community in an inhomogeneous random graph


In this talk we address the problem of detecting whether an inhomogeneous random graph contains a planted community. In the last decades a substantial amount of work has been focussed on extracting relatively large-sized communities from networks. In contrast, the focus of our work is somewhat different, and the goal is to understand when it is possible to successfully detect the presence of small communities in a large graph. We cast the problem as a binary hypothesis test. Specifically, we observe a single realization of a graph. Under the null hypothesis, this graph is a sample from an inhomogeneous random graph, whereas under the alternative hypothesis, there exists a small subgraph where the edge probabilities are increased by a multiplicative scaling factor. The homogeneous setting (where the null hypothesis corresponds to a Erdös-Rényi graph) has been characterized in works of Arias-Castro and Verzelen. Our focus is to understand what can be said when the null-model is inhomogeneous, and how inhomogeneity affects the detection boundary. We develop a scan-type test and provide conditions under which it is able to detect the presence of small planted community. Furthermore, we present information-theoretical lower bounds showing that, in many regimes, the proposed scan test is essentially asymptotically optimal. 
Based on joint work with Kay Bogerd, Remco van der Hofstad and Nicolas Verzelen - https://arxiv.org/abs/1909.03217

Wednesday 24th March 2021

Zoom link: https://us02web.zoom.us/j/87332597754?pwd=amlhS0dVdTRHN1ArSjJUbWVRRjVaZz09

15:00-15:50


Benedikt Stufler (TUWien, Vienna)


Random planar graphs - results and conjectures


The study of random combinatorial structures and their limits is a growing field at the interface of combinatorics, probability theory, and mathematical physics. Planar graphs are a prominent example of such structures, yet important problems concerning their asymptotic shape remain open. This talk highlights open conjectures and reviews recent results, in particular the discovery of a Uniform Infinite Planar Graph (UIPG) as their quenched local limit.

16:10-17:00


Eric Fusy (LIX-Polytechnique)


Maps of unfixed genus and blossoming trees


Bijective enumeration of 4-regular planar maps can be done via two different constructions both due to Schaeffer, one with so-called blossoming trees and the other one (in the dual setting) with so-called well-labeled trees. A great success of these constructions has been to give access to metric properties of random quadrangulations, and to show that the radius and typical distances are in the scale of n^{1/4} (Chassaing-Schaeffer, Le Gall, Miermont). In terms of generating functions, as shown by Bouttier, Di Francesco and Guitter, these bijections ensure that the so-called 2-point function R_i(g) of 4-regular planar maps (generating function of 4-regular maps with two points at dual distance smaller than i) are related by the recurrence R_i(g)=1+R_i(g)*(R_{i-1}(g)+R_i(g)+R_{i+1}(g)) (with boundary condition R_0(g)=0) which remarkably can be solved explicitly. 
I will show how the construction based on blossoming trees can be extended to 4-regular maps of unfixed genus. This provides a bijective proof of the fact that the corresponding counting series is expressed as the first term r_1(g) of a sequence of series (r_i(g))_{i>0} that are now related by the recurrence r_i(g)=i+r_i(g)*(r_{i-1}(g)+r_i(g)+r_{i+1}(g)), with boundary condition r_0(g)=0 (this is the same recurrence as for the R_i(g), except for the constant term i instead of 1), an expression that had previously been obtained via the configuration model and matrix integrals. Our construction also contains the one for 4-regular planar maps, and it explains the similarity between the series expressions for the planar case and the unfixed genus case. 
This is joint work with Emmanuel Guitter.


Wednesday 24th February 2021

Zoom link: https://us02web.zoom.us/j/87332597754?pwd=amlhS0dVdTRHN1ArSjJUbWVRRjVaZz09

Slides Gábor / Slides Élie / Video

15:00-15:50


Gábor Lugosi (UPF, Barcelona)


Network archeology: a few results and many questions


Networks are often naturally modeled by random processes in which nodes and edges of the network are added one-by-one, according to some simple stochastic dynamics. Uniform and preferential attachment processes are prime examples of such dynamically growing networks. The statistical problems we address in this talk regard discovering the past of the network when a present-day snapshot is observed. Such problems are sometimes termed "network archeology". We present a few results that show that, even in gigantic networks, a lot of information is preserved from the very early days. As the field is still in its infancy, many interesting questions remain to be explored.

16:10-17:00


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


The design of algorithms for the production of training data


There is a well-known saying in the supervised machine learning community: "garbage in, garbage out". The performance of a supervised learning algorithm depends critically on the quantity and quality of training data. This training data is obtained from raw data through data labeling performed by human experts. The growing use of machine learning tools makes the design of efficient data labeling algorithms more relevant than ever. 

I will present progress made by Maya Stein, Quentin Lutz and I on a problem proposed by Nokia engineer Maria Laura Maag. It corresponds to the reconstruction of a set partition using as few queries as possible, each query asking whether two elements belong to the same block. We have obtained a partial proof and numerical confirmations for an interesting conjecture characterizing the optimal algorithms, as well as the analysis of the optimal distribution of the query numbers.