Bounded quantifier depth spectrum for random uniform hypegraphs

2023/11/18 by Svetlana Popova, Popova, Svetlana
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.2311.11168

openalex publication_date 2023/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The notion of spectrum for first-order properties introduced by J. Spencer for Erdos-Renyi random graph is considered in relation to random uniform hypergraphs. In this work we study the set of limit points of the spectrum for first-order formulae with bounded quantifier depth and obtain bounds for its maximum value. Moreover, we prove zero-one k-laws for the random uniform hypergraph and improve the bounds for the maximum value of the spectrum for first-order formulae with bounded quantifier depth. We obtain that the maximum value of the spectrum belongs to some two-element set.

Related

• Spectrum for first-order properties of random hypergraphs
• On infinite spectra of first order properties of random graphs
• On the convergence of probabilities of the random graphs' properties expressed by first-order formulae with a bounded quantifier depth
• Adjacency Spectra of Random and Uniform Hypergraphs
• First order sentences about random graphs: small number of alternations