Ups and downs of first order sentences on random graphs

Joel Spencer, Gábor Tardos

Research output: Contribution to journalArticlepeer-review

Abstract

Shelah and Spencer [1] proved that the zero-one law holds for the first order sentences on random graphs G(n,n) whenever α is a fixed positive irrational. This raises the question what zero-one valued functions on the positive irrationals arise as the limit probability of a first order sentence on these graphs. Here we prove two necessary conditions on these functions, a number-theoretic and a complexity condition. We hope to prove in a subsequent paper that these conditions together with two simpler and previously proved conditions are also sufficient and thus they constitute a characterization.

Original languageEnglish (US)
Pages (from-to)263-280
Number of pages18
JournalCombinatorica
Volume20
Issue number2
DOIs
StatePublished - 2000

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Ups and downs of first order sentences on random graphs'. Together they form a unique fingerprint.

Cite this