Seymour’s Second Neighborhood Conjecture on sparse random graphs
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.
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.