Enumerating Bipartite Graphs With Degree Constraints

Speaker : Emma Caizergues
Nokia Bell Labs France
Date: 15/06/2022
Time: 11:00 am - 12:00 pm
Location: Telecom Paristech

Abstract

Enumerating graphs with a given degree sequence is a problem of interest in many fields such as voting theory and statistics. If we are able to give nice asymptotic formulas [1], there does not exist an exact formula that is feasible to compute. Even though asymptotics already provides sufficient information for most applications, some require an exact enumeration. In this presentation, we will enumerate bipartite graphs with degree constraints using a special combinatorial technique. This will be the occasion to make an introduction to some classical combinatorial tools such as generating functions [2].

[1] Asymptotic enumeration of digraphs and bipartite graphs by degree sequence, A Liebenau, N Wormald, 2020
[2] Analytic combinatorics, P Flajolet, R Sedgewick, 2009