On the spectra of first-order language properties for random graphs

J. H. Spencer; M. E. Zhukovskii

doi:10.1134/S1064562415040304

On the spectra of first-order language properties for random graphs

J. H. Spencer, M. E. Zhukovskii

Research output: Contribution to journal › Article › peer-review

Abstract

We found the maximum and the minimum number in the spectra of the first-order formula with a quantifier depth of at most k. Moreover, we obtain the upper bounds on the mimimal limit points in the spectra and the lower bounds on the maximum limit points in the spectra.

Original language	English (US)
Pages (from-to)	503-506
Number of pages	4
Journal	Doklady Mathematics
Volume	92
Issue number	1
DOIs	https://doi.org/10.1134/S1064562415040304
State	Published - Jul 10 2015

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.1134/S1064562415040304

Cite this

@article{83d9b733983b41d590b3a67181ac55f5,

title = "On the spectra of first-order language properties for random graphs",

abstract = "We found the maximum and the minimum number in the spectra of the first-order formula with a quantifier depth of at most k. Moreover, we obtain the upper bounds on the mimimal limit points in the spectra and the lower bounds on the maximum limit points in the spectra.",

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

note = "Publisher Copyright: {\textcopyright} 2015, Pleiades Publishing, Ltd.",

year = "2015",

month = jul,

day = "10",

doi = "10.1134/S1064562415040304",

language = "English (US)",

volume = "92",

pages = "503--506",

journal = "Doklady Mathematics",

issn = "1064-5624",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "1",

}

TY - JOUR

T1 - On the spectra of first-order language properties for random graphs

AU - Spencer, J. H.

AU - Zhukovskii, M. E.

PY - 2015/7/10

Y1 - 2015/7/10

N2 - We found the maximum and the minimum number in the spectra of the first-order formula with a quantifier depth of at most k. Moreover, we obtain the upper bounds on the mimimal limit points in the spectra and the lower bounds on the maximum limit points in the spectra.

AB - We found the maximum and the minimum number in the spectra of the first-order formula with a quantifier depth of at most k. Moreover, we obtain the upper bounds on the mimimal limit points in the spectra and the lower bounds on the maximum limit points in the spectra.

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

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

U2 - 10.1134/S1064562415040304

DO - 10.1134/S1064562415040304

M3 - Article

AN - SCOPUS:84941045005

VL - 92

SP - 503

EP - 506

JO - Doklady Mathematics

JF - Doklady Mathematics

SN - 1064-5624

IS - 1

ER -

On the spectra of first-order language properties for random graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this