The Binomial Random Graph is a Bad Inducer

ABSTRACT For a finite graph $$ F $$ and a value $$ p\in \left[0,1\right] $$, let $$ I\left(F,p\right) $$ denote the largest $$ y $$ for which there is a sequence of graphs of edge density approaching $$ p $$ so that the induced $$ F $$-density of the sequence approaches $$ y $$. We show that for all $$ F $$ on at least three vertices and all $$ p\in \left(0,1\right) $$, the binomial random graph $$ G\left(n,p\right) $$ has induced $$ F $$-density strictly less than $$ I\left(F,p\right). $$ 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 $$ p $$. This is done by finding a sequence of balanced perturbations of arbitrarily small norm that increase the $$ F $$-density.

Duke Scholars

Author Fan Wei Mathematics