Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-14T09:42:12.781Z Has data issue: false hasContentIssue false
  • English
  • Français

Sub-Gaussian Tails for the Number of Triangles in G(n, p)

Published online by Cambridge University Press:  14 May 2010

GUY WOLFOVITZ
GUY WOLFOVITZ*
Affiliation:
Department of Computer Science, Haifa University, Haifa, Israel (e-mail: gwolfovi@cs.haifa.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let X be the random variable that counts the number of triangles in the binomial random graph G(n, p). We show that for some positive constant c, the probability that X deviates from its expectation by at least λVar(X)1/2 is at most e−cλ2, provided p = o(1), λ = ω($\sqrt{\ln n}$) and λ ≤ (n3p3 + n4p5)1/6.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 1 , January 2011, pp. 155 - 160
Copyright
Copyright © Cambridge University Press 2010

References

[1]Bollobás, B. (1981) Threshold functions for small subgraphs. Math. Proc. Cambridge Philos. Soc. 90 197–206.CrossRefGoogle Scholar
[2]Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 17–61.Google Scholar
[3]Frieze, A. (1992) On small subgraphs of random graphs. In Random Graphs 2 (Poznań 1989), Wiley-Interscience, pp. 67–90.Google Scholar
[4]Janson, S., Łuczak, T. and Ruciński, A. (1990) An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. In Random Graphs '87 (Poznań 1987), Wiley, pp. 73–87.Google Scholar
[5]Janson, S., Oleszkiewicz, K. and Ruciński, A. (2004) Upper tails for subgraph counts in random graphs. Israel J. Math. 142 61–92.Google Scholar
[6]Janson, S. and Ruciński, A. (2002) The infamous upper tail. Random Struct. Alg. 20 317–342.Google Scholar
[7]Kannan, R. (2008) A new probability inequality using typical moments and concentration results. arXiv:0809.2477v2 [math.PR].Google Scholar
[8]Karoński, M. and Ruciński, A. (1983) On the number of strictly balanced subgraphs of a random graph. In Graph Theory (Łagów 1981), Vol. 1018 of Lecture Notes in Mathematics, Springer, pp. 79–83.Google Scholar
[9]Kim, J. H. and Vu, V. H. (2004) Divide and conquer martingales and the number of triangles in a random graph. Random Struct. Alg. 24 166–174.CrossRefGoogle Scholar
[10]McDiarmid, C. (1989) On the method of bounded differences. In Surveys in Combinatorics (Norwich 1989), Vol. 141 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 148–188.Google Scholar
[11]Ruciński, A. (1988) When are small subgraphs of a random graph normally distributed? Probab. Theory Rel. Fields 78 1–10.CrossRefGoogle Scholar
[12]Schürger, K. (1979) Limit theorems for complete subgraphs of random graphs. Period. Math. Hungar. 10 47–53.Google Scholar
[13]Vu, V. H. (2001) A large deviation result on the number of small subgraphs of a random graph. Combin. Probab. Comput. 10 79–94.CrossRefGoogle Scholar
[14]Vu, V. H. (2002) Concentration of non-Lipschitz functions and applications. Random Struct. Alg. 20 262–316.Google Scholar