Concentration of multivariate polynomials and its applications (Q5932644): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q105584599 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s004930070014 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2077204415 / rank | |||
Normal rank |
Latest revision as of 19:21, 19 March 2024
scientific article; zbMATH DE number 1603950
Language | Label | Description | Also known as |
---|---|---|---|
English | Concentration of multivariate polynomials and its applications |
scientific article; zbMATH DE number 1603950 |
Statements
Concentration of multivariate polynomials and its applications (English)
0 references
12 June 2001
0 references
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.
0 references
probability and random variables
0 references
multivariate polynomials
0 references
hypergraphs and subhypergraphs
0 references
random graphs
0 references