5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what do you mean by $k$-partite? $\endgroup$ – Fedor Petrov Jul 5 '17 at 19:47
  • $\begingroup$ @FedorPetrov $k$-colorable en.wikipedia.org/wiki/Multipartite_graph. $\endgroup$ – T.... Jul 5 '17 at 19:48
  • 3
    $\begingroup$ math.stackexchange.com/questions/2347062/… The answer there doesn't seem close to sharp but please post links both ways if you cross-post. $\endgroup$ – Douglas Zare Jul 6 '17 at 0:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Jon Noel Jul 6 '17 at 10:15
  • 1
    $\begingroup$ 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? $\endgroup$ – Jon Noel Jul 6 '17 at 10:31
6
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ The Lovasz-Plummer Conjecture relates to the minimum number of perfect matchings. @Turbo is asking about the maximum number of perfect matchings. $\endgroup$ – Jon Noel Jul 6 '17 at 10:40
  • 2
    $\begingroup$ @Jon Noel: Earlier versions of the question asked for lower bounds, too. $\endgroup$ – Douglas Zare Jul 7 '17 at 15:45
  • 2
    $\begingroup$ 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). $\endgroup$ – Jon Noel Jul 7 '17 at 21:33
5
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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