🔖 On random graphs by Paul ErdÅ‘s and Alfréd Rényi (1959)

Bookmarked On Random Graphs. I by Paul Erdős and Alfréd Rényi (Publicationes Mathematicae. 6: 290–297.)

Original source of Erdős–Rényi model.

In the mathematical field of graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs. They are named after mathematicians Paul Erdős and Alfréd Rényi, who first introduced one of the models in 1959,[1][2] while Edgar Gilbert introduced the other model contemporaneously and independently of Erdős and Rényi.[3] In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely; in the model introduced by Gilbert, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

hat tip: Linked: The New Science Of Networks by Albert-László Barabási

Published by

Chris Aldrich

I'm a biomedical and electrical engineer with interests in information theory, complexity, evolution, genetics, signal processing, IndieWeb, theoretical mathematics, and big history. I'm also a talent manager-producer-publisher in the entertainment industry with expertise in representation, distribution, finance, production, content delivery, and new media.

Leave a Reply

Your email address will not be published. Required fields are marked *