Spectrum of FO logic with quantifier depth 4 is finite

2021/11/22 by Yury Yarovikov, Yarovikov, Yury, Maksim Zhukovskii +1
Computer Science · Engineering · #Advanced Algebra and Logic #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2111.11470

openalex publication_date 2021/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The k-spectrum is the set of all α>0 such that G(n,n^-α) does not obey the 0-1 law for FO sentences with quantifier depth at most k. In this paper, we prove that the minimum k such that the k-spectrum is infinite equals 5.

Related

• On the variable hierarchy of first-order spectra
• Zero-one laws for existential first order sentences of bounded quantifier depth
• From Quantifier Depth to Quantifier Number: Separating Structures with k Variables
• First order sentences about random graphs: small number of alternations
• Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman\n Refinement Steps