DocumentCode :
1616139
Title :
Convergence law for random graphs with specified degree sequence
Author :
Lynch, James F.
Author_Institution :
Dept. of Math. & Comput. Sci., Clarkson Univ., Potsdam, NY, USA
fYear :
2003
Firstpage :
301
Lastpage :
310
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Logic in Computer Science, 2003. Proceedings. 18th Annual IEEE Symposium on
ISSN :
1043-6871
Print_ISBN :
0-7695-1884-2
Type :
conf
DOI :
10.1109/LICS.2003.1210070
Filename :
1210070
Link To Document :
بازگشت