Return to Answer

A "digraph" is a simple digraph without $2$-cycles, i.e., an oriented graph. "Locally finite" means outwards locally finite, i.e., each vertex $x$ has finite outdegree $\deg^+(x)\lt\infty$. If $x,y$ are vertices in a digraph, $d(x,y)$ is the minimum length of a directed path from $x$ to $y$.

Your "infinite second neighborhood conjecture" for locally finite weakly connected digraphs is equivalent to a certain proposition about finite digraphs which is ostensibly stronger than Seymour's conjecture, namely:

Strong Second Neighborhood Conjecture. There is a function $f:\mathbb N\to\mathbb N$ such that, if $x$ is a vertex of outdegree $\deg^+(x)=d$ in a finite digraph $G$, then there is a vertex $y$ in $G$ with $d(x,y)\le f(d)$ and $|N^+(y)|\le|N^{++}(y)|$.

(If this is true then $f(d)\ge d$ as shown by the graph with vertex set $X_1\cup\cdots\cup X_{d+1}$ where the $X_i$ are disjoint sets with $|X_i|=i$, and with arcs from all vertices in $X_{i+1}$ to all vertices in $X_i$. Could it be that $f(d)=d$ holds for all $d$? At least it holds for $d\le3$.)

It will be convenient to restate the equivalence in the contrapositive form:

Theorem. For any $d\in\mathbb N$ the following statements are equivalent:
(1) there is a locally finite weakly connected digraph $G$, containing a vertex $x$ of outdegree $\deg^+(x)=d$, such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $G$;
(2) for each $n\in\mathbb N$ there is a finite digraph $F$ containing a vertex $x$ with outdegree $\deg^+(x)=d$ such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $F$ with $d(x,y)\le n$.

Proof.
(1) $\implies$ (2): Just take the subgraph induced by $\{y:d(x,y)\le n+1\}$.
(2) $\implies$ (1): For $n\in\mathbb N$ let $\mathbb F_n$ be the class of rooted finite digraphs $(F,x)$ such that (i) $\deg^+(x)=d$, (ii) each vertex $y$ in $F$ is reachable from $x$ with $d(x,y)\le n+1$, and (iii) $|N^+(y)|\gt|N^{++}(y)|$ whenever $d(x,y)\le n$. It follows from (2) that $\mathbb F_n$ is nonempty for every $n\in\mathbb N$. Moreover, if $(F,x)\in\mathbb F_n$, and if $y$ is a vertex with $d(x,y)\le n$, and if there is an arc $y\to z$, then it follows from $|N^+(y)|\gt|N^{++}(y)|$ that $\deg^+(z)\le2\cdot\deg^+(y)-2$. From this it follows that the elements of each $\mathbb F_n$ are bounded in size, whence each $\mathbb F_n$ is finite up to isomorphism. Finally, we can use Kőnig's infinity lemma to get an increasing infinite sequence of rooted finite digraphs whose union is a digraph $G$ as in (1).

A "digraph" is a simple digraph without $2$-cycles, i.e., an oriented graph. "Locally finite" means outwards locally finite, i.e., each vertex $x$ has finite outdegree $\deg^+(x)\lt\infty$. If $x,y$ are vertices in a digraph, $d(x,y)$ is the minimum length of a directed path from $x$ to $y$.

Your "infinite second neighborhood conjecture" for locally finite weakly connected digraphs is equivalent to a certain proposition about finite digraphs which is ostensibly stronger than Seymour's conjecture, namely:

Strong Second Neighborhood Conjecture. There is a function $f:\mathbb N\to\mathbb N$ such that, if $x$ is a vertex of outdegree $\deg^+(x)=d$ in a finite digraph $G$, then there is a vertex $y$ in $G$ with $d(x,y)\le f(d)$ and $|N^+(y)|\le|N^{++}(y)|$.

(If this is true then $f(d)\ge d$ as shown by the graph with vertex set $X_1\cup\cdots\cup X_{d+1}$ where the $X_i$ are disjoint sets with $|X_i|=i$, and with arcs from all vertices in $X_{i+1}$ to all vertices in $X_i$. Could it be that $f(d)=d$ holds for all $d$? At least it holds for $d\le4$.)

It will be convenient to restate the equivalence in the contrapositive form:

Theorem. For any $d\in\mathbb N$ the following statements are equivalent:
(1) there is a locally finite weakly connected digraph $G$, containing a vertex $x$ of outdegree $\deg^+(x)=d$, such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $G$;
(2) for each $n\in\mathbb N$ there is a finite digraph $F$ containing a vertex $x$ with outdegree $\deg^+(x)=d$ such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $F$ with $d(x,y)\le n$.

Proof.
(1) $\implies$ (2): Just take the subgraph induced by $\{y:d(x,y)\le n+1\}$.
(2) $\implies$ (1): For $n\in\mathbb N$ let $\mathbb F_n$ be the class of rooted finite digraphs $(F,x)$ such that (i) $\deg^+(x)=d$, (ii) each vertex $y$ in $F$ is reachable from $x$ with $d(x,y)\le n+1$, and (iii) $|N^+(y)|\gt|N^{++}(y)|$ whenever $d(x,y)\le n$. It follows from (2) that $\mathbb F_n$ is nonempty for every $n\in\mathbb N$. Moreover, if $(F,x)\in\mathbb F_n$, and if $y$ is a vertex with $d(x,y)\le n$, and if there is an arc $y\to z$, then it follows from $|N^+(y)|\gt|N^{++}(y)|$ that $\deg^+(z)\le2\cdot\deg^+(y)-2$. From this it follows that the elements of each $\mathbb F_n$ are bounded in size, whence each $\mathbb F_n$ is finite up to isomorphism. Finally, we can use Kőnig's infinity lemma to get an increasing infinite sequence of rooted finite digraphs whose union is a digraph $G$ as in (1).

A "digraph" is a simple digraph without $2$-cycles, i.e., an oriented graph. "Locally finite" means outwards locally finite, i.e., each vertex $x$ has finite outdegree $\deg^+(x)\lt\infty$. If $x,y$ are vertices in a digraph, $d(x,y)$ is the minimum length of a directed path from $x$ to $y$.

Your "infinite second neighborhood conjecture" for locally finite weakly connected digraphs is equivalent to a certain proposition about finite digraphs which is ostensibly stronger than Seymour's conjecture, namely:

Strong Second Neighborhood Conjecture. There is a function $f:\mathbb N\to\mathbb N$ such that, if $x$ is a vertex of outdegree $\deg^+(x)=d$ in a finite digraph $G$, then there is a vertex $y$ in $G$ with $d(x,y)\le f(d)$ and $|N^+(y)|\le|N^{++}(y)|$.

(If this is true then $f(d)\ge d$ as shown by the graph with vertex set $X_1\cup\cdots\cup X_{d+1}$ where the $X_i$ are disjoint sets with $|X_i|=i$, and with arcs from all vertices in $X_{i+1}$ to all vertices in $X_i$. Could it be that $f(d)=d$ holds for all $d$? At least it holds for $d\le4$.)

It will be convenient to restate the equivalence in the contrapositive form:

Theorem. For any $d\in\mathbb N$ the following statements are equivalent:
(1) there is a locally finite weakly connected digraph $G$, containing a vertex $x$ of outdegree $\deg^+(x)=d$, such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $G$;
(2) for each $n\in\mathbb N$ there is a finite digraph $F$ containing a vertex $x$ with outdegree $\deg^+(x)=d$ such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $F$ with $d(x,y)\le n$.

Proof.
(1) $\implies$ (2): Just take the subgraph induced by $\{y:d(x,y)\le n+1\}$.
(2) $\implies$ (1): For $n\in\mathbb N$ let $\mathbb F_n$ be the class of rooted finite digraphs $(F,x)$ such that (i) $\deg^+(x)=d$, (ii) each vertex $y$ in $F$ is reachable from $x$ with $d(x,y)\le n+1$, and (iii) $|N^+(y)|\gt|N^{++}(y)|$ whenever $d(x,y)\le n$. It follows from (2) that $\mathbb F_n$ is nonempty for every $n\in\mathbb N$. Moreover, if $(F,x)\in\mathbb F_n$, and if $y$ is a vertex with $d(x,y)\le n$, and if there is an arc $y\to z$, then it follows from $|N^+(y)|\gt|N^{++}(y)|$ that $\deg^+(z)\le2\cdot\deg^+(y)-2$. From this it follows that the elements of each $\mathbb F_n$ are bounded in size, whence each $\mathbb F_n$ is finite up to isomorphism. Finally, we can use Kőnig's infinity lemma to get an increasing infinite sequence of rooted finite digraphs whose union is a digraph $G$ as in (1).

A "digraph" is a simple digraph without $2$-cycles, i.e., an oriented graph. "Locally finite" means outwards locally finite, i.e., each vertex $x$ has finite outdegree $\deg^+(x)\lt\infty$. If $x,y$ are vertices in a digraph, $d(x,y)$ is the minimum length of a directed path from $x$ to $y$.

Your "infinite second neighborhood conjecture" for locally finite weakly connected digraphs is equivalent to a certain proposition about finite digraphs which is ostensibly stronger than Seymour's conjecture, namely:

Strong Second Neighborhood Conjecture. There is a function $f:\mathbb N\to\mathbb N$ such that, if $x$ is a vertex of outdegree $\deg^+(x)=d$ in a finite digraph $G$, then there is a vertex $y$ in $G$ with $d(x,y)\le f(d)$ and $|N^+(y)|\le|N^{++}(y)|$.

(If this is true then $f(d)\ge d$ as shown by the graph with vertex set $X_1\cup\cdots\cup X_{d+1}$ where the $X_i$ are disjoint sets with $|X_i|=i$, and with arcs from all vertices in $X_{i+1}$ to all vertices in $X_i$. Could it be that $f(d)=d$ holds for all $d$? At least it holds for $d\le3$.)

It will be convenient to restate the equivalence in the contrapositive form:

Theorem. For any $d\in\mathbb N$ the following statements are equivalent:
(1) there is a locally finite weakly connected digraph $G$, containing a vertex $x$ of outdegree $\deg^+(x)=d$, such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $G$;
(2) for each $n\in\mathbb N$ there is a finite digraph $F$ containing a vertex $x$ with outdegree $\deg^+(x)=d$ such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $F$ with $d(x,y)\le n$.

Proof.
(1) $\implies$ (2): Just take the subgraph induced by $\{y:d(x,y)\le n+1\}$.
(2) $\implies$ (1): For $n\in\mathbb N$ let $\mathbb F_n$ be the class of rooted finite digraphs $(F,x)$ such that (i) $\deg^+(x)=d$, (ii) each vertex $y$ in $F$ is reachable from $x$ with $d(x,y)\le n+1$, and (iii) $|N^+(y)|\gt|N^{++}(y)|$ whenever $d(x,y)\le n$. It follows from (2) that $\mathbb F_n$ is nonempty for every $n\in\mathbb N$. Moreover, if $(F,x)\in\mathbb F_n$, and if $y$ is a vertex with $d(x,y)\le n$, and if there is an arc $y\to z$, then it follows from $|N^+(y)|\gt|N^{++}(y)|$ that $\deg^+(z)\le2\cdot\deg^+(y)-2$. From this it follows that the elements of each $\mathbb F_n$ are bounded in size, whence each $\mathbb F_n$ is finite up to isomorphism. Finally, we can use Kőnig's infinity lemma to get an increasing infinite sequence of rooted finite digraphs whose union is a digraph $G$ as in (1).

A "digraph" is a simple digraph without $2$-cycles, i.e., an oriented graph. "Locally finite" means outwards locally finite, i.e., each vertex $x$ has finite outdegree $\deg^+(x)\lt\infty$. If $x,y$ are vertices in a digraph, $d(x,y)$ is the minimum length of a directed path from $x$ to $y$.

Your "infinite second neighborhood conjecture" for locally finite weakly connected digraphs is equivalent to a certain proposition about finite digraphs which is ostensibly stronger than Seymour's conjecture, namely:

Strong Second Neighborhood Conjecture. There is a function $f:\mathbb N\to\mathbb N$ such that, if $x$ is a vertex of outdegree $\deg^+(x)=d$ in a finite digraph $G$, then there is a vertex $y$ in $G$ with $d(x,y)\le f(d)$ and $|N^+(y)|\le|N^{++}(y)|$.

(If this is true then $f(d)\ge d$ as shown by the graph with vertex set $X_1\cup\cdots\cup X_{d+1}$ where the $X_i$ are disjoint sets with $|X_i|=i$, and with arcs from all vertices in $X_{i+1}$ to all vertices in $X_i$. Could it be that $f(d)=d$ holds for all $d$? At least it holds for $d\le3$.)

It will be convenient to restate the equivalence in the contrapositive form:

Theorem. For any $d\in\mathbb N$ the following statements are equivalent:
(1) there is a locally finite weakly connected digraph $G$, containing a vertex $x$ of outdegree $\deg^+(x)=d$, such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $G$;
(2) for each $n\in\mathbb N$ there is a finite digraph $F$ containing a vertex $x$ with outdegree $\deg^+(x)=d$ such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $F$ with $d(x,y)\le n$.

Proof.
(1) $\implies$ (2): Just take the subgraph induced by $\{y:d(x,y)\le n+1\}$.
(2) $\implies$ (1): For $n\in\mathbb N$ let $\mathbb F_n$ be the class of rooted finite digraphs $(F,x)$ such that (i) $\deg^+(x)=d$, (ii) each vertex $y$ in $F$ is reachable from $x$ with $d(x,y)\le n+1$, and (iii) $|N^+(y)|\gt|N^{++}(y)|$ whenever $d(x,y)\le n$. It follows from (2) that $\mathbb F_n$ is nonempty for every $n\in\mathbb N$. Moreover, if $(F,x)\in\mathbb F_n$, and if $y$ is a vertex with $d(x,y)\le n$, and if there is an arc $y\to z$, then it follows from $|N^+(y)|\gt|N^{++}(y)|$ that $\deg^+(z)\le2\cdot\deg^+(y)-2$. From this it follows that the elements of each $\mathbb F_n$ are bounded in size, whence each $\mathbb F_n$ is finite up to isomorphism. Finally, we can use Kőnig's infinity lemma to get an increasing infinite sequence of rooted finite digraphs whose union is a digraph $G$ as in (1).

A "digraph" is a simple digraph without $2$-cycles, i.e., an oriented graph. "Locally finite" means outwards locally finite, i.e., each vertex $x$ has finite outdegree $\deg^+(x)\lt\infty$. If $x,y$ are vertices in a digraph, $d(x,y)$ is the minimum length of a directed path from $x$ to $y$.

Your "infinite second neighborhood conjecture" for locally finite weakly connected digraphs is equivalent to a certain proposition about finite digraphs which is ostensibly stronger than Seymour's conjecture, namely:

Strong Second Neighborhood Conjecture. There is a function $f:\mathbb N\to\mathbb N$ such that, if $x$ is a vertex of outdegree $\deg^+(x)=d$ in a finite digraph $G$, then there is a vertex $y$ in $G$ with $d(x,y)\le f(d)$ and $|N^+(y)|\le|N^{++}(y)|$.

(If this is true then $f(d)\ge d$ as shown by the graph with vertex set $X_1\cup\cdots\cup X_{d+1}$ where the $X_i$ are disjoint sets with $|X_i|=i$, and with arcs from all vertices in $X_{i+1}$ to all vertices in $X_i$. Could it be that $f(d)=d$ holds for all $d$? At least it holds for $d\le4$.)

It will be convenient to restate the equivalence in the contrapositive form:

Theorem. For any $d\in\mathbb N$ the following statements are equivalent:
(1) there is a locally finite weakly connected digraph $G$, containing a vertex $x$ of outdegree $\deg^+(x)=d$, such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $G$;
(2) for each $n\in\mathbb N$ there is a finite digraph $F$ containing a vertex $x$ with outdegree $\deg^+(x)=d$ such that $|N^+(y)|\gt|N^{++}(y)|$ for all vertices $y$ in $F$ with $d(x,y)\le n$.

Proof.
(1) $\implies$ (2): Just take the subgraph induced by $\{y:d(x,y)\le n+1\}$.
(2) $\implies$ (1): For $n\in\mathbb N$ let $\mathbb F_n$ be the class of rooted finite digraphs $(F,x)$ such that (i) $\deg^+(x)=d$, (ii) each vertex $y$ in $F$ is reachable from $x$ with $d(x,y)\le n+1$, and (iii) $|N^+(y)|\gt|N^{++}(y)|$ whenever $d(x,y)\le n$. It follows from (2) that $\mathbb F_n$ is nonempty for every $n\in\mathbb N$. Moreover, if $(F,x)\in\mathbb F_n$, and if $y$ is a vertex with $d(x,y)\le n$, and if there is an arc $y\to z$, then it follows from $|N^+(y)|\gt|N^{++}(y)|$ that $\deg^+(z)\le2\cdot\deg^+(y)-2$. From this it follows that the elements of each $\mathbb F_n$ are bounded in size, whence each $\mathbb F_n$ is finite up to isomorphism. Finally, we can use Kőnig's infinity lemma to get an increasing infinite sequence of rooted finite digraphs whose union is a digraph $G$ as in (1).