Zobrazeno 1 - 10
of 398
pro vyhledávání: '"Zhukovskii, M. A."'
Autor:
Malyshkin, Y. A., Zhukovskii, M. E.
We prove the monadic second order 0-1 law for two recursive tree models: uniform attachment tree and preferential attachment tree. We also show that the first order 0-1 law does not hold for non-tree uniform attachment models.
Externí odkaz:
http://arxiv.org/abs/2007.14768
We study the weak $K_s$-saturation number of the Erd\H{o}s--R\'{e}nyi random graph $\mathbbmsl{G}(n, p)$, denoted by $\mathrm{wsat}(\mathbbmsl{G}(n, p), K_s)$, where $K_s$ is the complete graph on $s$ vertices. Kor\'{a}ndi and Sudakov in 2017 proved
Externí odkaz:
http://arxiv.org/abs/2006.06855
Autor:
Kalinichenko, O., Zhukovskii, M.
Publikováno v:
In European Journal of Combinatorics December 2023 114
We prove that, for every $\ell\geq 4$, there exists an $\ell$-vertex graph and a first order sentence having a quantifier depth at most $\ell-1$ defining the property of having an induced subgraph isomorphic to the given one. We prove that a first or
Externí odkaz:
http://arxiv.org/abs/1902.03648
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
In this paper, we prove that for every positive $\varepsilon$, there exists an $\alpha\in(1/(k-1),1/(k-1)+\varepsilon)$ such that the binomial random graph $G(n,n^{-\alpha})$ does not obey 0-1 law w.r.t. first order sentences with k variables. In con
Externí odkaz:
http://arxiv.org/abs/1811.07026
Autor:
Burkin, A. V., Zhukovskii, M. E.
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 and prove that the number of copies of a strictly balanced graph has a
Externí odkaz:
http://arxiv.org/abs/1701.06917
Autor:
Demidovich, Yu.1 (AUTHOR) demidovich.yua@phystech.edu, Zhukovskii, M.2 (AUTHOR)
Publikováno v:
Journal of Graph Theory. Jul2023, Vol. 103 Issue 3, p451-461. 11p.
Autor:
Zhukovskii, M. E.
In this paper, we study spectra of first order properties of Erdos-Renyi random graph. We proved that minimal quantifier depth of a formula with an infinite spectrum is either 4 or 5.
Externí odkaz:
http://arxiv.org/abs/1609.01115