arXiv
Open Access
2014
On robustly asymmetric graphs
Uriel Feige
Abstrak
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.
Penulis (1)
U
Uriel Feige
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2014
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓