Loading Events

« All Events

  • 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.


May 17
15:45 - 16:45
Event Category:


MF 11-12 (4th floor MetaForum Building, TU/e)