Seymour's second neighborhood conjecture for infinite graphs

Question

Let $G$ be a directed graph (say simple, so no loops and each pair of vertices has at most one directed edge between them). Suppose $G$ is 'locally finite', in the sense that each vertex has only finitely many edges going out of it. The first neighborhood $N^+(x)$ is the set of all $y\in G$ such that there is an edge $x\to y$. The second neighborhood $N^{++}(x)$ is everything reachable in exactly two steps from $x$: all $z\not\in N^+(x)\cup \{x\}$ such that there is some $y\in G$ with $x\to y\to z$.

A well-known conjecture of Seymour states that if $G$ is a finite nonempty directed graph then there exists some $x\in G$ with $\lvert N^+(x)\rvert \leq \lvert N^{++}(x)\rvert$. This is still open (but see e.g. Seymour's second neighborhood conjecture for some partial results).

What is the status of Seymour's second neighborhood conjecture for infinite (but still locally finite) connected graphs?

That is,

If $G$ is an infinite, locally finite, graph, must there exist some $x\in G$ such that $\lvert N^+(x)\rvert \leq \lvert N^{++}(x)\rvert$?

I ask mainly because it seems a natural generalisation, but to my surprise I can't find any discussion of it in the literature. Perhaps this is because it's 'trivial' for some reason that I can't see. Possibilities:

1. It's easily false, there is a simple construction of an infinite $G$.
2. It's easily true, there is some simple argument in the infinite case I can't see.
3. It's equivalent to the regular, finite graph, conjecture via some simple(ish) argument.
4. It's a genuinely different, hard, conjecture.

I've added the model-theory tag because I've mentioned this to a logician who suggested that possibility (3) might hold via some general model-theoretic argument (reducing the 'infinite model' of $G$ to some finite model somehow), but I don't know any details, and perhaps this just doesn't work.

(The restriction to locally finite is mainly so that the sizes of these neighborhoods are finite numbers, which I prefer thinking about. I don't know, but would be interested in, an answer even allowing the sizes of these neighborhoods to have infinite cardinalities.)

Any insights, answers, or pointers to somewhere in the literature this has been discussed and I've missed, would be appreciated.

EDIT: As Tony Huynh has pointed out in the comments, the infinite version implies the finite version (even if we ask for the infinite graph to be weakly connected). So (2) is unlikely, and the hard part of proving equivalence is showing that the finite case implies the infinite case.

Answer 1

Allow me to make an observation concerning what I find to be an interesting angle on the question in the context without the axiom of choice, where there are competing conceptions of what it means to be finite.

Namely, if we use Dedekind's notion of finiteness, then it is relatively consistent with ZF that the infinitary Seymour graph conjecture is false. A set is Dedekind finite, when it is not bijective with any proper subset.

Theorem. It is relatively consistent with the Zermelo Fraenkel ZF axioms of set theory without the axiom of choice that there is a simple directed graph $\Gamma$ such that

1. The graph $\Gamma$ is Dedekind finite.
2. The graph $\Gamma$ is weakly connected, and indeed, for any two nodes $x,y$ there is either an edge $x\to y$ or $y\to x$. So the underlying graph is complete.
3. Every node $v$ has a Dedekind finite neighbor set $N^+(v)$. Furthermore, the cardinalities of $N^+(v)$ are distinct for distinct vertices $v$.
4. Every $N^{++}(v)$ has strictly smaller cardinality than $N^+(v)$. Indeed, $N^{++}(v)=\varnothing$ for every node $v$.

Proof. It is well known to be relatively consistent with ZF that there is a set of real numbers $A\subseteq\mathbb{R}$ that is infinite, but Dedekind finite. We may assume that $A$ has no least element since $A$ can have at most a finite discrete order at the bottom, which upon deleting will produce an infinite Dedekind finite set with no least element.

Consider the directed graph $\Gamma$ consisting of the $>$ relation on $A$. That is, every element of $A$ points at the other elements strictly below it. Since the entirety of $A$ is Dedekind finite and $A$ has no least element, it follows that $N^+(v)$ is infinite but Dedekind finite for every vertex $v$.

And since every node points at all the lower nodes, the graph relation is transitive, it follows that $N^{++}(v)=\varnothing$, as it is defined in the OP. Thus, $N^{++}(v)$ is strictly smaller in cardinality than $N^+(v)$. So this graph has the desired properties.

Note that the neighbor sets $N^+(v)$ strictly descend in cardinality as $v$ descends in $A$, since if $v<w$ then the predecessors of $v$ in $A$ cannot be placed into bijection with the predecessors of $w$ in $A$, since this would lead to a nontrivial bijection of $A$ with a proper subset of itself, which is impossible for a Dedekind finite set. $\Box$

The same idea works as a theorem, and not just a relative consistency result, if one allows nodes to have infinite degree. This answers the version of the question mentioned by Louis D in the comments of the OP.

Theorem. The digraph consisting of the $>$ relation on an endless linear order has the properties that

1. The digraph is weakly connected, with the underlying graph complete.
2. Every $N^+(v)$ is infinite.
3. Every $N^{++}(v)=\varnothing$ is empty.

Proof. The graph consisting of the $>$ relation, meaning that every node points at the nodes strictly below it, has every $N^+(v)$ as the set of smaller nodes. This is weakly connected, since any two distinct nodes are related one way or the other. Since there is no minimal element, these sets are all infinite. But $N^{++}(v)=\varnothing$ is empty, because the relation is transitive. $\Box$

Answer 2

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).