On isomorphism-invariant antistochastic properties of random graphs (Q6654120)

This paper considers a class of graph properties which are defined as anti-stochastic. A graph property (that is, a subset of graphs on a given vertex set that is closed under automorphisms) is called anti-stochastic if it does not hold with high probability among the set of graphs on \(n\) vertices (selected uniformly at random), and there is a function on this set of graph which modifies only one pair of vertices and, thereafter, the property holds with high probability as \(n \to \infty\). This function can be thought of as an adversary who makes a local change which results in the destruction of the property. The first result of the paper shows that there is such a property that occurs with probability \(\sim 2/n^2\). (Note that a property with an asymptotically smaller probability of occurrence cannot be anti-stochastic.) They also deduce this for the anti-stochastic properties of unlabelled graphs. The construction of this anti-stochastic property (for the labelled case) relies on covering codes with optimal density. Roughly speaking, such a code is identified with a set of labelled graphs and its closure under taking isomorphisms. The issue with this approach is that the property that will be created will not occur with low probability and hence the set of graphs needs to be sparsified, with the use of a certain construction. The authors also construct another anti-stochastic property that is expressed in terms of the degree sequence - this occurs with probability \(\sim 2/(n\ln n)\). Moreover, they show that every such anti-stochastic property holds with probability at least \(\sim 1/(n\ln n)\).