Divide and conquer martingales and the number of triangles in a random graph (Q4459588)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2062667
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Divide and conquer martingales and the number of triangles in a random graph |
scientific article; zbMATH DE number 2062667 |
Statements
Divide and conquer martingales and the number of triangles in a random graph (English)
0 references
29 March 2004
0 references
0.7632161378860474
0 references
0.7575646638870239
0 references
0.7562886476516724
0 references
This paper deals with a martingale method often used in probabilistic combinatorics. A simple version of it is related to the \(\sigma\)-fields generated by a collection of \(m\) independent and identically distributed binary random variables \(\tau_i\), \(i= 1,\dots, m\). For \(\tau= (\tau_1,\dots,\tau_m)\) we let \(Y= Y(\tau)\) to denote a random variable depending on \(\tau\). The method is based on upper bounds for probabilities of the type \(P(| Y- E(Y)|\geq \text{const})\). The error terms there involve the difference \[ C_i(\tau)=| E(Y\mid\tau_1,\dots, \tau_{i-1},\tau_i= 1)- E(Y\mid \tau_1,\dots, \tau_{i-1},\tau_i= 0)|. \] This method is usually applied to combinatorial problems in which \(C_i(\tau)\) turns out to be either unbounded or crudely bounded. The authors illustrate its power deriving an essentially sharp bound for the probability that a random graph contains significantly more triangles than expected.
0 references