Seymour’s Second Neighborhood Conjecture on sparse random graphs

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

DOI: https://doi.org/10.5753/etc.2022.222701

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 n⁴p⁶ → 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.