糖心TV Complexity Science Events
Complexity Centre and MathSys CDT events carry priority over room D1.07.
To book D1.07 please email Sheetal dot Sharma at warwick dot ac dot uk
Please note that your event booking is for D1.07 only. The adjacent common room is a private area for the MathSys Centre that cannot used as part of your booking.
Complexity Forum: P. Erdős (Alfréd Rényi Institute of Mathematics)
Speaker: P. Erdős (Alfréd Rényi Institute of Mathematics)
Title: Constructing, sampling and counting graphical realizations of restricted degree sequences
Abstract:
With the current burst of network theory research (especially in connection with social and biological networks) there is a renewed interest on realizations of given degree sequences and uniform sampling of them. In this paper we propose a new degree sequence problem: we want to find graphical realizations of a given degree sequence on labeled vertices, where certain would-be edges are forbidden. Then we want to sample uniformly all possible realizations.
In this paper, as a first step, we solve this restricted degree sequence (RDS for short) problem for half-regular bipartite graphs, where the forbidden edges form the union of a (not necessarily maximal) 1-factor and a (possible empty) star. Our result contains, as special cases, the well-known result of Kannan, Tetali and Vempala on sampling regular bipartite graphs and a recent result of Greenhill on sampling regular directed graphs (so it also provides new proofs for them).
Since the RDS problem with one forbidden 1-factor and one star is self-reducible, therefore our fully polynomial almost uniform sampler (a.k.a. FPAUS) on the space of all realizations also provides a fully polynomial randomized approximation scheme (a.k.a. FPRAS) for approximate counting of all realizations.
Lunch group: 1