# Maximum number of perfect matchings in a planar graph?

What is the maximum number of perfect matchings a planar $k$-partite $|V|$ number of vertices simple graph can have where $k=2,3,4$ ($k>4$ is impossible for a planar graph)?

Since number of matchings cannot exceed $2^{\alpha_k |V|}$ where $\alpha_k>0$ is an absolute constant that depends only on $k$ in essence 'what is the best estimate of $\alpha_k$?' is the query.

• what do you mean by $k$-partite? – Fedor Petrov Jul 5 '17 at 19:47
• @FedorPetrov $k$-colorable en.wikipedia.org/wiki/Multipartite_graph. – Turbo Jul 5 '17 at 19:48
• math.stackexchange.com/questions/2347062/… The answer there doesn't seem close to sharp but please post links both ways if you cross-post. – Douglas Zare Jul 6 '17 at 0:30
• Every planar graph is $4$-colourable. So, I guess that $k\in\{2,3,4\}$ in your question? For the case $k=2$, your question precisely asks for the maximum number of perfect matchings in a bipartite planar graph, and so I think that @DouglasZare 's comment is quite relevant. – Jon Noel Jul 6 '17 at 10:15
• I guess that my point is that $\alpha_k = \alpha_4$ for all $k\geq5$. So you are truly only asking for $\alpha_2,\alpha_3$ and $\alpha_4$. Right? – Jon Noel Jul 6 '17 at 10:31

An old conjecture of Lovász and Plummer is that for every cubic graph $G$ with no cut-edge, the number of perfect matchings in $G$ is exponential in the number of vertices. Chudnovsky and Seymour proved that the conjecture holds for all planar graphs.

That is, every $n$-vertex, cubic, planar graph with no cut-edge has at least $2^{n/655978752}$ perfect matchings.

Note that the full Lovász-Plummer Conjecture has since been proved by Esperet, Kardo?, King, Král, and Norine.

• The Lovasz-Plummer Conjecture relates to the minimum number of perfect matchings. @Turbo is asking about the maximum number of perfect matchings. – Jon Noel Jul 6 '17 at 10:40
• @Jon Noel: Earlier versions of the question asked for lower bounds, too. – Douglas Zare Jul 7 '17 at 15:45
• Yes, but earlier versions asked for lower bounds on the maximum number of perfect matchings. So, it was asking for a family of planar graphs having a large number of perfect matchings. Chudnovsky-Seymour gives a lower bound on the minimum number of perfect matchings in a cubic planar graph. That doesn't seem super relevant here, despite being an interesting and important result. (to get a way better lower bound than $2^{n/655978752}$, you can take $n/4$ disjoint $4$-cycles, for example). – Jon Noel Jul 7 '17 at 21:33

In order to get an upper bound on $\alpha_4$ (which is probably far from being a tight bound), you can use the Kahn-Lovász Theorem (a generalisation of Brégman's Theorem). The Kahn-Lovász Theorem says that the number of perfect matchings in any graph $G$ is at most $$\prod_{v\in V(G)}(d(v)!)^{1/2d(v)}.$$ Its not immediately clear to me how to obtain an upper bound of the form $2^{c|V(G)|}$ from this, but it looks like it might be possible since planar graphs have at most $3|V(G)|-6$ edges (and therefore the sum of the vertex degrees is at most linear in $|V(G)|$).

Like I said, this is unlikely to be tight, but at least it might give you a bound. The Kahn-Lovász Theorem is tight for general graphs, but I think that the unique tight example is a disjoint union of balanced complete bipartite graphs, which is not planar unless every component is isomorphic to $K_2$ or $K_{2,2}$.