Skip to main content
6 of 7
added 6 characters in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

On number of perfect matchings

Consider $2n$ vertex balanced bipartite graph.

If total number of edges is $n^2$ then we have $n!$ perfect matchings.

Fix $c\in(0,\frac12)$ and consider collection of $2n$ vertex balanced bipartite graphs with at least $cn!$ perfect matchings. What fraction of graphs in this collection have at most $dn^2$ total number of edges in it for some fixed $d\in(0,\frac12)$?

Is there a positive portion of such graphs (if $c\in(0,\frac12)$ can a positive proportion of graphs have $d\in(0,\frac12)$)?

Turbo
  • 13.9k
  • 1
  • 27
  • 76