Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials: One Theorem for all. | Van der Waerden Schrijver-Valiant like Conjectures and Stable aka Hyperbolic Homogeneous Polynomials One Theorem for all Leonid Gurvits Los Alamos National Laboratory gurvits@ Submitted Jul 29 2007 Accepted Apr 29 2008 Published May 5 2008 Mathematics Subject Classihcation 05E99 Abstract Let p be a homogeneous polynomial of degree n in n variables p z1 . zn p Z Z 2 Cn. We call such a polynomial p H-Stable if p z1 . zn 0 provided the real parts Re zi 0 1 i n. This notion from Control Theory is closely related to the notion of Hyperbolicity used intensively in the PDE theory. The main theorem in this paper states that if p x1 . xn is a homogeneous H-Stable polynomial of degree n with nonnegative coefficients degp i is the maximum degree of the variable xi Ci min degp i i and Cap p inf_ p xi . xra Xi 0 1 i n Xi xn then the following inequality holds . p 0 . 0 Cap p n C7 p1. @ 2 kS C This inequality is a vast and unifying generalization of the Van der Waerden conjecture on the permanents of doubly stochastic matrices as well as the Schrijver-Valiant conjecture on the number of perfect matchings in k-regular bipartite graphs. These two famous results correspond to the H-Stable polynomials which are products of linear forms. Our proof is relatively simple and noncomputational it uses just very basic properties of complex numbers and the AM GM inequality. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R66 1 1 The permanent the mixed discriminant the Van Der Waerden conjecture s and homogeneous polynomials Recall that an n X n matrix A is called doubly stochastic if it is nonnegative entry-wise and its every column and row sum to one. The set of n X n doubly stochastic matrices is denoted by Qn. Let A k n denote the set of n X n matrices with nonnegative integer entries and row and column sums all equal to k. We define the following subset of rational doubly stochastic matrices Qk k 1 A A 2 A k n . In a 1989 paper 2 . Bapat defined the set Dn of doubly .
