Properties of Random Graphs -- Subgraph Containment

 

Title: Properties of Random Graphs -- Subgraph Containment
Author: Lars Hupel
Submission date: 2014-02-13
Abstract: Random graphs are graphs with a fixed number of vertices, where each edge is present with a fixed probability. We are interested in the probability that a random graph contains a certain pattern, for example a cycle or a clique. A very high edge probability gives rise to perhaps too many edges (which degrades performance for many algorithms), whereas a low edge probability might result in a disconnected graph. We prove a theorem about a threshold probability such that a higher edge probability will asymptotically almost surely produce a random graph with the desired subgraph.
BibTeX:
@article{Random_Graph_Subgraph_Threshold-AFP,
  author  = {Lars Hupel},
  title   = {Properties of Random Graphs -- Subgraph Containment},
  journal = {Archive of Formal Proofs},
  month   = feb,
  year    = 2014,
  note    = {\url{http://isa-afp.org/entries/Random_Graph_Subgraph_Threshold.shtml},
            Formal proof development},
  ISSN    = {2150-914x},
}
License: BSD License
Depends on: Girth_Chromatic