Seymour’s Second Neighborhood Conjecture on sparse random graphs

  • Fábio Botler UFRJ
  • Phablo Moura UFMG
  • Tássio Naia USP

Resumo


Seymour’s Second Neighborhood Conjecture (SNC) says that every oriented graph contains a vertex whose second neighborhood is at least as large as its first neighborhood. We prove that asymptotically almost surely (a.a.s.) every orientation of the binomial random graph G(n, p) satisfies the SNC if n4p6 → 0. We also show that if p ∈ (0, 2/3), then a.a.s. a uniformly-random orientation of G(n, p) satisfies the SNC, settling it for almost every labeled oriented graph.

Palavras-chave: binomial random graph, second neighbor conjecture, orientations

Referências

Chen, G., Shen, J., and Yuster, R. (2003). Second neighborhood via first neighborhood in digraphs. Annals of Combin., 7(1):15–20.

Cohn, Z., Godbole, A., Harkness, E. W., and Zhang, Y. (2016). The number of Seymour vertices in random tournaments and digraphs. Graphs and Combin., 32(5):1805–1816.

Conlon, D. and Gowers, W. T. (2016). Combinatorial theorems in sparse random sets. Ann. of Math. (2), 184(2):367–454.

Dean, N. and Latka, B. J. (1995). Squaring the tournament-an open problem. Congressus Numerantium, pages 73–80.

Fidler, D. and Yuster, R. (2007). Remarks on the second neighborhood problem. J. of Graph Theory, 55(3):208–220.

Fisher, D. C. (1996). Squaring a tournament: A proof of Dean’s conjecture. J. of Graph Theory, 23(1):43–48.

Havet, F. and Thomassé, S. (2000). Median orders of tournaments: A tool for the second neighborhood problem and Sumner’s conjecture. J. of Graph Theory, 35(4):244–256.

Seacrest, T. (2015). The arc-weighted version of the second neighborhood conjecture. J. of Graph Theory, 78(3):219–228.
Publicado
31/07/2022
BOTLER, Fábio; MOURA, Phablo; NAIA, Tássio. Seymour’s Second Neighborhood Conjecture on sparse random graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 37-40. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.222701.