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

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 346, n. 12, p. 12-pg., 2023-12-01.

Resumo

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)

• Processo FAPESP: 20/16570-4 - Problemas em Teoria de Ramsey, grafos aleatórios e imersões
• Beneficiário: Tássio Naia dos Santos
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 19/04375-5 - Problemas em Teoria de Ramsey, grafos aleatórios e imersões
• Beneficiário: Tássio Naia dos Santos
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos
• Beneficiário: Cristina Gomes Fernandes
• Modalidade de apoio: Auxílio à Pesquisa - Regular