Email this article Infinite Spectra of First-Order Properties for Random Hypergraphs
- Authors: Popova S.N.1
-
Affiliations:
- Moscow Institute of Physics and Technology (State University)
- Issue: Vol 54, No 3 (2018)
- Pages: 281-289
- Section: Large Systems
- URL: https://journal-vniispk.ru/0032-9460/article/view/166542
- DOI: https://doi.org/10.1134/S0032946018030079
- ID: 166542
Cite item
Open Access
Access granted
Subscription Access
Abstract
We study the asymptotic behavior of probabilities of first-order properties for random uniform hypergraphs. In 1990, J. Spencer introduced the notion of a spectrum for graph properties and proved the existence of a first-order property with an infinite spectrum. In this paper we give a definition of a spectrum for properties of uniform hypergraphs and establish an almost tight bound for the minimum quantifier depth of a first-order formula with infinite spectrum.
About the authors
S. N. Popova
Moscow Institute of Physics and Technology (State University)
Author for correspondence.
Email: popovaclaire@mail.ru
Russian Federation, Moscow
Supplementary files
