On anti-stochastic properties of unlabeled graphs. (arXiv:2112.04395v2 [cs.DM] UPDATED)

We study vulnerability of a uniformly distributed random graph to an attack
by an adversary who aims for a global change of the distribution while being
able to make only a local change in the graph. We call a graph property \$A\$
anti-stochastic if the probability that a random graph \$G\$ satisfies \$A\$ is
small but, with high probability, there is a small perturbation transforming
\$G\$ into a graph satisfying \$A\$. While for labeled graphs such properties are
easy to obtain from binary covering codes, the existence of anti-stochastic
properties for unlabeled graphs is not so evident. If an admissible
perturbation is either the addition or the deletion of one edge, we exhibit an
anti-stochastic property that is satisfied by a random unlabeled graph of order
\$n\$ with probability \$(2+o(1))/n^2\$, which is as small as possible. We also
express another anti-stochastic property in terms of the degree sequence of a
graph. This property has probability \$(2+o(1))/(nln n)\$, which is optimal up
to factor of 2.

Go to Source of this post
Author Of this post: <a href="http://arxiv.org/find/cs/1/au:+Kiselev_S/0/1/0/all/0/1">Sergei Kiselev</a>, <a href="http://arxiv.org/find/cs/1/au:+Kupavskii_A/0/1/0/all/0/1">Andrey Kupavskii</a>, <a href="http://arxiv.org/find/cs/1/au:+Verbitsky_O/0/1/0/all/0/1">Oleg Verbitsky</a>, <a href="http://arxiv.org/find/cs/1/au:+Zhukovskii_M/0/1/0/all/0/1">Maksim Zhukovskii</a>