Robust hamiltonicity of random directed graphs

Asaf Ferber, Rajko Nenadov, Andreas Noever +2

In his seminal paper from 1952 Dirac showed that the complete graph on $n\ge 3$ vertices remains Hamiltonian even if we allow an adversary to remove $\lfloor n/2\rfloor$ edges tou…