Second neighborhood problem

Key takeaways

Second neighborhood problem belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Second neighborhood problem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Second neighborhood problem from memory before moving on to harder problems.

Reference excerpt

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. The problem is also known as the second neighborhood conjecture or Seymour’s distance two conjecture.

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 v {\displaystyle v} (also called its open neighborhood) consists of all vertices at distance one from v {\displaystyle v} , and the second neighborhood of v {\displaystyle v} consists of all vertices at distance two from v {\displaystyle v} . These two neighborhoods form disjoint sets, neither of which contains v {\displaystyle v} itself. In 1990, Paul Seymour conjectured that, in every oriented graph, there always exists at least one vertex v {\displaystyle v} whose second neighborhood is at least as large as its first neighborhood. Equivalently, in the square of the graph, the degree of v {\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.

A vertex in a directed graph whose second neighborhood is at least as large as its first neighborhood is called a Seymour vertex. 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. 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 v {\displaystyle v} of minimum out-degree is again a Seymour vertex, because for any edge from v {\displaystyle v} to another vertex w {\displaystyle w} , the out-neighbors of w {\displaystyle w} all belong to the second neighborhood of v {\displaystyle v} . 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.. Following this, the conjecture is true for all graphs with a number of vertices ≤ 14, as these must contain at least one vertex with out-degree ≤ 6. This can be improved to graphs with a number of vertices ≤ 15, because the only graphs with 15 vertices and none with out-degree ≤ 6 are tournament graphs. Every oriented bipartite graph follows the conjecture, as well as all oriented graphs whose vertex set can be partitioned into an independent set and a 2-degenerate graph. Random tournaments and some random directed graphs have many Seymour vertices with high probability. Every oriented graph has a vertex whose second neighborhood is at least γ {\displaystyle \gamma } times as big as the first neighborhood, where

γ = 1 6 ( − 1 + 53 − 6 78 3 + 53 + 6 78 3 ) ≈ 0.657 {\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 2 x 3 + x 2 − 1 {\displaystyle 2x^{3}+x^{2}-1} .

Illustrations

Worked examples

Example 1 — a first encounter with Second neighborhood problem

Start with the simplest possible case. Write down what Second neighborhood problem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Second neighborhood problem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Second neighborhood problem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Second neighborhood problem

In research: Second neighborhood problem appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Second neighborhood problem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Second neighborhood problem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Conjectures, Unsolved problems in graph theory, so understanding it makes those chapters shorter.
In everyday life: Look for Second neighborhood problem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Second neighborhood problem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Second neighborhood problem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Second neighborhood problem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Second neighborhood problem in simple terms?

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.

Why does Second neighborhood problem matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Second neighborhood problem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Second neighborhood problem.