Characterization of infinite paths in graphs First an introduction.
A directed graph we all know what is, and a graph is serial whenever
every vertex has a successor. I do not consider the empty graph.  A
pair $(\mathcal{G},s)$ is called a rooted graph when $s \in
\mathcal{G}$ and $\mathcal{G}$ is a directed serial graph.
Given a rooted graph $(\mathcal{G},s)$, a $(\mathcal{G},s)$-path is a
function $\lambda: \mathbb{N} \rightarrow V(\mathcal{G})$ such that
$\lambda(0) = s$ and for all $i \in \mathbb{N}$,
$(\lambda(i),\lambda(i+1)) \in E(\mathcal{G})$. Given any rooted graph
$(\mathcal{G},s)$, we define the set $N(\mathcal{G},s)$ as follows:
$$N(\mathcal{G},s) = \{ X \subseteq V(\mathcal{G}) \mid \text{ exists
a $(\mathcal{G},s)$-path $\lambda$ s.t. for all $i \in \mathbb{N}$, }
\lambda(i) \in X \}$$
My question is, for what sets $N$ does there exist a rooted directed
graph $(\mathcal{G},s)$ such that $N = N(\mathcal{G},s)$?
I am looking for a way of describing (possibly infinite) directed
serial graphs by giving a set of sets of vertices, each of which
corresponds to an infinite path starting in a specific start vertex
$s$.  I call these sets neighbourhood sets (a slightly unfortunately
name in graphs, I agree, but it comes from modal logic and its
neighbourhood semantics, which I am applying this to).
I would like to make some restrictions on a family of sets so that I
can say when such a family of sets do has a corresponding graph,
i.e. given a set of sets $N$, which properties must $N$ have in order
to have a rooted directed graph $(\mathcal{G},s)$ such that $N =
N(\mathcal{G},s)$.
Define the non-monotonic core of $N$ as follows:
$$N^{nc} = \{ X \in N \mid \not \exists Y \in N \text{ with } Y \subset X \}$$
I have come up with a few trivial properties that are all necessary,
but they are not sufficient, not even when restricted to finite
graphs. The properties are as follows:


*

*Safety: The universe itself (i.e. the vertex set $V$) has to be contained in $N$

*Reflexivity: There is an element $s$ such that when $X \in N$, we have that $s \in X$

*Upwards closed: If $X \in N$ and $X \subseteq Y \subseteq V$, $Y \in N$

*Countable case: If $X \in N^{nc}$, then $ |X| \leq \omega $

*If $X \in N^{nc}$ and $Y \in N^{nc}$ and $|X \cap Y| = |X \setminus Y| = |Y \setminus X| = \omega$, then there has to be at least another (or infinitely many) $Y \neq Z \in N^{nc}$ with $|X \cap Z| = |X \setminus Z| = |Z \setminus X| = \omega$


Now, it is trivial to check that the $N(\mathcal{G},s)$ satisfies the
above properties for any directed graph $\mathcal{G}$, but they are
not sufficient. Consider the following set:
$$N = \{ \{s,1,2,3\}, \{s,1,2,4\}, \{s,1,3,4\} ,\{s,2,3,4\},
\{s,1,2,3,4\} \}$$ 
I have proven (in a very brute force manner) that the above cannot
have a corresponding graph, so I will not give the proof here.
I am looking for the missing properties, and work that has been done
in this area.  I apologize in advance if I have not given enough
explanation, I have been stuck in this problem too long now to see
this clearly.  If I should explain more, or give examples, please let
me know, and I will.
Edit: Added some cases I didn't want to explain, but realized later I should put in anyway, but they both deals with infinite graphs, and I'm first and foremost after managing the subproblem that is finite graphs.
 A: (Not an answer, but too long for a comment)
One way to look at what you're asking for is a theory in some appropriate language which axiomatizes that we have a serial directed rooted graph, and a collection of subsets of the graph which behaves like $N(\mathcal{G},s)$, where the part of the axiomatization that dictates the behaviour of $N(\mathcal{G},s)$ doesn't say anything about the graph relation on $\mathcal{G}$.  I'll give an axiomatization where the part that talks about $N(\mathcal{G},s)$ does mention the graph relation, and I'll set it up in such a way that it'll seem unlikely that it can be redone without mentioning the graph relation.  I'm not sure about this, it's just an idea, but it's too long for a comment.
The Language
Consider the language $(\bar{V}, \bar{N}, \bar{E}, \bar{s}, \bar{\epsilon})$ - two unary relation symbols, one binary relation symbol, one constant symbol, and another binary relation symbol, respectively.  I'm going to set up a theory whose finite models will be precisely (sort of) those in which $(\bar{V}, \bar{E})$ is interpreted as a directed serial graph $\mathcal{G}$, $\bar{s}$ gets interpreted as a member $s$ of $\bar{V}$, $\bar{N}$ gets interpreted as $N(\mathcal{G},s)$, and $\bar{\epsilon}$ gets interpreted as the membership relation, a subset of $\bar{V} \times \bar{N}$.  Setting up the right theory is easy, the only part that will require a little explanation is how we ensure $\bar{N}$ gets interpreted correctly.
Axiomatizing $N(\mathcal{G},s)$ when we're allowed to mention the edge relation
Consider a formula like:
$$x_1 = \bar{s} \wedge x_1 \neq x_2 \wedge x_1 \neq x_3 \wedge x_2 \neq x_3$$
$$\wedge \bar{E}(x_1,x_2) \wedge \bar{E}(x_2,x_1) \wedge \neg \bar{E}(x_1,x_3) \wedge \neg \bar{E}(x_3,x_1) \wedge \neg \bar{E}(x_2,x_3) \wedge \neg \bar{E}(x_3,x_2)$$
It "says" we have three distinct $x_i$, the first one is $s$, and it tells you exactly which pairs stand in edge relation to one another and which don't.  You can also tell by looking at it that it defines a set $\{ x_1, x_2, x_3\}$ which contains an infinite path starting at $s$, namely $x_1, x_2, x_1, x_2, \dots$.
Let's define $\mathcal{R}$ to be the set of formulas in the language $(\bar{s}, \bar{E})$ of the form $\phi(x_1, \dots , x_n)$ which say that the $x_i$ are distinct, and which tell you precisely which pairs of the $x_i$ stand in $\bar{E}$ relation to one another, and which don't.  Define $\mathcal{R}^+$ to be those formulas $\phi \in \mathcal{R}$ such that for any rooted directed graph $((V,E),s)$, we have that:  
$(V,s,E)\vDash \phi(v_1, \dots , v_n) \rightarrow \{v_1, \dots , v_n\} \in N((V,E),s)$.
$\mathcal{R}^-$ will be those $\phi$ such that:  
$(V,s,E)\vDash \phi(v_1, \dots , v_n) \rightarrow \{v_1, \dots , v_n\} \not\in N((V,E),s)$.
Alright, now here's our theory:  


*

*(Rooted serial directed graph) $\bar{V}(\bar{s}) \wedge \forall x \bar{V}(x) \rightarrow [\neg \bar{E}(x,x) \wedge \exists y (\bar{V}(y) \wedge \bar{E}(x,y))]$

*(Schema for what goes in $N$) As $\phi(x_1, \dots ,x_n)$ varies over $\mathcal{R}^+$: $\forall \vec{x} \exists Y \forall x \left (\phi(\vec{x}) \rightarrow \left[ \bar{N}(Y) \wedge \bigwedge _i (x_i \bar{\epsilon} Y) \wedge \left (x \bar{\epsilon} Y \rightarrow \bigvee _i (x = x_i)\right )\right ]\right )$

*(Schema for what stays out of $N$) As $\phi(x_1, \dots ,x_n)$ varies over $\mathcal{R}^-$: $\forall \vec{x} \forall Y \exists x \left (\phi(\vec{x}) \rightarrow \neg \left[ \bar{N}(Y) \wedge \bigwedge _i (x_i \bar{\epsilon} Y) \wedge \left (x \bar{\epsilon} Y \rightarrow \bigvee _i (x = x_i)\right )\right ]\right )$


Checking this axiomatization works
It's clear that if $\mathcal{G} = (V,E)$ is a finite directed serial graph and $s \in V$, then $(V,N(\mathcal{G},s),E,s,\in)$ is a model of this theory.  Conversely, if we have a finite model $(V,N_0,E,s,\epsilon)$ of this theory, then $(V,E)$ forms a directed serial graph with $s \in V$.  Now let $N_1$ consist of those $Y \in N_0$ such that $\forall x (x \epsilon Y \rightarrow V(x))$.  I claim that:
$N((V,E),s) = \{ \{x : x \epsilon Y\} : Y \in N_1\}$
But I won't prove this.
A remark about some "unnaturalness"
It should seem like I could have done things differently so that things looked more natural and the above claim could be proved more easily.  The way I've written 2 and 3 are not the most natural, but I've done it for a reason.  2 says that if $\vec{x}$ is a tuple which is sure to contain an infinite path starting at $s$, then there's a member of $N$ consisting precisely of the members of $\vec{x}$.  3 says that if $\vec{x}$ is sure to not contain an infinite path starting at $x$, then there's nothing in $N$ consisting precisely of the members of $\vec{x}$.  The formulas in 2 and 3 are in prenex normal form, where the matrix is a conditional where the left side only involves the symbols $\bar{E}$ and $\bar{s}$, and the right side only $\bar{N}$ and $\bar{\epsilon}$.  Moreover, the antecedents have variables $\vec{x}$ and the consequents have variables $\vec{x}, Y, x$.
The point
You want a theory equivalent to axiom 1 and schemas 2 and 3 above, but you want to replace 2 and 3 with (probably finitely many) axioms which don't mention the symbol $\bar{E}$.  I feel like there ought to be some interpolation-type theorem (along the lines of Craig Interpolation or Lyndon Interpolation) which says this can't happen, i.e. something which says that a theory in which each axiom mention either only $\bar{V}, \bar{E}, \bar{s}$ or only $\bar{V}, \bar{N}, \bar{s}, \bar{\epsilon}$ can't prove a theory which has axioms like those in schemas 2 or 3.
