38 citations · 74 across the 45 of their papers we have counts for
4 papers · 1 filter
Logical laws for short existential monadic second order sentences about graphs
Maksim Zhukovskii
In this paper, we study existential monadic second order (EMSO) properties of undirected graphs. In 2001, J.-M. Le Bars proved that there exists an EMSO sentence about undirected g…
On the First-Order Complexity of Induced Subgraph Isomorphism
Oleg Verbitsky, Maksim Zhukovskii
Given a graph , let be the class of graphs containing as an induced subgraph. Let denote the minimum such that is definable in -variable first-or…
Small subgraphs and their extensions in a random distance graph
A. V. Burkin, M. E. Zhukovskii
In previous papers, threshold probabilities for the properties of a random distance graph to contain strictly balanced graphs were found. We extend this result to arbitrary graphs…
First order sentences about random graphs: small number of alternations
Aleksandr Matushkin, Maksim Zhukovskii
Spectrum of a first order sentence is the set of all such that does not obey zero-one law w.r.t. this sentence. We have proved that the minimal number of quantif…