Séminaire Lotharingien de Combinatoire, B36z (1996), 10pp.
S.-G. Hwang and A. R. Kräuter
A Comparison of Two Upper Bounds
for the Permanent of (0,1)-Matrices
Abstract.
The permanental bounds for (0,1)-matrices by
Minc-Bregman (1973) and for fully indecomposable integral matrices by Donald
et al. (1984) are, in general, not comparable, even if we restrict
ourselves to the class of fully indecomposable (0,1)-matrices A.
In this note we present sufficient conditions (in terms of the number of
those row sums of A that equal 2) such that it is possible to
predict immediately
which of the two bounds yields the better estimation for a given A. It is
noteworthy that this can be done without computing the bounds explicitly. As
an important tool we derive a couple of properties of a function that is
closely related to the classical gamma function.
The following versions are available: