2014/02/05 by Uriel Feige, Feige, Uriel
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.1402.1047
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 ≤ ρ≤ 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.