The Binomial Random Graph is a Bad Inducer

ABSTRACT For a finite graph and a value , let denote the largest for which there is a sequence of graphs of edge density approaching so that the induced ‐density of the sequence approaches . We show that for all on at least three vertices and all , the binomial random graph has induced ‐density strictly less than This provides a negative answer to a problem posed by Liu et al. (2023). Our approach is in the limiting setting of graphons, and we in fact show a stronger result: the binomial random graph is never a local maximum in the space of graphons of edge density . This is done by finding a sequence of balanced perturbations of arbitrarily small norm that increase the ‐density.