RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2018 Volume 54, Issue 3, Pages 92–101 (Mi ppi2276)

This article is cited in 3 papers

Large Systems

Infinite spectra of first-order properties for random hypergraphs

S. N. Popova

Moscow Institute of Physics and Technology (State University), Moscow, Russia

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.

UDC: 621.391.1:519.1

Received: 07.10.2017
Revised: 29.04.2018


 English version:
Problems of Information Transmission, 2018, 54:3, 281–289

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024