Asymptotic confirmation of the second neighborhood conjecture on inhomogeneous random graphs

Abstract

<jats:p> Seymour’s second neighborhood conjecture states that every oriented graph <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\vec {G}$$</jats:tex-math> <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> </jats:alternatives> </jats:inline-formula> has a Seymour vertex, namely, <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\vec {G}$$</jats:tex-math> <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> </jats:alternatives> </jats:inline-formula> 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 <jats:italic>G</jats:italic> , where each edge <jats:italic>e</jats:italic> in the complete graph <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$K_n$$</jats:tex-math> <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> </jats:alternatives> </jats:inline-formula> appears independently with probability <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$p_n(e)$$</jats:tex-math> <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> </jats:alternatives> </jats:inline-formula> . Under suitable density and regularity conditions, we show that every orientation of <jats:italic>G</jats:italic> contains a Seymour vertex with high probability, confirming the conjecture asymptotically. Moreover, if we consider an inhomogeneous random oriented graph <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\vec {G}$$</jats:tex-math> <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> </jats:alternatives> </jats:inline-formula> by assigning an orientation to each edge of <jats:italic>G</jats:italic> independently with equal probability, we prove that <jats:inline-formula> <jats:alternatives> <jats:tex-math>$$\vec {G}$$</jats:tex-math> <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> </jats:alternatives> </jats:inline-formula> contains a Seymour vertex with high probability across a broader range of regimes. </jats:p>