Counting perfect matchings with superposed directed cycles
by
Robert W. Robinson
University of Georgia

Maps on orientable surfaces, Feynman diagrams, and cycle decompositions of 2-regular digraphs can all be counted in a natural way when viewed as superpositions (edge-disjoint unions) of a perfect matching on a vertex set V with a vertex-disjoint union of directed cycles which span V.

In a Feynman diagram each matching edge corresponds to an interaction and each directed edge to a fermion moving between interactions. What is of interest for calculating the single particle self-energy in a system of fermions are the diagrams which are connected and rooted at a distinguished edge. They can be counted by numbers of vertices and directed cycles.

The standard combinatorial representation of a map on an orientable surface is obtained from a connected Feynman diagram by contracting the directed cycles while maintaining the cyclic order of the incident matching edge ends. What can be counted in this way are rooted or unrooted maps of all genera by numbers of vertices and edges.

A cycle decomposition of a labeled 2-regular digraph is obtained from a Feynman diagram by contracting the edges of the matching. This leads to formulae for counting labeled 2-regular digraphs by number of vertices.

Date received: April 18, 2008