Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Eighteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2003)

Paper: Convergence Law for Random Graphs with Specified Degree Sequence (at LICS 2003)

Authors: James F. Lynch

Abstract

The degree sequence of an n-vertex graph is d, ..., d, where each d is the number of vertices of degree i in the graph. A random graph with degree sequence d, ..., d is a randomly selected member of the set of graphs on {0, ..., n-1} with that degree sequence, all choices being equally likely. Let \lambda, \lambda, ... be a sequence of nonnegative reals summing to 1. A class of finite graphs has degree sequences approximated by \lambda, \lambda, ... if, for every i and n, the members of the class of size n have lambdan + o(n) vertices of degree i. Our main result is a convergence law for random graphs with degree sequences approximated by some sequence \lambda, \lambda, .... With certain conditions on the sequence \lambda, \lambda, ..., the probability of any first-order sentence on random graphs of size n converges to a limit as n grows.

BibTeX

  @InProceedings{Lynch-ConvergenceLawforRa,
    author = 	 {James F. Lynch},
    title = 	 {Convergence Law for Random Graphs with Specified Degree Sequence},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2003)},
    year =	 {2003},
    month =	 {June}, 
    pages =      {301--310},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski