- This event has passed.

# Eindhoven SPOR Seminar

## May 17, 15:45 - 16:45

**Rik Versendaal (UU) **

**Sampling simple random graphs under degree and edge-weight constraints**

In [1], the problem was studied of sampling simple random graphs with degree constraints, which is typically a hard problem. Therefore, the authors proposed a sequential algorithm that samples such graphs asymptotically uniformly at random, when the number n of vertices tends to infinity.

In this talk, we will extend the algorithm in [1] to also include edge-weights. More specifically, we first assign random weights to all edges according to some probability distribution and consider some target edge-weight distribution . We then aim to sample random graphs satisfying some prescribed degree sequence, while additionally having empirical edge-weight distribution close to the target distribution . We make this statement precise by proving that with high probability the empirical edge-weight distribution of the random graph produced by our algorithm is close to in Wasserstein distance. The key assumption for this is that the target edge-weight distribution is not too large compared to the distribution of the edge-weights, i.e., for some constant . This constant is allowed to grow moderately with , being for some . The proof of this result mainly relies on a variety of concentration inequalities.

Finally, we will discuss what happens in the boundary case where This for example occurs when studying graphs under geometric constraints in the box , where the connection threshold is in the critical regime, i.e., of order .

This seminar will be hosted in a **hybrid** fashion; you are welcome to attend the talk either on-campus or via Zoom. The on-campus location will be announced later. The Zoom link is attached to the bottom of the invitation text.

For upcoming events of the SPOR seminar, as well as a history of previous talks, see: https://www.eurandom.tue.nl/eindhoven-spor-seminar/. Recordings of earlier talks are available upon request.