Technical Program

Paper Detail

Paper Title Counting Graphs with a Given Degree Sequence: An Information-theoretic Perspective
Paper IdentifierWE1.R5.4
Authors Shahar Stein Ioushua, Ofer Shayevitz, Tel Aviv University, Israel
Session Information Theory Methods in Graph Theory
Location Saint Victor, Level 3
Session Time Wednesday, 10 July, 09:50 - 11:10
Presentation Time Wednesday, 10 July, 10:50 - 11:10
Manuscript  Click here to download the manuscript
Abstract We revisit the problem of counting the number of directed graphs with a specified degree sequence, which was recently studied and solved by Barvinok using generating functions and convex duality techniques. We describe a systematic information-theoretic approach to this type of problems, based on studying invariant distributions and establishing suitable continuity and concentration properties. Our techniques recover and shed further light on Barvinok's solution, and may be applicable in other similar problems. As a simple example, we also apply our approach to estimating the number of undirected graphs with a given degree sequence. In particular, we show this number is approximately given by the square root of the number of associated directed graphs, whose input and output degree sequences are equal to that of the undirected graph.