Bounded quantifier depth spectra for random graphs

J. H. Spencer; M. E. Zhukovskii

doi:10.1016/j.disc.2016.01.005

Bounded quantifier depth spectra for random graphs

J. H. Spencer, M. E. Zhukovskii

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	1651-1664
Number of pages	14
Journal	Discrete Mathematics
Volume	339
Issue number	6
DOIs	https://doi.org/10.1016/j.disc.2016.01.005
State	Published - Jun 6 2016

Keywords

First-order logic
Random graphs
Spectra
Zero-one laws

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2016.01.005

Cite this

@article{828c776a7f3241f3bdc68de691742061,

title = "Bounded quantifier depth spectra for random graphs",

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.",

keywords = "First-order logic, Random graphs, Spectra, Zero-one laws",

author = "Spencer, {J. H.} and Zhukovskii, {M. E.}",

note = "Funding Information: This work was carried out with the support of the Russian Foundation for Basic Research Grant No. 13-01-00612 and by the Grant No. 15-01-03530 , grant of the Russian President MK-2184.2014.1. Publisher Copyright: {\textcopyright} 2016 Elsevier B.V. All rights reserved.",

year = "2016",

month = jun,

day = "6",

doi = "10.1016/j.disc.2016.01.005",

language = "English (US)",

volume = "339",

pages = "1651--1664",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Bounded quantifier depth spectra for random graphs

AU - Spencer, J. H.

AU - Zhukovskii, M. E.

N1 - Funding Information: This work was carried out with the support of the Russian Foundation for Basic Research Grant No. 13-01-00612 and by the Grant No. 15-01-03530 , grant of the Russian President MK-2184.2014.1. Publisher Copyright: © 2016 Elsevier B.V. All rights reserved.

PY - 2016/6/6

Y1 - 2016/6/6

N2 - 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.

AB - 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.

KW - First-order logic

KW - Random graphs

KW - Spectra

KW - Zero-one laws

UR - http://www.scopus.com/inward/record.url?scp=84958819011&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958819011&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2016.01.005

DO - 10.1016/j.disc.2016.01.005

M3 - Article

AN - SCOPUS:84958819011

SN - 0012-365X

VL - 339

SP - 1651

EP - 1664

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 6

ER -

Bounded quantifier depth spectra for random graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this