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
      0 references
      0 references
      29 March 2004
      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

      Identifiers