On robustly asymmetric graphs

O’Donnell, Wright, Wu and Zhou [SODA 2014] introduced the notion of robustly asymmetric graphs. Roughly speaking, these are graphs in which for every $0 \le \rho \le 1$,everypermutationthatpermutesa$\rho$ fraction of the vertices maps a $\mathrm{\Theta }(\rho )$ fraction of the edges to non-edges. We show that there are graphs for which the constant hidden in the $\mathrm{\Theta }$ notation is roughly~1.