Author_Institution :
Dept. of Math. & Comput. Sci., Clarkson Univ., Potsdam, NY, USA
Abstract :
The degree sequence of an n-vertex graph is d0, ..., dn - 1, where each di is the number of vertices of degree i in the graph. A random graph with degree sequence d0, ..., dn - 1 is a randomly selected member of the set of graphs on {0, ..., n - 1} with that degree sequence, all choices being equally likely. Let λ 0, λ 1, ... be a sequence of nonnegative reals summing to 1. A class of finite graphs has degree sequences approximated by λ0, λ1, ... if, for every i and n, the members of the class of size n have λi n + o(n) vertices of degree i. Our main result is a convergence law for random graphs with degree sequences approximated by some sequence λ0, λ1, .... With certain conditions on the sequence λ0, λ1, ..., the probability of any first-order sentence on random graphs of size n converges to a limit as n grows.
Keywords :
convergence; graph theory; probability; theorem proving; convergence law; degree sequence; first-order sentence probability; n-vertex; random graph; Biological system modeling; Collaboration; Computer science; Convergence; Diseases; IP networks; Internet telephony; Power engineering and energy; Power systems; Sociology;