Seymour’s Second Neighborhood Conjecture on sparse random graphs - Botler, Fábio; Moura, Phablo; Naia, Tássio (Anais do Encontro de Teoria da Computação (ETC), 2022)
Seymour’s Second Neighborhood Conjecture (SNC) says that every oriented graph contains a vertex whose second neighborhood is at least as large as its first neighborhood. We prove that asymptotically almost surely (a.a.s.) every orientation of the binomial random graph G(n, p) satisfies the SNC if n 4 p 6 → 0. We also show that if p ∈ (0, 2/3), then a.a.s. a uniformly-random orientation of G(n, p) satisfies the SNC, settling it for almost every labeled oriented graph.