• DocumentCode
    2785128
  • Title

    Probabilities of sentences about very sparse random graphs

  • Author

    Lynch, James F.

  • Author_Institution
    Dept. of Math. & Comput. Sci., Clarkson Univ., Potsdam, NY, USA
  • fYear
    1990
  • fDate
    22-24 Oct 1990
  • Firstpage
    689
  • Abstract
    The author considers random graphs with edge probability βn-α, where n is the number of vertices of the graph, β>0 is fixed, and α=1 or α=( l+1)/l for some fixed positive integer l. It is proved that, for every first-order sentence, the probability that the sentence is true for the random graph has an asymptotic limit. Also, there is an effective procedure for generating the value of the limit in closed form
  • Keywords
    formal languages; graph theory; edge probability; first-order sentence; fixed positive integer; very sparse random graphs; Application software; Combinatorial mathematics; Computer science; Formal languages; Logic; Probability distribution;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
  • Conference_Location
    St. Louis, MO
  • Print_ISBN
    0-8186-2082-X
  • Type

    conf

  • DOI
    10.1109/FSCS.1990.89591
  • Filename
    89591