8
$\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$
7
  • $\begingroup$ what do you mean by $k$-partite? $\endgroup$ Jul 5 '17 at 19:47
  • $\begingroup$ @FedorPetrov $k$-colorable en.wikipedia.org/wiki/Multipartite_graph. $\endgroup$
    – Turbo
    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$ 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
9
$\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)|$). See the edit below.

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

Edit: If the sum of the degrees is fixed, then the product in the upper bound here is maximized when all of the degrees are as similar as possible. This can be derived, e.g., from Karamata's Inequality. In a planar graph, the average degree is at most $6$. So, the number of perfect matchings is bounded above by $$(6!)^{n/12} = (1.73026\dots)^n.$$

$\endgroup$
8
  • 2
    $\begingroup$ Any planar graph has a vertex of degree at most 5, so by induction you get the upper bound $5^{n/2}$ without any complicated theorems. $\endgroup$
    – domotorp
    Apr 22 '21 at 12:55
  • $\begingroup$ Good point! Out of interest, I've updated my answer with the precise upper bound it gives, which is a bit better than $5^{n/2}$. But yeah, your argument is simpler. $\endgroup$
    – Jon Noel
    Apr 27 '21 at 20:42
  • $\begingroup$ Do you know the number of perfect matchings of a large triangular grid (the simplest example of a planar graph where almost every vertex has degree $6$)? $\endgroup$
    – Will Sawin
    Apr 27 '21 at 20:59
  • 1
    $\begingroup$ @WillSawin I know how to compute it, and am planning to work it out tonight. The analogous computation for a rectangular square grid with $N$ vertices (simplest bipartite graph where almost every degree is $4$) is $\exp(N G/\pi)$ where $G = 1-1/3^2+1/5^2-1/7^2+\cdots$, or about $1.339^N$. See, for example, arxiv.org/abs/math/0008220 $\endgroup$ Apr 27 '21 at 22:26
  • $\begingroup$ By comparison, $(4!)^{1/8} \approx 1.488$. $\endgroup$ Apr 27 '21 at 22:27
8
$\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
  • 4
    $\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$ 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

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.