Events in MathSys and Complexity Science
This is a calendar page detailing events within the MathSys CDT. It also acts as a booking diary for the Seminar Room D1.07. To book D1.07 please email Sheetal.Sharma@warwick.ac.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.
MathSys CDT events have priority for D1.07 room bookings.
Click here to see all seminars taking place in the Mathematics InstituteLink opens in a new window
Click here to see the calendar for SBIDERLink opens in a new window.
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