Talks
Spring 2019

Counting Degree-constrained Subgraphs and Orientations

Tuesday, March 19th, 2019, 10:30 am11:15 am

Add to Calendar

Speaker: 

Péter Csikvári (Eötvös Loránd University)

In this talk we introduce and study a partition function that counts degree-constrained subgraphs of a finite graph. In particular, our partition function generalizes the matching polynomial. Surprisingly, it is also possible to count degree-constrained orientations with the same partition function. In particular, we give a short proof to a theorem of A. Schrijver concerning a lower bound on the number of Eulerian orientations of a graph with only even degrees. We will discuss some applications to matchings too. This is joint work with Márton Borbényi.