Seymour’s second neighborhood conjecture states that every oriented graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\vec {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mover accent="true"> <mi>G</mi> <mo stretchy="false">→</mo> </mover> </math></EquationSource> </InlineEquation> has a Seymour vertex, namely, <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\vec {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mover accent="true"> <mi>G</mi> <mo stretchy="false">→</mo> </mover> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$K_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> appears independently with probability <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$p_n(e)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>p</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\vec {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mover accent="true"> <mi>G</mi> <mo stretchy="false">→</mo> </mover> </math></EquationSource> </InlineEquation> by assigning an orientation to each edge of G independently with equal probability, we prove that <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\vec {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mover accent="true"> <mi>G</mi> <mo stretchy="false">→</mo> </mover> </math></EquationSource> </InlineEquation> contains a Seymour vertex with high probability across a broader range of regimes.

Asymptotic confirmation of the second neighborhood conjecture on inhomogeneous random graphs

期刊论文
出版模式：

开放获取
发表日期：

2026年8月3日

查看全文

Yilun Shang

摘要

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