38 citations · 74 across the 45 of their papers we have counts for
7 papers · 1 filter
Zero-one laws for k-variable first-order logic of sparse random graphs
A. S. Razafimahatratra, M. Zhukovskii
In this paper, we prove that for every positive , there exists an such that the binomial random graph does not obey 0…
Existential monadic second order convergence law fails on sparse random graphs
Alena Egorova, Maksim Zhukovskii
In the paper, we prove that existential monadic second order convergence law fails for the binomial random graph for every .
On monotonicity of Ramanujan function for binomial random variables
Daniil Dmitriev, Maksim Zhukovskii
For a binomial random variable with parameters and , it is well known that the median equals when is an integer. In 1968, Jogdeo and Samuels studied the behavi…
Existential monadic second order logic of undirected graphs: a disproof of the Le Bars conjecture
Svetlana Popova, Maksim Zhukovskii
In 2001, J.-M. Le Bars disproved the zero-one law (that says that every sentence from a certain logic is either true asymptotically almost surely (a.a.s.), or false a.a.s.) for exi…
The distribution of the maximum number of common neighbors in the random graph
Igor Rodionov, Maksim Zhukovskii
Let be the maximum number of common neighbors of a set of vertices in . In this paper, we find and such that converges i…
Upper bound for the minimal quantifier depth of the first part of a monadic second-order sentence without asymptotic probability
Mickel González Sánchez, Maksim Evgenievich Zhukovskii
In this paper we found an upper bound for the minimal quantifier depth of the first part of a monadic second-order sentence without asymptotic probability described by Jerzy Tyszki…
Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism
Oleg Verbitsky, Maksim Zhukovskii
Let denote the number of vertices in a fixed connected pattern graph . We show an infinite family of patterns such that the existence of a subgraph isomorphic to …