On robustly asymmetric graphs

Abstract

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 ρ\le 1$, every permutation that permutes a $ρ$ fraction of the vertices maps a $Θ(ρ)$ fraction of the edges to non-edges. We show that there are graphs for which the constant hidden in the $Θ$ notation is roughly~1.