Paul Federbush
A Mysterious Cluster Expansion Associated to the Expectation Value
of the Permanent of 0-1 Matrices
(13K, LaTeX)
ABSTRACT. We consider two ensembles of 0-1 nxn matrices. The first is the set of
all nxn matrices with entries zeroes and ones such that all column sums
and all row sums equal r, uniformly weighted. The second is the set of
nxn matrices with zero and one entries where the probability that any
given entry is one is r/n, the probabilities of the individual entries
being i.i.d.'s. Calling the two expectations E and E_B respectively,
we develop a formal relation
E(perm(A))=E_B(perm(A)) exp( sum T_i ) (A1)
We use two well known approximating ensembles to E, E_1 and E_2.
Replacing E by either E_1 or E_2 we can evaluate all terms in (A1).
The equality of (A1) holds for either E_1 or E_2 and the T_i have
amazing properties. We conjecture (A1) is true for E, and all these
properties also hold for E.