Asymptotic confirmation of the second neighborhood conjecture on inhomogeneous random graphs

Seymour’s second neighborhood conjecture states that every oriented graph G⃗ G → has a Seymour vertex, namely, G⃗ G → has a vertex whose second-order out-neighborhood is at least as large as its first-order out-neighborhood. In this paper, we approach the conjecture by considering an inhomogeneous random graph G , where each edge e in the complete graph Kₙ K n appears independently with probability pₙ(e) p n ( e ) . Under suitable density and regularity conditions, we show that every orientation of G contains a Seymour vertex with high probability, confirming the conjecture asymptotically. Moreover, if we consider an inhomogeneous random oriented graph G⃗ G → by assigning an orientation to each edge of G independently with equal probability, we prove that G⃗ G → contains a Seymour vertex with high probability across a broader range of regimes.