Premium
Divide and conquer martingales and the number of triangles in a random graph
Author(s) -
Kim J. H.,
Vu V. H.
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10113
Subject(s) - random graph , struct , mathematics , martingale (probability theory) , combinatorics , random regular graph , graph , discrete mathematics , divide and conquer algorithms , computer science , line graph , algorithm , statistics , pathwidth , programming language
Abstract The goal of this paper is to present a novel application of a recent and useful martingale inequality. As an illustration, we prove an essentially sharp bound for the probability that a random graph contains significantly more triangles than expected. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004