Cover Image

Spectrum of FO logic with quantifier depth 4 is finite

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Yarovikov, Yury, Zhukovskii, Maksim
Format:	Preprint
Published:	2021
Subjects:	Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A logical approach to concentration
by: Benedikt, Michael, et al.
Published: (2026)

A very sharp threshold for first order logic distinguishability of random graphs
by: Benjamini, Itai, et al.
Published: (2022)

Sharp thresholds for spanning regular subgraphs
by: Zhukovskii, Maksim
Published: (2025)

Majority dynamics on finite trees
by: Benjamini, Itai, et al.
Published: (2025)

First order complexity of finite random structures
by: Demin, Danila, et al.
Published: (2024)

Non-isomorphic subgraphs in random graphs
by: Krivelevich, Michael, et al.
Published: (2025)

Weak saturation rank: a failure of linear algebraic approach to weak saturation
by: Terekhov, Nikolai, et al.
Published: (2024)

Reconstructing random graphs from distance queries
by: Krivelevich, Michael, et al.
Published: (2024)

Maximum chordal subgraphs of random graphs
by: Krivelevich, Michael, et al.
Published: (2023)

Canonical labelling of sparse random graphs
by: Verbitsky, Oleg, et al.
Published: (2024)

On the maximum number of common neighbours in dense random regular graphs
by: Isaev, Mikhail, et al.
Published: (2023)

Weak saturation numbers of large complete bipartite graphs
by: Akhmejanova, Margarita, et al.
Published: (2025)

Maximum induced trees and forests of bounded degree in random graphs
by: Akhmejanova, Margarita, et al.
Published: (2024)

First order distinguishability of sparse random graphs
by: Hershko, Tal, et al.
Published: (2024)

Tree tilings in random regular graphs
by: Diskin, Sahar, et al.
Published: (2024)

A Jump of the Saturation Number in Random Graphs?
by: Diskin, Sahar, et al.
Published: (2023)

Stability of large cuts in random graphs
by: Hoshen, Ilay, et al.
Published: (2024)

New bounds for the optimal density of covering single-insertion codes via the Turán density
by: Pikhurko, Oleg, et al.
Published: (2024)

Sums along the edges of bounded degree graphs
by: Alon, Noga, et al.
Published: (2025)

A large hole in pseudo-random graphs
by: Diskin, Sahar, et al.
Published: (2025)

Gathering Information about a Graph by Counting Walks from a Single Vertex
by: Fuhlbrück, Frank, et al.
Published: (2024)

Extremal independence in discrete random systems
by: Isaev, Mikhail, et al.
Published: (2021)

On the threshold for triangulations inside convex polygons
by: Kolesnik, Brett, et al.
Published: (2025)

Saturation in Random Hypergraphs
by: Diskin, Sahar, et al.
Published: (2024)

Functionality of Random Graphs
by: Sylvester, John, et al.
Published: (2024)

Sprinkling with random regular graphs
by: Isaev, Mikhail, et al.
Published: (2023)

When does a tree activate the random graph?
by: Antonir, Asaf Cohen, et al.
Published: (2025)

Faces in girth-saturated graphs on surfaces
by: Axenovich, Maria, et al.
Published: (2024)

Canonical labelling of random regular graphs
by: Isaev, Mikhail, et al.
Published: (2026)

Modeling FO-limits for monadically stable sequences
by: Braunfeld, S., et al.
Published: (2025)

Diameter and mixing time of the giant component in the percolated hypercube
by: Anastos, Michael, et al.
Published: (2025)

On the primitive subspace of Lando framed graph bialgebra
by: Karev, Maksim
Published: (2023)

Tight bounds on adjacency labels for monotone graph classes
by: Bonnet, Édouard, et al.
Published: (2023)

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
by: Bonnet, Édouard, et al.
Published: (2023)

The critical activation density in graph bootstrap percolation
by: Kolesnik, Brett, et al.
Published: (2026)

On the construction of frieze patterns from partitions of convex polygons by nonintersecting diagonals
by: Kochetkov, Yury
Published: (2025)

On one property of Catalan numbers
by: Kochetkov, Yury
Published: (2025)

Combinatorics of generic 5-degree polynomials
by: Kochetkov, Yury
Published: (2024)

Minimal triangulations of circle bundles
by: Panina, Gaiane, et al.
Published: (2023)

The sl(2)-weight system at c = 3/8 for graphs
by: Fomichev, Daniil, et al.
Published: (2024)