You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
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.
[1] Bhamidi, S., Bresler, G. and Sly, A. (2008). Mixing time of exponential random graphs. In 2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 803-12.
[2] Bolloba´s B. and Riordan, O. (2009). Metrics for sparse graphs. In S. Huczynska, J. D. Mitchell, and C. M. Roney-Dougal, eds., Surveys in combinatorics 2009, pp. 211-287, London Math. Soc. Lecture Note Ser. 365, Cambridge University Press, Cambridge.
[4] Borgs, C., Chayes, J., Lova´sz, L., So´s, V. T. and Vesztergombi, K. (2008). Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing. Adv. Math., 219 no. 6, 1801-1851.
[5] Borgs, C., Chayes, J., Lova´sz, L., So´s, V. T. and Vesztergombi, K. (2012). Convergent sequences of dense graphs. II. Multiway cuts and statistical physics. Ann. Math. (2), 176 no. 1, 151-219.
[6] Carinci, G., Chazottes, J.-R., Giardina`, C. and Redig, F. (2013). Nonconventional averages along arithmetic progressions and lattice spin systems. arXiv preprint.
[7] Chatterjee, S. (2005). Concentration inequalities with exchangeable pairs. Ph.D. thesis, Stanford University.
[13] Chatterjee, S. and Varadhan, S. R. S. (2012). Large deviations for random matrices. Commun. Stoch. Anal., 6 no. 1, 1-13.
[14] DeMarco, B. and Kahn, J. (2012). Upper tails for triangles. Random Structures Algorithms, 40 no. 4, 452-459.
[15] DeMarco, B. and Kahn, J. (2012). Tight upper tail bounds for cliques. Random Structures Algorithms, 41 no. 4, 469-487.
[16] Dembo, A. and Zeitouni, O. (2010). Large deviations techniques and applications. Corrected reprint of the second (1998) edition. Springer-Verlag, Berlin.
[17] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Stat. Assoc. 58 13-30.
[18] Janson, S., Oleszkiewicz, K. and Rucin´ski, A. (2004). Upper tails for subgraph counts in random graphs. Israel J. Math., 142, 61-92.
[19] Janson, S. and Rucin´ski, A. (2002). The infamous upper tail. Probabilistic methods in combinatorial optimization. Random Structures Algorithms, 20 no. 3, 317-342.
[20] Janson, S. and Rucin´ski, A. (2004). The deletion method for upper tail estimates. Combinatorica, 24 no. 4, 615-640.
[24] Kim, J. H. and Vu, V. H. (2004). Divide and conquer martingales and the number of triangles in a random graph. Random Structures Algorithms, 24 no. 2, 166-174.
[28] McDiarmid, C. (1989). On the method of bounded differences. In Surveys in combinatorics, 148-188, London Math. Soc. Lecture Note Ser., 141, Cambridge Univ. Press, Cambridge.
[29] Szemer´edi, E. (1978). Regular partitions of graphs. Probl`emes combinatoires et th´eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), pp. 399- 401, Colloq. Internat. CNRS, 260, CNRS, Paris.
[30] Talagrand, M. (1995). Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes E´tudes Sci. Publ. Math. 81 73-205.
[31] Tao, T. and Vu, V. H. (2006). Additive combinatorics. Cambridge University Press.
[32] Vu, V. H. (2001). A large deviation result on the number of small subgraphs of a random graph. Combin. Probab. Comput., 10 no. 1, 79-94.
[33] Vu, V. H. (2002). Concentration of non-Lipschitz functions and applications. Probabilistic methods in combinatorial optimization. Random Structures Algorithms, 20 no. 3, 262-316.