MARK KAC SEMINAR

For a given graphical degree sequence, there is typically a large number of simple graphs that satisfy it. We will consider the problem of uniformly sampling a graph from this set. This can also be viewed as a model for a random graph, i.e. a graph-valued random variable. In general, algorithms that realise such sampling have exponential complexity, but there are special classes of graphs where the complexity is less severe and could even be linear. In this talk, we will discuss several of such classes called sparse graphs and show that their uniform generation can be achieved in linear time using the so called sequential construction — non-uniformly placing one edge at a time in the course of m steps while updating the probabilities after each step. In the second part of the talk we will discuss the underlying random graph model and show that it gives rise to solutions of interesting nonlinear partial differential equations and can even be regarded as a method for solving such equations formally.

In this talk we consider random graph models with both spatial information (random geometric graphs) and a prescribed degree sequence (configuration model). When these constraints are considered separately, the random graph models are well understood. However, when imposed together, conflicts arise.

In the first part of this talk, we will consider an algorithm for sampling random graphs with spatial and degree constraints. In particular, we will consider a target degree sequence d_n and edge-length distribution f_n. Provided that d_n is bounded uniformly and f_n is not too large compared to the empirical distribution of the available edge-lengths, we will show that our algorithm randomly produces a graph with degree sequence dn and empirical edge-length distribution close to f_n.

In the second part, we will look into the emergence of a giant component in these random graph models. We make a first step into this direction by considering a d-dimensional torus partitioned into compartments forming a cubic lattice. We distribute vertices equally over these compartments, and only allow local edges inside compartments and between neighbouring compartments. We assume the number of compartments diverges when the number of vertices grows. Using connections with multitype branching processes, we will prove that if the num- ber of vertices per compartment grows quickly enough, then a giant component emerges under similar conditions on the degree sequence as for the standard configuration model.

All is based on work together with Ivan Kryven. The first part is based on [KV22], while the second part is based on [KV21].

[KV21] Ivan Kryven and Rik Versendaal. “Giant component in the configu- ration model under geometric constraints”. In: ArXiv preprint (2021). url: https://arxiv.org/abs/2108.04112.

[KV22] Ivan Kryven and Rik Versendaal. “Sequential construction of spatial networks with arbitrary degree sequence and edge length distribution”. In: ArXiv preprint (2022). url: https : / / arxiv . org / abs / 2207 . 08527.