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.

Improve this question
$\endgroup$
7
  • $\begingroup$ what do you mean by $k$-partite? $\endgroup$
    – Fedor Petrov
    Commented Jul 5, 2017 at 19:47
  • $\begingroup$ @FedorPetrov $k$-colorable en.wikipedia.org/wiki/Multipartite_graph. $\endgroup$
    – Turbo
    Commented Jul 5, 2017 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
    Commented Jul 6, 2017 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
    Commented Jul 6, 2017 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
    Commented Jul 6, 2017 at 10:31

2 Answers 2

Reset to default
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.$$

Improve this answer
$\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
    Commented Apr 22, 2021 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
    Commented Apr 27, 2021 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
    Commented Apr 27, 2021 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$
    – David E Speyer
    Commented Apr 27, 2021 at 22:26
  • $\begingroup$ By comparison, $(4!)^{1/8} \approx 1.488$. $\endgroup$
    – David E Speyer
    Commented Apr 27, 2021 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.

Improve this answer
$\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
    Commented Jul 6, 2017 at 10:40
  • 2
    $\begingroup$ @Jon Noel: Earlier versions of the question asked for lower bounds, too. $\endgroup$
    – Douglas Zare
    Commented Jul 7, 2017 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
    Commented Jul 7, 2017 at 21:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .