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: