On Anti-stochastic Properties of Unlabeled Graphs

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))/(n ln n), which is optimal up to factor of 2.