Van der Waerdensche permanent presumption
The van der Waerden permanent conjecture ( English: van der Waerden permanent conjecture ) is a famous, now proven mathematical theorem , which was put forward as a conjecture by the mathematician Bartel Leendert van der Waerden in 1926. It asserts an elementary lower estimate for permanents of real double-stochastic matrices .
Confirmation of the presumption
Van der Waerden's conjecture remained unproven for several decades and was finally confirmed by the two mathematicians Georgi P. Jegortschow and Dmitry I. Falikman - who worked independently of each other - in the years 1980–1981. So the following theorem applies :
- A natural number and a real double-stochastic matrix are given .
-
Then there is the inequality
- .
- In this inequality, the equal sign applies if and only if all elements of the matrix are equal .
Note on naming
In the English-language specialist literature, the inequality given above is sometimes also referred to as Van der Waerden-Egorychev-Falikman inequality .
literature
- Marshall Hall, Jr .: Combinatorial Theory (= Wiley-Interscience Series in Discrete Mathematics ). 2nd Edition. John Wiley & Sons, Inc. , New York 1986, ISBN 0-471-09138-3 ( MR0840216 ).
- Donald E. Knuth : A permanent inequality . In: American Mathematical Monthly . tape 88 , 1981, pp. 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, April 26 - May 2, 1981; edited by EF Beckenbach and W. Walter ) (= International Series of Numerical Mathematics . Volume 64 ). Birkhäuser Verlag , Basel 1983, p. 23-40 ( MR0785765 ).
- Kenneth H. Rosen (Ed.): Handbook of Discrete and Combinatorial Mathematics (= Discrete Mathematics and its Applications ). CRC Press, 2000, ISBN 0-8493-0149-1 .
- BL van der Waerden: Exercise 45 . In: Annual report of the German Mathematicians Association . tape 35 , 1926, pp. 117 .
Remarks
- ↑ Please note the different transcriptions of Russian names into German and English.
Individual evidence
- ↑ a b c Kenneth H. Rosen (Ed.): Handbook of Discrete and Combinatorial Mathematics. 2000, p. 423
- ^ A b Marshall Hall, Jr .: Combinatorial Theory. 1986, p. 58 ff.
- ^ A b Henryk Minc: Non-negative matrices. 1988, p. 128 ff.
- ^ Henryk Minc: The van der Waerden permanent conjecture. General inequalities 3, pp. 731-740, 798
- ^ Donald E. Knuth: A permanent inequality. Amer. Math. Monthly 88, pp. 731-740, 798