Concentration of multivariate polynomials and its applications
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.
- On the concentration of multivariate polynomials with small expectation
- Concentration for limited independence via inequalities for the elementary symmetric polynomials
- Anti-concentration for polynomials of independent random variables
- Combinatorial anti-concentration inequalities, with applications
- Concentration and moment inequalities for polynomials of independent random variables
- Random constructions and density results
- Triangle packings and 1-factors in oriented graphs
- On a. e. convergence of multivariate Kantorovich polynomials
- Concentration inequalities using the entropy method
- Upper tails for arithmetic progressions in random subsets
- Threshold functions and Poisson convergence for systems of equations in random sets
- De-anonymization of heterogeneous random graphs in quasilinear time
- On a refinement of Waring's problem
- Sandwiching random graphs: universality between random graph models
- Concentration inequalities for bounded functionals via log-Sobolev-type inequalities
- A sharp threshold for bootstrap percolation in a random hypergraph
- Dense sumsets of Sidon sequences
- Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients
- Upper tails via high moments and entropic stability
- Localization in random geometric graphs with too many edges
- On the missing log in upper tail estimates
- Upper tail bounds for stars
- A greedy algorithm for \(B_h[g]\) sequences
- A construction of small complete caps in projective spaces
- An inscribing model for random polytopes
- Finding large co-Sidon subsets in sets with a given additive energy
- Nonlinear large deviations
- Quasi-random multilinear polynomials
- On zero-sum free sequences contained in random subsets of finite cyclic groups
- The lower tail: Poisson approximation revisited
- Coloring sparse hypergraphs
- An introduction to large deviations for random graphs
- Anti-concentration for polynomials of independent random variables
- Freiman homomorphisms of random subsets of Z_N
- The missing log in large deviations for triangle counts
- When almost all sets are difference dominated
- Tight upper tail bounds for cliques
- A stronger bound for the strong chromatic index (extended abstract)
- Vertex Ramsey properties of randomly perturbed graphs
- On Sidon sets and asymptotic bases
- List Colouring Constants of Triangle Free Graphs
- Random points and lattice points in convex bodies
- scientific article; zbMATH DE number 3965308 (Why is no real title available?)
- On an anti-Ramsey threshold for random graphs
- Stationary distribution and cover time of random walks on random digraphs
- Colorful triangle counting and a \textsc{MapReduce} implementation
- On the concentration of multivariate polynomials with small expectation
- Concentration of non‐Lipschitz functions and applications
- The infamous upper tail
- On the size-Ramsey number of tight paths
- A stronger bound for the strong chromatic index
- Infinite Sidon sets contained in sparse random sets of integers
- Crossing numbers of random graphs
- On Sidon sets which are asymptotic bases of order \(4\)
- Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
- Combinatorial anti-concentration inequalities, with applications
- Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
- The Janson inequalities for general up-sets
- Stochastic load balancing on unrelated machines
- Sherali-Adams integrality gaps matching the log-density threshold
- Upper tail bounds for cycles
- The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
- On Komlós' tiling theorem in random graphs
- Probability bounds for polynomial functions in random variables
- Concentration inequalities for nonlinear matroid intersection
- On the method of typical bounded differences
- Concentration for noncommutative polynomials in random matrices
- Counting Independent Sets in Hypergraphs
- Concentration inequalities for nonlinear matroid intersection
- Concentration and moment inequalities for polynomials of independent random variables
- Joint Alignment from Pairwise Differences with a Noisy Oracle
- On Induced Paths, Holes, and Trees in Random Graphs
- Minimum rainbow \(H\)-decompositions of graphs
- Minimum rainbow \(H\)-decompositions of graphs
- A sequential algorithm for generating random graphs
- Evolving Shelah‐Spencer graphs
- Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
- Dynamic concentration of the triangle‐free process
- A randomized construction of high girth regular graphs
- Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- Deviation probabilities for arithmetic progressions and irregular discrete structures
- Concentration inequalities for some negatively dependent binary random variables
- Higher order concentration on Stiefel and Grassmann manifolds
- Average-case speedup for product formulas
- Resilience for tight Hamiltonicity
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- On \(B_h[1]\)-sets which are asymptotic bases of order \(2h\)
- On the threshold for Szemerédi's theorem with random differences
- A robust Corrádi-Hajnal theorem
- A note on the Cramér-Granville model
- Concentration of submodular functions and read-k families under negative dependence
- Sparse Hanson-Wright inequalities with applications
- Local central limit theorem for triangle counts in sparse random graphs
- On edge collapse of random simplicial complexes
- Coloring simple hypergraphs
- Partition universality for hypergraphs of bounded degeneracy and degree (extended abstract)
- High-girth Steiner triple systems
- More on Nosal's spectral theorem: books and 4-cycles
- When is the graph of a random 0/1 polytope a clique?
- Representation functions with prescribed rates of growth
- Sparse random graphs with many triangles
This page was built for publication: Concentration of multivariate polynomials and its applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5932644)
