Zobrazeno 1 - 10
of 494
pro vyhledávání: '"A. P. Zhukovskii"'
Autor:
Verbitsky, Oleg, Zhukovskii, Maksim
We show that if $p=O(1/n)$, then the Erd\H{o}s-R\'{e}nyi random graph $G(n,p)$ with high probability admits a canonical labeling computable in time $O(n\log n)$. Combined with the previous results on the canonization of random graphs, this implies th
Externí odkaz:
http://arxiv.org/abs/2409.18109
We prove that the density of any covering single-insertion code $C\subseteq X^r$ over the $n$-symbol alphabet $X$ cannot be smaller than $1/r+\delta_r$ for some positive real $\delta_r$ not depending on $n$. This improves the volume lower bound of $1
Externí odkaz:
http://arxiv.org/abs/2409.06425
We say that a vertex $v$ in a connected graph $G$ is decisive if the numbers of walks from $v$ of each length determine the graph $G$ rooted at $v$ up to isomorphism among all connected rooted graphs with the same number of vertices. On the other han
Externí odkaz:
http://arxiv.org/abs/2409.03690
Asymptotic behaviour of maximum sizes of induced trees and forests has been studied extensively in last decades, though the overall picture is far from being complete. In this paper, we close several significant gaps: 1) We prove $2$-point concentrat
Externí odkaz:
http://arxiv.org/abs/2408.15215
Autor:
Terekhov, Nikolai, Zhukovskii, Maksim
Given a graph $F$ and a positive integer $n$, the weak $F$-saturation number $\mathrm{wsat}(K_n,F)$ is the minimum number of edges in a graph $H$ on $n$ vertices such that the edges missing in $H$ can be added, one at a time, so that every edge creat
Externí odkaz:
http://arxiv.org/abs/2405.17857
Autor:
Hershko, Tal, Zhukovskii, Maksim
We study the problem of distinguishing between two independent samples $\mathbf{G}_n^1,\mathbf{G}_n^2$ of a binomial random graph $G(n,p)$ by first order (FO) sentences. Shelah and Spencer proved that, for a constant $\alpha\in(0,1)$, $G(n,n^{-\alpha
Externí odkaz:
http://arxiv.org/abs/2405.09146
Let $K^r_n$ be the complete $r$-uniform hypergraph on $n$ vertices, that is, the hypergraph whose vertex set is $[n]:=\{1,2,...,n\}$ and whose edge set is $\binom{[n]}{r}$. We form $G^r(n,p)$ by retaining each edge of $K^r_n$ independently with proba
Externí odkaz:
http://arxiv.org/abs/2405.03061
We estimate the minimum number of distance queries that is sufficient to reconstruct the binomial random graph $G(n,p)$ with constant diameter with high probability. We get a tight (up to a constant factor) answer for all $p>n^{-1+o(1)}$ outside "thr
Externí odkaz:
http://arxiv.org/abs/2404.18318
We prove that the family of largest cuts in the binomial random graph exhibits the following stability property: If $1/n \ll p = 1-\Omega(1)$, then, with high probability, there is a set of $n - o(n)$ vertices that is partitioned in the same manner b
Externí odkaz:
http://arxiv.org/abs/2402.14620
Autor:
Demin, Danila, Zhukovskii, Maksim
For a sequence of random structures with $n$-element domains over a relational signature, we define its first order (FO) complexity as a certain subset in the Banach space $\ell^{\infty}/c_0$. The well-known FO zero-one law and FO convergence law cor
Externí odkaz:
http://arxiv.org/abs/2402.02567