\documentstyle[german,12pt,twoside,leqno]{article}
\pagestyle{myheadings}
\markboth{\hfill {\sc s.-g.~hwang und a.~r.~kr\"auter} \hfill}{\hfill
{\sc permanenten} \hfill} 
\thispagestyle{empty}
\begin{document}

\noindent
{\sc S\'eminaire Lotharingien de Combinatoire} {\rm B36z (10pp.)}

\vspace{39pt}

\begin{center}
{\bf EIN VERGLEICH ZWEIER OBERER SCHRANKEN 

\vspace{6pt}

F\"UR DIE PERMANENTE VON $ (0,1) $-MATRIZEN}

\vspace{9pt}

{\sc von

\vspace{9pt}

Suk-Geun HWANG und Arnold Richard KR\"AUTER}
\end{center}

\vspace{21pt}

\setlength{\baselineskip}{12pt}

{\footnotesize {\sc Zusammenfassung.} \quad In dieser Note werden 
hinreichende
Bedingungen daf\"ur angegeben, welche der Permanentenabsch\"atzungen von 
Minc-Br\.egman (1973) und Donald {\it et al.} (1984) f\"ur eine gegebene
Matrix sch\"arfer ist.

\vspace{6pt}

{\sc Abstract.} \quad In this note we present sufficient conditions such
that one can predict immediately which one of
the permanental bounds by Minc-Br\.egman (1973) and Donald {\it et al.}
(1984) gives the better estimation for a given matrix.}

\setlength{\baselineskip}{15pt}

\vspace{21pt}

{\bf 1. Einleitung.} \quad Es sei $ A =(a_{ij}) $ eine $ n \times n $-Matrix 
\"uber $ {\bf{C}} $. Die {\it Permanente} von $ A $ ist definiert durch

\[
{\rm per}(A): = \sum_{\sigma \in S_n} a_{1 \sigma(1)} \cdot \ldots \cdot 
a_{n \sigma(n)} ,
\]
wobei $ S_n $ die symmetrische Gruppe der Ordnung $ n $ bezeichnet.

Eine Matrix $ A = (a_{ij} ) $ hei\ss t $ (0,1) $-{\it Matrix} falls
$ a_{ij} \in \{ 0,1 \} $ ist f\"ur alle $ i $ und $ j $.

Eine $ n \times n $-Matrix $ A $ hei\ss t {\it vollst\"andig unzerlegbar,}
falls es keine $ n \times n $-Permutationsmatrizen $ P $ und $ Q $ gibt
mit

\[
PAQ = \left[
\begin{array}{cc}
X & O \\
Z & Y 
\end{array}
\right],
\]
wobei die Diagonalbl\"ocke $ X $ und $ Y $ quadratisch sind. Anderenfalls
hei\ss t $ A $ {\it teilweise zerlegbar.}

Ausgangspunkt unserer Untersuchungen sind die folgenden zwei Ungleichungen
f\"ur Permanenten:

\vspace{12pt}

{\sc Satz A} $\;$ (vermutet von H.~Minc [6], bewiesen von L.~M.~Br\.egman [1], 
neu bewiesen von A.~Schrijver [8]). \quad {\it Es sei 
$ A $ eine} 
$ n \times n $-(0,1)-{\it Matrix mit den Zeilensummen $ r_1, \ldots , r_n $. 
Dann gilt}
\begin{eqnarray}
{\rm per}(A) \leq \prod^n_{i=1} r_i!^{1/r_i}.
\end{eqnarray}
{\it Gleichheit tritt in} (1) {\it genau dann auf, wenn $ A $ 
permutations\"aquivalent zu einer direkten Summe quadratischer Bl\"ocke ist,
deren Elemente s\"amtlich $ 1 $ sind.}

\vspace{12pt}

{\sc Satz B} $\;$ (J.~Donald, J.~Elwin, R.~Hager \& P.~Salamon [2], neu
bewiesen von S.-G.~Hwang \& A.~R.~Kr\"auter [4]). \quad
{\it Es sei $ A $ eine vollst\"andig unzerlegbare $ n \times n $-Matrix
mit nichtnegativen ganzzahligen Elementen und den Zeilensummen
$ r_1, \ldots, r_n $. Dann gilt}
\begin{eqnarray}
{\rm per}(A) \leq 1 + \prod^n_{i=1} (r_i - 1).
\end{eqnarray}
Auf die Wiedergabe der in [3] angegebenen Gleichheitsbedingung wird hier 
wegen der zahlreichen technischen Details verzichtet.

\vspace{12pt}

{\sc Bemerkungen.}

(a) Die Schranke in (1) gilt f\"ur {\it alle} $ (0,1) $-Matrizen, ob sie nun 
vollst\"andig unzerlegbar oder teilweise zerlegbar sind. Die Schranke in (2) 
hingegen gilt f\"ur {\it alle} vollst\"andig unzerlegbaren nichtnegativen 
ganzzahligen Matrizen, ob sie nun blo\ss\ Nullen und Einsen oder auch andere 
ganze Zahlen enthalten.


(b) Selbst dann, wenn wir uns auf vollst\"andig unzerlegbare $ (0,1) $-Matrizen
beschr\"anken, sind die Schranken in (1) und (2) nicht vergleichbar,
da (1) sch\"arfer ist als (2), falls viele Zeilensummen gr\"o\ss er als $ 2 $
sind, und da (2) sch\"arfer ist als (1), falls viele Zeilensummen gleich
$ 2 $ sind und die anderen Zeilensummen nicht besonders gro\ss\
(H.~Minc [7]).

\vspace{12pt}
  
{\sc Problem.} \quad Im folgenden bezeichne $ A $ stets eine {\it 
vollst\"andig unzerlegbare}
$ n \times n $-(0,1)-Matrix mit den Zeilensummen $ r_1, \ldots , r_n $.
Aus Bemerkung (b) folgt, da\ss\  die Anzahl der Zeilen von $ A $ mit genau
zwei Einsen von ma\ss geblicher Bedeutung daf\"ur ist, welche der beiden zur
Diskussion stehenden Ungleichungen die sch\"arfere Schranke liefert. Wir f\"uhren
deshalb diese Anzahl als zus\"atzlichen Parameter ein und leiten ein 
Kriterium daf\"ur her, welche der Schranken (1) und (2) f\"ur eine gegebene 
Matrix $ A $ die bessere ist.

\vspace{12pt}

{\bf 2. Eigenschaften einer mit der Gamma-Funktion zusammenh\"an\-gen\-den 
Funktion.} \quad Um die Herleitung des angek\"undigten Kriteriums zu 
erm\"oglichen, ben\"oti\-gen wir einige vorbereitende Betrachtungen \"uber eine 
mit der Gamma-Funk\-tion zusammenh\"angende Funktion. Dazu sei
\begin{eqnarray}
\Phi (x) : = \Gamma (x+1)^{1/x}, \quad x > 0,
\end{eqnarray}
wobei $ \Gamma $ die Gamma-Funktion bezeichnet.
Es ist bemerkenswert, da\ss\  f\"ur alle positiven ganzen Zahlen $ n $ gilt:

\[
\Phi(n) = n!^{1/n} .
\]
Ferner definieren wir
\begin{eqnarray}
g_{a,b}(x) : = \ln \frac{ax + b}{\Phi (x)}, \quad 
x > - \, \frac{b}{a} > 1,
\end{eqnarray}
wobei $ a $ und $ b $ reelle Konstanten bezeichnen.

\vspace{12pt}

{\sc Satz 1} $\;$ (S.-G.~Hwang \& A.~R.~Kr\"auter [5]). \quad $ g_{a,b} (x) $
{\it ist streng monoton wachsend und konkav. Ferner gilt}
\begin{eqnarray}
\lim_{x \to \infty} g_{a,b} (x) = 1 + \ln a .
\end{eqnarray}
(Der Beweis beruht im Wesentlichen auf der Stirlingschen Formel f\"ur die
Gamma-Funktion,
\begin{eqnarray}
\Gamma(x) = \sqrt{2 \pi} x^{x- \frac{1}{2}} e^{-x + \mu(x)}, \quad x > 0,
\end{eqnarray}
und verwendet einige Eigenschaften von $ \mu (x) $.)

\vspace{12pt}

Wir definieren
\begin{eqnarray}
\lambda (x) : = g_{1,-1}(x) = \ln \frac{x-1}{\Phi (x)}, \quad x > 1 .
\end{eqnarray}

\vspace{12pt}

{\sc Korollar 1.}

(a) $ \lambda(x) $ {\it ist streng monoton wachsend und konkav. \"Uberdies
gilt die Beziehung}
\begin{eqnarray}
\lim_{x \to \infty} \lambda(x) = 1.
\end{eqnarray}

(b) {\it Es gelten die folgenden Ungleichungen:}
\begin{eqnarray}
\Phi (x) > x - 1 \quad \mbox{{\it f\"ur}} \quad 0 < x < x_0,
\end{eqnarray}
\begin{eqnarray}
\Phi (x) < x - 1 \quad \mbox{{\it f\"ur}} \quad x_0 < x < \infty,
\end{eqnarray}
{\it wobei} $ x_0 = 2,695142 \ldots $ {\it die eindeutig bestimmte
Nullstelle von} $ \lambda(x) $ {\it f\"ur} $ x > 1 $ {\it ist}.

(c) {\it Die Funktion} $ \frac{x-1}{\Phi (x)} $ {\it ist streng monoton
wachsend f\"ur} $ x > 1 $.

\vspace{24pt}

{\bf 3. Ein Vergleich der Absch\"atzungen (1) und (2) f\"ur vollst\"andig 
unzerlegbare $ (0,1) $-Matrizen.} \quad Gem\"a\ss\  Korollar 1, (b) ist die 
Schranke $ (1) $ besser (bzw. schlechter)
als die Schranke (2), falls $ r_i \geq  3 $ (bzw. $ r_i = 2 $ ) f\"ur alle
$ i $ gilt. F\"ur weiterreichende Aussagen ben\"otigen wir einige zus\"atzliche 
Bezeichnungen. Es seien
$ r_1, \ldots , r_n $ ganze Zahlen $ \geq 2 $, ferner sei $ {\bf r} =
(r_1, \ldots, r_n) $. Wir definieren
\begin{eqnarray}
\mu({\bf r}) : = \prod_{i=1}^n \Phi (r_i),
\end{eqnarray}
\begin{eqnarray}
\delta ({\bf r}) : = 1 + \prod_{i=1}^n (r_i - 1).
\end{eqnarray}
F\"ur ganze Zahlen $ n $ und $ k $ mit $ 0 \leq k \leq n $ sei

\[
{\cal S} (n,k) : = \{ {\bf r} = (r_1, \ldots , r_n) : k \;  \mbox{der} \;
r_i \; \mbox{sind gleich} \; 2, \quad 3 \leq r_i \leq n \; \mbox{sonst} \}.
\]
Im folgenden bestimmen wir die Mengen

\[
K_n : = \{ k : 0 \leq k \leq n, \mu({\bf r }) < \delta({\bf r}) \;
\mbox{f\"ur alle} \; {\bf r} \in {\cal S} (n,k) \},
\]
\[
L_n : = \{ k : 0 \leq k \leq n, \mu({\bf r}) > \delta ({\bf r}) \;
\mbox{f\"ur alle} \; {\bf r} \in {\cal S} (n,k) \}
\]
und zeigen, da\ss\ 

\[
K_n = \{ 0,1,2, \ldots , k_1 (n) \},
\]
\[
L_n = \{ k_2(n), k_2(n) + 1, \ldots, n-1,n \}
\]
gilt, wobei $ k_1(n) $ und $ k_2(n) $ extremal in dem Sinne sind, da\ss\ 
$ k_1 (n) + 1 \notin K_n $ und $ k_2(n) - 1 \notin L_n $. Nun sind wir in der
Lage, das folgende wichtige Hilfsresultat zu formulieren.

\vspace{12pt}

{\sc Lemma 1.} \quad {\it Es sei} \, $ {\bf x}_k = (2, \ldots, 2,3, \ldots, 
3) \in {\cal S} (n,k) $ {\it und} \, $ {\bf y}_k = (2, \ldots, 2,n,
\ldots, n) \in {\cal S} (n,k). $ {\it Dann gilt f\"ur alle} $ {\bf r}
\in {\cal S} (n,k) $
\begin{eqnarray}
\delta ( {\bf x}_k) - \mu ( {\bf x}_k) \leq \delta ( {\bf r} ) -
\mu ( {\bf r} ) \leq \delta ({\bf y}_k) - \mu ( {\bf y}_k) .
\end{eqnarray}

\vspace{12pt}

Zur Bestimmung von $ K_n $ definieren wir
\begin{eqnarray}
c: = \frac{\ln (2 \sqrt{2} / \sqrt[3]{6} )}{\ln (2/ \sqrt[3]{6})} =
4,614131 \ldots,
\end{eqnarray}
und, f\"ur ganze Zahlen $ n $ und $ k $ mit $ 0 \leq k \leq n, $
\begin{eqnarray}
\epsilon(n,k) : = \frac{1}{\ln (2 \sqrt{2}/ \sqrt[3]{6})}
\ln \left( 1 + \frac{1}{2^{n-k}} \right) .
\end{eqnarray}
$ \epsilon $ besitzt folgende Eigenschaften:

(a) $ \epsilon (n,k) > 0 $ ;

(b) $ \epsilon (n,k) \to 0 \quad \mbox{f\"ur} \quad (n-k) \to \infty $;

(c) $ \epsilon  (n,k) < 1 \quad \mbox{f\"ur} \quad k \leq n - 1 $.

Eine entscheidende Rolle bei der Bestimmung von $ k_1(n) $ spielt
die folgende Ungleichung:
\begin{eqnarray}
\lfloor n/c \rfloor + 1 - \frac{n}{c} < \epsilon (n, \lfloor n/c 
\rfloor + 1),
\end{eqnarray}
worin $ \lfloor x \rfloor $ den ganzzahligen Anteil von $ x $ bezeichnet.

\vspace{12pt}

{\sc Satz 2} $\;$ (S.-G.~Hwang \& A.~R.~Kr\"auter [5]). \quad {\it Es sei} 
$ n \geq 3 $ {\it eine ganze Zahl und es sei} $ K_n $ {\it die
oben definierte Menge. Dann gilt} $ K_n = \{ 0,1,2, \ldots, k_1 (n) \} $,
{\it wobei}

\[
k_1(n) = \left\{
\begin{array}{ll}
\lfloor n/c \rfloor + 1, & \quad \mbox{\it falls} \quad (16) \quad
\mbox{\it gilt,} \\
\lfloor n/c \rfloor      & \quad \mbox{\it sonst.}
\end{array} \right.
\]

{\it Beweisskizze.} \quad Wir zeigen

\[
K_n = \{ k : 0 \leq k \leq \lfloor n/c \rfloor + a_n \},
\]
wobei

\[
a_n = \left\{
\begin{array}{ll}
1, & \quad \mbox{falls} \quad   (16) \quad \mbox{gilt,} \\
0  & \quad \mbox{sonst.}
\end{array} \right.
\]
F\"ur $ {\bf x}_k = (2, \ldots, 2,3, \ldots, 3) \in {\cal S} (n,k) $ folgt
aus Lemma 1 sofort

\[
K_n = \{ k: 0 \leq k \leq n, \; \mu ({\bf x}_k) < \delta ({\bf x}_k) \}.
\]
Nun ist

\[
\mu ( {\bf x}_k ) = 2^{k/2} \Phi (3)^{n-k},
\]
\[
\delta ({\bf x}_k) = 2^{n-k} \left( 1 + \frac{1}{2^{n-k}} \right).
\]
Somit gilt $ \mu ({\bf x}_k) < \delta ( {\bf x}_k ) $ genau dann, wenn

\[
\left( \frac{2 \sqrt{2}}{\Phi (3)} \right)^k <
\left( \frac{2}{\Phi (3) } \right)^n \left( 1 + \frac{1}{2^{n-k}} \right)
\]
gilt oder
\begin{eqnarray}
k < \frac{n}{c} + \epsilon (n,k).
\end{eqnarray}
Ist nun $ k \leq \lfloor n/c \rfloor $, so ist (17) sicher erf\"ullt und
damit $ \{ 0,1,2, \ldots, \lfloor n/c \rfloor \} \subseteq K_n $.
$ k = \lfloor n/c \rfloor + 1 $ gen\"ugt (17) genau dann, wenn (16) erf\"ullt 
ist.

\noindent
Wir haben noch zu zeigen: $ K_n $ enth\"alt kein $ k $ mit $ \lfloor n/c 
\rfloor + 2 \leq k \leq n $. Wegen $ n \geq 3 $ ist sicher $ n \notin K_n $.
Es sei also $ \lfloor n/c \rfloor + 2 \leq k \leq n - 1 $. Dann ist aber
$ \epsilon (n,k) < 1 $ und somit

\[
k \geq  ( \lfloor n/c \rfloor + 1) + 1 > \frac{n}{c} + \epsilon (n,k).
\]
\hfill $ \Box $

\vspace{12pt}

Zur Bestimmung von $ L_n $ definieren wir
\begin{eqnarray}
\beta_n : = 1 + \frac{\ln \sqrt{2}}{\lambda (n) }
\end{eqnarray}
und
\begin{eqnarray}
\zeta (n,k) : = \frac{1}{\ln \sqrt{2} + \lambda(n)} \ln 
\left( 1 + \frac{1}{(n-1)^{n-k}} \right).
\end{eqnarray}
$ \beta_n $ und $ \zeta $ besitzen folgende Eigenschaften:

(a) $ \beta_n \searrow 1 + \ln \sqrt{2} $ f\"ur $ n \rightarrow \infty $;

(b) $ \zeta (n,k) \rightarrow 0 $ f\"ur $ n \rightarrow \infty $;

(c) $ \zeta (n,k) < 1 $, falls $ k < n $. 

Die "`Testungleichung"' bei der Bestimmung von $ k_2(n) $
lautet

\begin{eqnarray}
\lfloor n/\beta_n \rfloor + 1 - \frac{n}{\beta_n} > \zeta
(n, \lfloor n/ \beta_n \rfloor + 1 ) .
\end{eqnarray}

\vspace{12pt}

{\sc Satz 3} $\;$ (S.-G.~Hwang \& A.~R.~Kr\"auter [5]). \quad {\it Es sei }
$ n \geq 3 $ {\it eine ganze Zahl und} $ L_n $ {\it wie oben definiert. Dann
gilt} $ L_n = \{ k_2 (n), k_2(n) + 1, \ldots, n-1,n \} $, {\it wobei}

\[
k_2(n) = \left\{ 
\begin{array}{ll}
\lfloor n/\beta_n \rfloor + 1, & \quad \mbox{\it falls} \quad (20)
\quad 
\mbox{\it gilt,} \\
\lfloor n/\beta_n \rfloor + 2, & \quad \mbox{\it sonst.}
\end{array} \right.
\]

\vspace{12pt}

\noindent
F\"ur $ n \leq 10 $ sind die Werte von $ k_1(n) $ und $ k_2(n) $ in Tabelle 1
angef\"uhrt.  

\vspace{12pt}

\begin{center}
\begin{tabular}{|c||c|c|} \hline
$ n $ & $ k_1(n) $ & $ k_2(n) $ \\ \hline
3 & 1 & 2 \\
4 & 1 & 3 \\
5 & 1 & 3 \\
6 & 1 & 4 \\
7 & 1 & 5 \\
8 & 2 & 6 \\
9 & 2 & 6 \\
10 & 2 & 7 \\ \hline
\end{tabular}

\vspace{12pt}

{\sc Tabelle 1.}

\end{center}

\vspace{12pt}

{\sc Bemerkung.} \quad Aufgrund von Satz 2 k\"onnte man erwarten, da\ss\  
$ \beta_n $
aus Satz 3, welches ja von $ n $ abh\"angt, durch eine Konstante $ \beta $ 
ersetzt werden kann. Mit kleinen Einschr\"ankungen ist dies tats\"achlich m\"oglich,
wie der folgende Satz zeigt.

\vspace{12pt}

{\sc Satz 4} $\;$ (S.-G.~Hwang \& A.~R.~Kr\"auter [5]). \quad {\it Es seien} 
$ n \geq 
4 $ {\it und } $ k \leq n $ {\it ganze Zahlen. Falls} $ k > n/(1+ \ln 
\sqrt{2} ) $ {\it gilt, dann ist } $  k \in L_n $.

\vspace{12pt}

{\sc Bemerkungen.}

(a) Es sei $ \beta = 1 + \ln \sqrt{2} $. Satz 4 hat den Vorteil, da\ss\  nun die
unhandliche Beziehung (20) nicht mehr erforderlich ist. Ein Nachteil von 
Satz 4 besteht darin, da\ss\  nunmehr im allgemeinen wegen
$ k \geq \lfloor n/\beta \rfloor + 1 \qquad k > k_2(n) $ ist.

(b) Aufgrund der Gr\"o\ss e der "`Skalierungsfaktoren"' $ c $ und $ \beta_n $ tritt
eine L\"ucke zwischen $ k_1(n) $ und $ k_2(n) $ auf, das hei\ss t f\"ur 
$ k_1(n) < k < k_2(n) $ ist keine einheitliche Vorhersage m\"oglich, ob
$ \mu( {\bf r} ) < \delta ( {\bf r}) $ oder $ \mu ( {\bf r}) > \delta
( {\bf r}) $ gilt f\"ur $ {\bf r} \in {\cal S} (n,k) $.

\vspace{12pt}

{\sc Beispiel.} \quad Es sei $ n = 4 $ und $ k = 2 $. Dann ist nach Satz 2 
und Satz 3 $ k_1(4) < 2 < k_2 (4) $. Hier gibt es folgende drei 
M\"oglichkeiten:

\noindent
(a) $ {\bf r} = ( 2,2,3,3) $. Dann gilt

\[
6,603 \ldots = \mu ( {\bf r} ) > \delta ( {\bf r} ) = 5
\]
f\"ur die Matrizen

\[
\left[
\begin{array}{cccc}
1 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 \\
1 & 0 & 1 & 1
\end{array} \right],
\quad\left[
\begin{array}{cccc}
1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1
\end{array} \right],
\quad\left[
\begin{array}{cccc}
1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
1 & 0 & 1 & 1
\end{array} \right],
\quad\left[
\begin{array}{cccc}
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 \\
1 & 0 & 1 & 1
\end{array} \right].
\]
(b) $ {\bf r} = (2,2,3,4) $. Dann gilt

\[
8,043 \ldots = \mu ( {\bf r} ) > \delta ( {\bf r} ) = 7
\]
f\"ur die Matrizen

\[
\left[
\begin{array}{cccc}
1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1
\end{array} \right],
\quad
\left[
\begin{array}{cccc}
1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 1 & 1
\end{array} \right],
\quad
\left[
\begin{array}{cccc}
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 \\
1 & 1 & 1 & 1
\end{array} \right].
\]

\noindent
(c) $ {\bf r}  = (2,2,4,4) $. Dann gilt

\[
9,797 \ldots = \mu ({\bf r} ) < \delta ( {\bf r} ) = 10
\]
f\"ur die Matrizen

\[
\left[
\begin{array}{cccc}
1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1
\end{array} \right],
\quad
\left[
\begin{array}{cccc}
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1
\end{array} \right].
\]

\vspace{33pt}

\begin{center}
{\sc zitierte literatur}
\end{center}

\begin{footnotesize}

\begin{enumerate}

\item L. M. Br\.egman, Some properties of nonnegative matrices and their
permanents [Russian], {\it Dokl. Akad. Nauk SSSR} {\bf 211} (1973), 27 - 30.
English translation in {\it Sov. Math. Dokl.} {\bf 14} (1973), 945 - 949.
\item J. Donald, J. Elwin, R. Hager, and P. Salamon, A graph theoretic upper
bound on the permanent of a nonnegative integer matrix. I, {\it Linear Algebra
Appl.} {\bf 61} (1984), 187 - 198.
\item J. Donald, J. Elwin, R. Hager, and P. Salamon, A graph theoretic upper
bound on the permanent of a nonnegative integer matrix II. The extremal case.
{\it Linear Algebra Appl.} {\bf 61} (1984), 199 - 218.
\item S. G. Hwang and A. R. Kr\"auter, A matrix theoretical proof of an upper
bound for the permanent of a nonnegative integral matrix. {\it Preprint,
Montanuniversit\"at Leoben,} 1996.
\item S. G. Hwang and A. R. Kr\"auter, Comparison of permanental bounds of
(0,1)-matrices. {\it Preprint, Montanuniversit\"at Leoben,} 1996.
\item H. Minc, Upper bounds for permanents of (0,1)-matrices. {\it Bull.
Amer. Math. Soc.} {\bf 69} (1963), 789 - 791.
\item H. Minc, Theory of permanents 1982 - 1985. {\it Linear Multilinear
Algebra} {\bf 21} (1987), 109 - 148.
\item A. Schrijver, A short proof of Minc's conjecture. {\it J. Comb. 
Theory Ser. A} {\bf 25} (1978), 80 - 83.

\end{enumerate}

\end{footnotesize}

\vspace{36pt}

\begin{tabular}{lp{4.8cm}l}
& & Suk-Geun {\sc Hwang} \\
& & Department of Mathematics Education \\
& & Teachers College \\
& & Kyungpook National University \\
& & Taegu 702-701, Republik Korea \\
& & E-mail: {\sf sghwang@bh.kyungpook.ac.kr} \\
& & \\
& & und \\
& & \\
& & Arnold Richard {\sc Kr\"auter} \\
& & Institut f\"ur Mathematik \\
& & und Angewandte Geometrie \\
& & Montanuniversit\"at Leoben \\
& & Franz-Josef-Stra\ss e 18 \\
& & A-8700 Leoben, \"Osterreich \\
& & E-mail: {\sf kraeuter@unileoben.ac.at} \\
\end{tabular}

\end{document}
