Asymptotic confirmation of the second neighborhood conjecture on inhomogeneous random graphs

Seymour’s second neighborhood conjecture states that every oriented graph has a Seymour vertex, namely, 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 appears independently with probability . 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 by assigning an orientation to each edge of G independently with equal probability, we prove that contains a Seymour vertex with high probability across a broader range of regimes.