European J. Combin., t. 33, p. 199-214, 2012.
Bodo Lass
The Algebra of Set Functions II : An Enumerative Analogue of Hall's Theorem for Bipartite Graphs
Abstract.
Triesch conjectured that Hall's classical theorem on matchings in bipartite graphs
is a special case of a phenomenon of monotonicity for the number of matchings in such graphs.
We prove this conjecture for all graphs with sufficiently many edges by deriving an explicit
monotonic formula counting matchings in bipartite graphs.
This formula follows from a general duality theory which we develop for counting matchings.
Moreover, we make use of generating functions for set functions as introduced in
The Algebra of Set Functions I : Product Theorem and Duality,
and we show how they are useful for counting matchings in bipartite graphs in many different ways.
Les versions suivantes sont disponibles :
Version du journal :