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.html}, Formal proof development}, ISSN = {2150-914x}, }
License:	BSD License
Depends on:	Girth_Chromatic
Status: [ok]	This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.