Asymptotic confirmation of the second neighborhood conjecture on inhomogeneous random graphs

Abstract

Abstract Seymour’s second neighborhood conjecture states that every oriented graph $$\vec {G}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> </mml:math> has a Seymour vertex, namely, $$\vec {G}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> </mml:math> 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_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> appears independently with probability $$p_n(e)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>e</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . 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 $$\vec {G}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> </mml:math> by assigning an orientation to each edge of G independently with equal probability, we prove that $$\vec {G}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> </mml:mover> </mml:math> contains a Seymour vertex with high probability across a broader range of regimes.