Skip to main content

Section 7.3 Permanents and Counting Perfect Matchings

Recall that a perfect matching in a graph \(G\) is a set \(M\subseteq E(G)\) of edges such that every vertex is contained in exactly one edge of \(M\text{.}\) The question that we address here is: how many perfect matchings can a graph with a given degree sequence have? The following example is similar to the key example in Section 6.2.

Example 7.3.1.

Let \(d_1,\dots,d_k\) be positive integers and let \(G\) be a disjoint union of complete bipartite graphs \(K_{d_i,d_i}\) for \(1\leq i\leq k\text{.}\) The number of perfect matchings in \(K_{d_i,d_i}\) is precisely \(d_i!\) and so the number in \(G\) is
\begin{equation*} \prod_{i=1}^kd_i!\text{.} \end{equation*}
Let \((A,B)\) be the bipartition of \(G\text{.}\) Then, in the \(i\)th component of \(G\text{,}\) there are \(d_i\) vertices of \(A\text{,}\) each of degree \(d(v)\text{.}\) Another way to express this number is as follows. Then the number of perfect matchings in \(G\) is precisely
\begin{equation*} \prod_{v\in A}(d(v)!)^{1/d(v)} \end{equation*}
or
\begin{equation*} \prod_{v\in V(G)}(d(v)!)^{1/(2d(v))}\text{.} \end{equation*}
These may seem like weird ways of writing things, but this will be convenient for comparing this example to the bounds that we will prove below.
Given a graph \(G\text{,}\) let \(\permat(G)\) be number of perfect matchings in \(G\text{.}\) Our goal will be to show that the bound in Example 7.3.1 is actually tight. The special case of bipartite \(G\) is particularly interesting. The proof combines some of the facts that we have learned about entropy in the previous section.

Proof.

Let \(G\) be a bipartite graph with bipartition \((A,B)\text{.}\) Let \(M\) be a perfect matching in \(G\) chosen uniformly at random from the set of all perfect matchings. Then, by Lemma 7.1.4, we have that the entropy of \(M\) is equal to the logarithm of the cardinality of its range. Therefore,
\begin{equation*} \mathbb{H}(M) = \log_2(\permat(G))\text{.} \end{equation*}
So, proving an upper bound on \(\permat(G)\) is equivalent to proving an upper bound on \(\mathbb{H}(M)\text{;}\) we focus on the latter.
For each \(v\in A\text{,}\) let \(X_v\) be equal to the vertex \(u\in B\) such that \(vu\in M\text{.}\) Note that the joint random variable
\begin{equation*} X=(X_v: v\in A) \end{equation*}
is equivalent to \(M\text{;}\) that is, \(X\) is determined by \(M\) and \(M\) is determined by \(X\) as well. Therefore, \(\mathbb{H}(X)=\mathbb{H}(M)=\log_2(\permat(G))\) and we can focus on bounding the entropy of \(X\text{.}\) For each \(u\in B\text{,}\) we can similarly define \(Y_u\) to be the vertex of \(A\) such that \(Y_uu\in M\text{.}\)
For any total order \(\prec\) on \(A\text{,}\) we have, by Lemma 7.1.9,
\begin{equation} \mathbb{H}(X) = \sum_{v\in A}\mathbb{H}(X_v\mid X_w, w\prec v)\text{.}\tag{7.3.1} \end{equation}
Given a vertex \(v\in A\) and a total order \(\prec\) on \(A\text{,}\) we define the following random variable
\begin{equation*} R_{v}^\prec:=\left|N(v)\setminus \{u\in B: Y_u\prec v\}\right|\text{.} \end{equation*}
Note that \(R_{v}^\prec\) is determined by \((X_w: w\prec v)\text{.}\) So, by Lemma 7.1.12 and Lemma 7.1.11 and the definition of conditional entropy,
\begin{equation*} \mathbb{H}(X_v\mid X_w: w\prec v)= \mathbb{H}(X_v\mid (X_w: w\prec v), R_{v}^\prec)\leq \mathbb{H}(X_v\mid R_{v}^\prec)=\sum_{k=1}^{d(v)}\mathbb{P}(R_v^\prec=k)\mathbb{H}(X_v\mid R_v^\prec=k)\text{.} \end{equation*}
When \(R_v^\prec=k\text{,}\) then the number of choices for \(X_v\) is at most \(k\text{.}\) So, by Lemma 7.1.4, we have \(\mathbb{H}(X_v\mid R_v^\prec=k)\leq \log_2(k)\) and so
\begin{equation*} \mathbb{H}(X_v\mid X_w: w\prec v)\leq \sum_{k=1}^{d(v)}\mathbb{P}(R_v^\prec=k)\log_2(k)\text{.} \end{equation*}
Plugging this back into equation (7.3.1) and summing over all choices of \(\preceq\) yields
\begin{equation*} \mathbb{H}(X)\leq\frac{1}{n!}\sum_{\prec}\sum_{v\in A}\sum_{k=1}^{d(v)}\mathbb{P}(R_v^\prec=k)\log_2(k)=\frac{1}{n!}\sum_{v\in A}\sum_{k=1}^{d(v)}\log_2(k)\sum_{\prec}\mathbb{P}(R_v^\prec=k) \end{equation*}
\begin{equation*} =\frac{1}{n!}\sum_{v\in A}\sum_{k=1}^{d(v)}\log_2(k)\sum_{\prec}\sum_{M}\frac{1_{\{R_v^\prec=k\}}}{\permat(G)} \end{equation*}
\begin{equation*} =\frac{1}{\permat(G)}\sum_{v\in A}\sum_{k=1}^{d(v)}\log_2(k)\sum_{M}\sum_{\prec}\frac{1_{\{R_v^\prec=k\}}}{n!} \end{equation*}
\begin{equation*} =\frac{1}{\permat(G)}\sum_{v\in A}\sum_{k=1}^{d(v)}\log_2(k)\sum_{M}\frac{1}{d(v)} \end{equation*}
\begin{equation*} =\sum_{v\in A}\sum_{k=1}^{d(v)}\log_2(k)\frac{1}{d(v)} =\sum_{v\in A}\frac{\log_2(d(v)!)}{d(v)}. \end{equation*}
Therefore,
\begin{equation*} \permat(G)\leq \prod_{v\in A}(d(v)!)^{1/d(v)}\text{.} \end{equation*}
Brègman’s Theorem can also be interpreted as an upper bound on the permanent of a matrix. Given an \(n\times n\) matrix \(A = (a_{i,j})_{1\leq i,j\leq n}\text{,}\) the permanent of \(A\) is
\begin{equation*} \per(A):=\sum_{\sigma \in S_n}\prod_{i=1}^na_{i,\sigma(i)} \end{equation*}
where \(S_n\) is the set of all bijections \(\sigma:\{1,\dots,n\}\to \{1,\dots,n\}\) (i.e. the symmetric group of order \(n\)). For completeness, define \(\per(A)=0\) if \(A\) is not a square matrix. Note that this is the same thing as the determinant, except without alternating signs. However, unlike the determinant, which can be efficiently computed, e.g. by Gauss–Jordan elimination, the permanent is computationally difficult to compute. Given a bipartite graph \(G\) with bipartition \((A,B)\) with \(A=\{u_1,\dots,u_k\}\) and \(B=\{v_1,\dots,v_\ell\}\text{,}\) the biadjacency matrix of \(G\) is the \(k\times \ell\) matrix where the \((i,j)\) entry is \(1\) if \(u_iv_j\in E(G)\) and \(0\) otherwise. The following is not hard to prove.

Observation 7.3.3.

If \(G\) is a bipartite graph with biadjacency matrix \(A\text{,}\) then
\begin{equation*} \permat(G)=\per(A)\text{.} \end{equation*}
Thus, Theorem 7.3.2 is equivalent to the following.
What about non-bipartite graphs, you may ask? As it turns out, there is a nice trick for applying Corollary 7.3.4 to get the following best-possible upper bound for general graphs; we will explore the proof in the exercises.

Proof.

Here are two YouTube videos related to Brègman’s Theorem: