FACTOID # 14: North Carolina has a larger Native American population than North Dakota, South Dakota and Montana combined.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Random graph

In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs. Euclid, detail from The School of Athens by Raphael. ... A labeled graph with 6 vertices and 7 edges. ... Probability theory is the mathematical study of probability. ...

Contents


Random graph models

A random graph is obtained by starting with a set of n vertices and adding edges between them at random. Different random graph models produce different probability distributions on graphs. In mathematics, a probability distribution assigns to every interval of the real numbers a probability, so that the probability axioms are satisfied. ...


The most commonly studied model, called G(n,p), includes each possible edge independently with probability p. A closely related model, G(n,M) assigns equal probability to all graphs with exactly M edges. Both models can be viewed as snapshots at a particular time of the random graph process tilde{G}_n, which is a stochastic process that starts with n vertices and no edges and at each time unit adds one new edge chosen uniformly from the set of missing edges. In the mathematics of probability, a stochastic process is a random function. ...


We can also construct an object called an infinite random graph.


Consider a graph with vertices contained in a set X, as a binary relation R subset Xtimes X by defining R as: (a,b)in R if there is an edge between a and b. Conversely each symmetric relation R on Xtimes X gives rise to a graph on X.


A random graph is a graph R on an infinite set X satisfying the following properties:


i) R is irreflexive ii) R is symmetric iii) Given any n + m elements a_1,ldots, a_n,b_1,ldots, b_m in X there is cin X such that cin X is related to a_1,ldots, a_n, and c is not related to b_1,ldots, b_m.


It turns out that if the set X is countable there is a unique random graph up to isomorphism (that is any two countable random graphs are isomorphic). This is an example of an ω-categorical theory.


Properties of random graphs

The theory of random graphs studies typical properties of random graphs, those that hold with high probability for graphs drawn from a particular distribution. For example, we might ask for a given value of n and p what the probability is that G(n,p) is connected, meaning that it has a path between any two vertices. In studying such questions, random graph theorists often concentrate on the limit behavior of random graphs—the values that various probabilities converge to as n grows very large.


(threshold functions, evolution of G~)


Random graphs are widely used in the probabilistic method, where one tries to prove the existence of graphs with certain properties. The existence of a property on a random graph can be translated to the existence of the property on almost all graphs using the famous Szemerédi regularity lemma This article is not about probabilistic algorithms, which give the right answer with high probability but not with certainty, nor about Monte Carlo methods, which are simulations relying on pseudo-randomness. ... In mathematics, Szemerédis regularity lemma states that for every and every positive integer there is an integer such that every graph with vertices has an ε-regular partition into classes, Categories: Mathematics stubs | Graph theory | Lemmas ...


History

Random graphs were first defined by Paul Erdős and Alfréd Rényi in their 1959 paper "On Random Graphs I" published in Publ. Math. Debrecen 6, 290. Paul ErdÅ‘s, pictured in lecture, late in life. ... Alfréd Rényi (March 20, 1921 – February 1, 1970) was a Hungarian mathematician who made contributions in combinatorics and graph theory but mostly in probability theory. ...


(Erdos and Renyi, Bollobas)?


References

  • Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press

Béla Bollobás (born August 3, 1943 in Budapest, Hungary) is a leading Hungarian mathematician who has worked in functional analysis, and now specializes in combinatorics and graph theory. ...

See also


  Results from FactBites:
 
Random graph - Wikipedia, the free encyclopedia (448 words)
The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.
Random graphs are widely used in the probabilistic method, where one tries to prove the existence of graphs with certain properties.
Random graphs were first defined by Paul Erdős and Alfréd Rényi in their 1959 paper "On Random Graphs I" published in Publ.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m