Die van-der-waerdensche Permanentenvermutung (englisch van der Waerden permanent conjecture) ist ein berühmter, inzwischen bewiesener mathematischer Lehrsatz, der von dem Mathematiker Bartel Leendert van der Waerden im Jahre 1926 als Vermutung aufgestellt wurde. Sie behauptet eine elementare untere Abschätzung für Permanenten reeller doppelt-stochastischer Matrizen.

Bestätigung der Vermutung

Van der Waerdens Vermutung stand mehrere Jahrzehnte unbewiesen im Raum und konnte schließlich durch die beiden Mathematiker Georgi P. Jegortschow und Dmitry I. Falikman – die unabhängig voneinander arbeiteten – in den Jahren 1980–1981 bestätigt werden. Es gilt also der folgende Lehrsatz:

Gegeben seien eine natürliche Zahl ${\displaystyle n\geq 1}$ sowie eine reelle doppelt-stochastische Matrix ${\displaystyle A\in {\mathbb {R} }^{n\times n}}$.

Dann besteht die Ungleichung

${\displaystyle \operatorname {perm} (A)\geq {\frac {n!}{n^{n}}}}$.

Dabei gilt in dieser Ungleichung das Gleichheitszeichen dann und nur dann, wenn alle Elemente der Matrix ${\displaystyle A}$ gleich ${\displaystyle \textstyle {\frac {1}{n}}}$ sind.

Hinweis zur Namensgebung

In der englischsprachigen Fachliteratur wird die oben gegebene Ungleichung mitunter auch als Van der Waerden-Egorychev-Falikman inequality bezeichnet.

Literatur

• Marshall Hall, Jr.: Combinatorial Theory (= Wiley-Interscience Series in Discrete Mathematics). 2. Auflage. John Wiley & Sons, Inc., New York 1986, ISBN 0-471-09138-3 (MR0840216). 
• Donald E. Knuth: A permanent inequality. In: American Mathematical Monthly. Band 88, 1981, S. 731–740, 798 (MR0668399). 
• Henryk Minc: Nonnegative Matrices (= Wiley-Interscience Series in Discrete Mathematics and Optimization). John Wiley & Sons, Inc., New York 1988, ISBN 0-471-83966-3 (MR0932967). 
• Henryk Minc: The van der Waerden permanent conjecture. In: General inequalities 3 (Oberwolfach, 26.4.–2.5.1981; herausgegeben von E. F. Beckenbach und W. Walter) (= International Series of Numerical Mathematics. Band 64). Birkhäuser Verlag, Basel 1983, S. 23–40 (MR0785765). 
• Kenneth H. Rosen (Hrsg.): Handbook of Discrete and Combinatorial Mathematics (= Discrete Mathematics and its Applications). CRC Press, 2000, ISBN 0-8493-0149-1. 
• B. L. van der Waerden: Aufgabe 45. In: Jahresbericht der Deutschen Mathematiker-Vereinigung. Band 35, 1926, S. 117. 

Anmerkungen

1. ↑ Hier beachte man die unterschiedlichen Transkriptionen russischer Namen ins Deutsche und Englische.

Einzelnachweise

1. 1 2 3 Kenneth H. Rosen (Hrsg.): Handbook of Discrete and Combinatorial Mathematics. 2000, S. 423
2. 1 2 Marshall Hall, Jr.: Combinatorial Theory. 1986, S. 58 ff.
3. 1 2 Henryk Minc: Nonnegative Matrices. 1988, S. 128 ff.
4. ↑ Henryk Minc: The van der Waerden permanent conjecture. General inequalities 3, S. 731–740, 798
5. ↑ Donald E. Knuth: A permanent inequality. Amer. Math. Monthly 88, S. 731–740, 798