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
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom