Second neighborhood problem

In mathematics, the second neighborhood problem is an unsolved problem about oriented graphs posed by Paul Seymour. Intuitively, it suggests that in a social network described by such a graph, someone will have at least as many friends-of-friends as friends. ^{[1] [2]}

The problem is also known as the second neighborhood conjecture or Seymour’s distance two conjecture. ^{[1] [3]}

Statement

An oriented graph is a finite directed graph obtained from a simple undirected graph by assigning an orientation to each edge. Equivalently, it is a directed graph that has no self-loops, no parallel edges, and no two-edge cycles. The first neighborhood of a vertex ${\displaystyle v}$ (also called its open neighborhood) consists of all vertices at distance one from ${\displaystyle v}$, and the second neighborhood of ${\displaystyle v}$ consists of all vertices at distance two from ${\displaystyle v}$. These two neighborhoods form disjoint sets, neither of which contains ${\displaystyle v}$ itself.

In 1990, Paul Seymour conjectured that, in every oriented graph, there always exists at least one vertex ${\displaystyle v}$ whose second neighborhood is at least as large as its first neighborhood. Equivalently, in the square of the graph, the degree of ${\displaystyle v}$ is at least doubled. The problem was first published by Nathaniel Dean and Brenda J. Latka in 1995, in a paper that studied the problem on a restricted class of oriented graphs, the tournaments (orientations of complete graphs). Dean had previously conjectured that every tournament obeys the second neighborhood conjecture, and this special case became known as Dean's conjecture. ^[4]

Unsolved problem in mathematics:

Does every oriented graph contain a Seymour vertex?

(more unsolved problems in mathematics)

A vertex in a directed graph whose second neighborhood is at least as large as its first neighborhood is called a Seymour vertex. ^[5]

In the second neighborhood conjecture, the condition that the graph have no two-edge cycles is necessary, for in graphs that have such cycles (for instance the complete oriented graph) all second neighborhoods may be empty or small.

Partial results

Fisher (1996) proved Dean's conjecture, the special case of the second neighborhood problem for tournaments. ^[6]

For some graphs, a vertex of minimum out-degree will be a Seymour vertex. For instance, if a directed graph has a sink, a vertex of out-degree zero, then the sink is automatically a Seymour vertex, because its first and second neighborhoods both have size zero. In a graph without sinks, a vertex of out-degree one is always a Seymour vertex. In the orientations of triangle-free graphs, any vertex ${\displaystyle v}$ of minimum out-degree is again a Seymour vertex, because for any edge from ${\displaystyle v}$ to another vertex ${\displaystyle w}$, the out-neighbors of ${\displaystyle w}$ all belong to the second neighborhood of ${\displaystyle v}$. ^[7]

For arbitrary graphs with higher vertex degrees, the vertices of minimum degree might not be Seymour vertices, but the existence of a low-degree vertex can still lead to the existence of a nearby Seymour vertex. Using this sort of reasoning, the second neighborhood conjecture has been proven to be true for any oriented graph that contains at least one vertex of out-degree ≤ 6. ^[8]

Random tournaments and some random directed graphs graphs have many Seymour vertices with high probability. ^[5] Every oriented graph has a vertex whose second neighborhood is at least ${\displaystyle \gamma }$ times as big as the first neighborhood, where

${\displaystyle \gamma ={\frac {1}{6}}\left(-1+{\sqrt[{3}]{53-6{\sqrt {78}}}}+{\sqrt[{3}]{53+6{\sqrt {78}}}}\right)\approx 0.657}$

is the real root of the polynomial ${\displaystyle 2x^{3}+x^{2}-1}$. ^[9]

See also

• Friendship paradox

References

1. Ghazal, Salman (2015). "A Remark on the Second Neighborhood Problem". Electronic Journal of Graph Theory and Applications. 3 (2): 182–190. arXiv: 1509.03282 . doi:10.5614/ejgta.2015.3.2.6. S2CID   12891714.
2. ""Seymour's 2nd Neighborhood Conjecture"". faculty.math.illinois.edu. Retrieved 2023-04-28.
3. "A Proof of Seymour's Second Neighborhood Conjecture" (PDF).
4. Dean, Nathaniel; Latka, Brenda J. (1995), "Squaring the tournament—an open problem", Proceedings of the Twenty-Sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), Congressus Numerantium, 109: 73–80, MR   1369296
5. Cohn, Zachary; Godbole, Anant; Wright Harkness, Elizabeth; Zhang, Yiguang (2016), "The number of Seymour vertices in random tournaments and digraphs", Graphs and Combinatorics, 32 (5): 1805–1816, arXiv: 1502.04061 , doi:10.1007/s00373-015-1672-9, MR   3543199, S2CID   253889516
6. Fisher, David C. (1996), "Squaring a tournament: a proof of Dean's conjecture", Journal of Graph Theory , 23 (1): 43–48, doi:10.1002/(SICI)1097-0118(199609)23:1<43::AID-JGT4>3.0.CO;2-K, MR   1402137
7. Brantner, James; Brockman, Greg; Kay, Bill; Snively, Emma (2009), "Contributions to Seymour's second neighborhood conjecture", Involve, 2 (4): 385–393, arXiv: 0808.0946 , doi:10.2140/involve.2009.2.387, MR   2579558, S2CID   6206110
8. Kaneko, Yoshihiro; Locke, Stephen C. (2001), "The minimum degree approach for Paul Seymour's distance 2 conjecture", Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001), Congressus Numerantium, 148: 201–206, MR   1887387
9. Chen, Guantao; Shen, Jian; Yuster, Raphael (2003), "Second neighborhood via first neighborhood in digraphs", Annals of Combinatorics , 7 (1): 15–20, doi:10.1007/s000260300001, MR   1984642, S2CID   11503071

External links

• Seymour's 2nd Neighborhood Conjecture, Open Problems in Graph Theory and Combinatorics, Douglas B. West.