1
$\begingroup$

What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am particularly interested in $k=2$.

For planar balanced bipartite graphs (each color has to have same number of vertices assigned) the number of perfect matchings is $2^{O(n)}$ while for genus $\Omega(n^2)$ we can have $2^{\Omega(n\log n)}$. So is maximum number of perfect matchings $2^{O(n\log g)}$ for $k=2$?

Improve this question
$\endgroup$
13
  • $\begingroup$ genus alone is not a big obstacle, it appears. e.g. fullerens (particular kind of planar graphs) can have exponentially many perfect matchings : arxiv.org/abs/0801.1438 $\endgroup$
    – Dima Pasechnik
    Commented May 28, 2019 at 7:03
  • $\begingroup$ @DimaPasechnik You dont get the point. Balanced bipartite graphs can have $2^{\Omega(n\log n)}$ perfect matchings however genus needs to be high and if you have planarity you are constrained by $2^{O(n)}$ perfect matchings. $\endgroup$
    – Turbo
    Commented May 28, 2019 at 7:08
  • $\begingroup$ planar 4-gonal $2k\times 2k$ grids can have exponentially many perfect matchnigs, too - one covers such a grid by $2\times 2$ squares, each containing a 4-gon, so you can switch each of them in 2 different ways. $\endgroup$
    – Dima Pasechnik
    Commented May 28, 2019 at 7:09
  • 1
    $\begingroup$ Forgot the reference but check mathoverflow.net/questions/273765/…. $\endgroup$
    – Turbo
    Commented May 28, 2019 at 7:22
  • 1
    $\begingroup$ The (bipartite) hypercube on $N=2^n$ vertices has genus $1+(n-4)2^{n-3} \approx C N \log(N)$, and it has roughly $2^{c N \log(\log(N))}$ perfect matchings. So there’s something with not huge genus having superexponentialy many perfect matchings. $\endgroup$
    – Pat Devlin
    Commented May 29, 2019 at 1:59

1 Answer 1

Reset to default
1
$\begingroup$

Yes, but not for a great reason.

Fact: genus of a graph is bounded below by $|E|/6 - n/2+1$.

Case 1: suppose $|E| \leq 10 n$. Then the number of perfect matchings is at most ${ {|E|} \choose {n/2}} \leq 2^{|E|} \leq 2^{10n}.$

Case 2: suppose $|E| \geq 10n$ so that (by fact) the genus satisfies $g \geq n$. We know every graph has at most $2^{O(n \log(n))}$ perfect matchings, and we’re done since $g\geq n$.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Yes... If $g=\log(n)$, then there are at most $10n$ edges, so at most $2^{10n}$ perfect matchings [see case 1]. $\endgroup$
    – Pat Devlin
    Commented May 29, 2019 at 15:38
  • $\begingroup$ Great. In which case the genus is greater than $n$ [see case 2]. $\endgroup$
    – Pat Devlin
    Commented May 29, 2019 at 15:40
  • $\begingroup$ Are you hoping for a construction or a lower bound? If the genus is too small, there are not many edges at all (at most linearly many). And if there are only $cn$ edges, the number of perfect matchings is at most $2^{cn}$, which is in fact less than $2^{cn \log(g)}$. This is a better upper bound than what you were hoping for. So there is no lower bound matching the upper bound hoped for in OP. $\endgroup$
    – Pat Devlin
    Commented May 29, 2019 at 15:47
  • 1
    $\begingroup$ (Commenting on “all or nothing” comment) Yea. Seems like it. The upper bounds of $2^{E}$ and $n!$ are always smaller than $2^{n \log(g)}$. I think one of the morals here is that “logs and tolerable multiplicative factors in the exponent cover a multitude of sin.” $\endgroup$
    – Pat Devlin
    Commented May 29, 2019 at 16:16
  • 1
    $\begingroup$ Page $18$ cs.columbia.edu/~cs6204/files/Lec2-Min&MaxGenus.pdf refers. $\endgroup$
    – Turbo
    Commented May 29, 2019 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.