Mathematics – Combinatorics
Scientific paper
2011-12-23
Mathematics
Combinatorics
15 pages, 3 figures
Scientific paper
This survey paper deals with upper and lower bounds on the number of $k$-matchings in regular graphs on $N$ vertices. For the upper bounds we recall the upper matching conjecture which is known to hold for perfect matchings. For the lower bounds we first survey the known results for bipartite graphs, and their continuous versions as the van der Waerden and Tverberg permanent conjectures and its variants. We then discuss non-bipartite graphs. Little is known beyond the recent proof of the Lov\'asz-Plummer conjecture on the exponential growth of perfect matchings in cubic bridgeless graphs. We discuss the problem of the minimum of haffnians on the convex set of matrices, whose extreme points are the adjacency matrices of subgraphs of the complete graph corresponding to perfect matchings. We also consider infinite regular graphs. The analog of $k$-matching is the $p$-monomer entropy, where $p\in [0,1]$ is the density of the number of matchings.
No associations
LandOfFree
Results and open problems in matchings in regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Results and open problems in matchings in regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Results and open problems in matchings in regular graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-193108