Page 72 - Textos de Matemática Vol. 39

62 SHMUEL FRIEDLAND AND DANIEL LEVY
[7] yields the existence a fpras to compute the number of perfect matchings
in a general bipartite graph satisfying #V1 = #V2. The aim of this note is to
show that there exists fpras to compute the number of k-matchings for any
bipartite graph G and any integer k ∈ [1, #V ]. In particular, the generating 2
matching polynomial of any bipartite graph G has a fpras. This observation can be used to find a fast computable approximation to the pressure function, as discussed in [4], for certain families of infinite graphs appearing in many models of statistical mechanics, like the integer lattice Zd .
More generally, there exists a fpras for computing permk B, the sum
of all k × k subpermanents of an m × n matrix B, for any nonnegative B.
This is done by showing that perm B = permBk for a corresponding k (m−k)!(n−k)!
(m+n−k)×(m+n−k) matrix Bk.
It is known that for a nonbipartite graph G on 2n vertices, the number
of perfect matchings is given by haf A(G), the hafnian of the incidence ma-
trix A(G) of G. The existence of a fpras for computing the number of perfect
matching for any undirected graph G on even number of vertices is an open
problem. (The probabilistic algorithm suggested in [7] applies to the compu-
tation of perfect matchings in G, however it is not known if this algorithm is
fpras.) The number of k-matchings in a graph G is equal to hafk A(G), the sum
of the hafnians of all 2k × 2k principle submatrices of A(G). We show that that
for any m×m matrix A there exists a (2m−2k)×(2m−2k) matrix Ak such
that hafk A = haf Ak . Hence the computation of the number of k-matching in (2m−k)!
an arbitrary G, where n = O(k), has fpras if and only if the number of perfect matching in G has fpras.
2. The equality perm B = perm Bk
k (m−k)!(n−k)!
Recall that for a squarematrix A = [aij]ni,j=1 ∈ Rn×n, the permanent of A is given as perm A := σ∈Sn a1σ(1) . . . anσ(n), where Sn is the permu-
i,j=1
ing k × l submatrix of B. Then
permk B := perm B[α, β].
α∈Qk,m,β∈Qk,n
Let G = (V1 ∪ V2, E) be a bipartite graph on two classes of vertices V1
and V2. For simplicity of notation we assume that E ⊂ V1 × V2. It would be
convenient to assume that #V1 = m, #V2 = n. So G is presented by (0, 1) ma-
trix B(G) ∈ {0,1}m×n. That is B(G) = [bij]m,n and bij = 1 ⇐⇒ (i,j) ∈ E. i,j=1
Let k ∈ [1,min(m,n)] be an integer. Then k-matching is a choice of k edges
Qk,m denote
α ∈ Qk,m, β ∈ Ql,n we let B[α, β] := [bαiβj ]k,l ∈ Rk×l to be the correspond-
tation group on ⟨n⟩ := {1, . . . , n}. Let
the set
of all subset
of
cardinality k of ⟨m⟩. Identify α ∈ Qk,m with the subset {α1, . . . , αk} where
1≤α1 <...<αk ≤m. Given an m×n matrix B = [bij]m,n ∈ Rm×n and
i,j=1