Concentration of multivariate polynomials and its applications (Q5932644): Difference between revisions

Let \(t_1,\dots,t_n\) be independent random variables which can have two values 0 and 1 and let a multi-variable polynomial in \(t_i\)'s with positive coefficients be denoted by \(Y\). If the largest number of \(t_i\)-factors in the terms of \(Y\) is \(k\), then \(Y\) is called a positive polynomial of degree \(k\), and such polynomials arise in many combinatorics problems. The authors introduce the concept of the supporting hypergraph \(H=\{V,\mathfrak E\}\) of \(Y\:V=\{1,2,\dots,n\}\) and each edge \(e\in \mathfrak E\) has at most \(k\) vertices with some weight \(w(e)\), the independent random variables \(t_i\), \(i=1,2,\dots,n\), could be one of the following types -- \(t_i\) is a \(\{0, 1\}\) variable with expected value \(p_i\), -- \(t_i=p_i\) with probability 1; then they get a polynomial \(Y_H=\sum_{e\in \mathfrak E}w(e)\prod_{s\in e} t_s\). (Examples are given in the paper.) If \(E_0(H)\) is the expected value of \(Y_H\), then the authors prove that they are able to give the probability \(\text{Pr}(|Y_H-E_0(H)|>\alpha)\) for some \(\alpha\) which also depends on \(k\); this theorem is the main result of the paper. This means that they give a condition which guarantees that \(Y\) concentrates strongly around its mean when several variables could have a large effect on \(Y\). Therefore they introduce a computational model. The idea of the proof of the main result bases on induction on \(k\) and on the application of one of two lemmas (Theorem 2.2.2). Finally some applications on probabilistic combinatorics and random graphs are discussed.