Bounded quantifier depth spectra for random graphs

J. H. Spencer, M. E. Zhukovskii

Research output: Contribution to journalArticlepeer-review

Abstract

For which α there are first order graph statements A of given quantifier depth k such that a Zero-One law does not hold for the random graph G(n,p(n)) with p(n) at or near (there are two notions) n? A fairly complete description is given in both the near dense (α near zero) and near linear (α near one) cases.

Original languageEnglish (US)
Pages (from-to)1651-1664
Number of pages14
JournalDiscrete Mathematics
Volume339
Issue number6
DOIs
StatePublished - Jun 6 2016

Keywords

  • First-order logic
  • Random graphs
  • Spectra
  • Zero-one laws

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Bounded quantifier depth spectra for random graphs'. Together they form a unique fingerprint.

Cite this