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