Seymour's Second Neighborhood Conjecture for orientations of (pseudo)random graphs

Author(s)

Botler, Fabio ; Moura, Phablo F. S. ; Naia, Tassio

• Document type: Journal article
• Source: DISCRETE MATHEMATICS; v. 346, n. 12, p. 12-pg., 2023-12-01.

Abstract

Seymour's Second Neighborhood Conjecture (SNC) states that every oriented graph contains a vertex whose second neighborhood is as large as its first neighborhood. We investigate the SNC for orientations of both binomial and pseudo random graphs, verifying the SNC asymptotically almost surely (a.a.s.) (i) for all orientations of G(n, p) if lim supn & RARR;& INFIN; p < 1/4; and (ii) for a uniformly-random orientation of each weakly (p, A,Jnp)-bijumbled graph of order n and density p, where p = S2(n-1/2) and 1 - p = S2(n-1/6) and A > 0 is a universal constant independent of both n and p. We also show that a.a.s. the SNC holds for almost every orientation of G(n, p). More specifically, we prove that a.a.s. (iii) for all & epsilon; > 0 and p = p(n) with lim supn & RARR;& INFIN; p < 2/3 - & epsilon;, every orientation of G(n, p) with minimum outdegree S2 & epsilon;(,Jn) satisfies the SNC; and (iv) for all p = p(n), a random orientation of G(n, p) satisfies the SNC. We remark that either (iii) or (iv) confirms the SNC for almost every oriented graph. & COPY; 2023 Elsevier B.V. All rights reserved. (AU)

• FAPESP's process: 20/16570-4 - Problems in Ramsey Theory, random graphs and embeddings
• Grantee: Tássio Naia dos Santos
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
• FAPESP's process: 19/04375-5 - Problems in Ramsey Theory, random graphs and embeddings
• Grantee: Tássio Naia dos Santos
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 19/13364-7 - Extremal and structural problems in graph theory
• Grantee: Cristina Gomes Fernandes
• Support Opportunities: Regular Research Grants