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.

6more comments