Counting Graphs with a Given Degree Sequence: An Information-theoretic Perspective

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

Full description

Saved in:
Bibliographic Details
Main Authors: Ioushua, Shahar Stein, Shayevitz, Ofer
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Electrocardiography
Entropy
History
Information theory
Systematics
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2157-8117
DOI:10.1109/ISIT.2019.8849579