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>

By admin