Convergence law for random graphs with specified degree sequence
2003
The degree sequence of an n-vertex graph is d/sub 0/, ..., d/sub n - 1/, where each d/sub i/ is the number of vertices of degree i in the graph. A random graph with degree sequence d/sub 0/, ..., d/sub n - 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 /spl lambda/ /sub 0/, /spl lambda/ /sub 1/, ... be a sequence of nonnegative reals summing to 1. A class of finite graphs has degree sequences approximated by /spl lambda//sub 0/, /spl lambda//sub 1/, ... if, for every i and n, the members of the class of size n have /spl lambda//sub 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 /spl lambda//sub 0/, /spl lambda//sub 1/, .... With certain conditions on the sequence /spl lambda//sub 0/, /spl lambda//sub 1/, ..., the probability of any first-order sentence on random graphs of size n converges to a limit as n grows.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
41
References
0
Citations
NaN
KQI