Nonlinear large deviations

作者：Chatterjee Sourav^*; Dembo Amir

来源：Advances in Mathematics, 2016, 299: 396-450.

DOI：10.1016/j.aim.2016.05.017

• Large deviations
• Sparse random graphs
• Regularity lemma
• Arithmetic progressions
• Exponential random graph models
• Concentration of measure

We present a general technique for computing large deviations of nonlinear functions of independent Bernoulli random variables. The method is applied to compute the large deviation rate functions for subgraph counts in sparse random graphs. Previous technology, based on Szemeredi's regularity lemma, works only for dense graphs. Applications are also made to exponential random graphs and three-term arithmetic progressions in random sets of integers.

• 出版日期2016-8-20