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

-
One obvious but possibly helpful comment is that one can't hope to recover the graph from the set system. For example, suppose our graph $G$ is just the infinite ray: vertices are natural numbers $s=0,1,2,\ldots$, and there is an edge from $n$ to $n+1$. Then the only element of $N(G,s)$ is the set of all the vertices of $G$. However that means we can't hope to reconstruct the edges of $G$ from that: any other reordering of the integers would furnish us with the same $N(G,s)$. –  James Cranch May 9 '11 at 13:16
No, we can not recover it, but we can make a graph isomorphic to the original, by the obvious mapping. But you are right, any ordering of $\mathbb{N}$ would suffice. –  Pål GD May 9 '11 at 13:40
I suppose I meant recovering the graph not up to abstract isomorphism but up to labelled isomorphism. But there are cases where we genuinely can't even reconstruct the abstract isomorphism type of the graph. Consider the set system on the objects $a,b,0,1,2,...$ consisting of the three sets that contain everything except possibly one of $a$ and $b$. Then this is $N(G,s)$ for any graph that looks like an infinite ray, except that it forks off for a and b and then rejoins immediately afterwards. It could fork off anywhere, so it is $N(g,s)$ for lots of graphs which aren't abstractly isomorphic. –  James Cranch May 9 '11 at 13:48
You are indeed right (again), but what I'm really after, is not finding isomorphic (nor non-isomorphic) graphs based on the family of sets approach, but I'm really looking for what are the properties a family of sets need to have in order to in fact have a corresponding graph. These properties should also hold for any set generated from a given graph. –  Pål GD May 9 '11 at 14:49
Another necessary condition is that any $X\in N$ contains an at most countable $Y\in N$. –  Emil Jeřábek May 10 '11 at 12:42

(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:

1. (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))]$
2. (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 )$
3. (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.

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$.
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.
Thank you very much for your time, and for a good and thorough answer. I will have great use of your ideas and insight. I've only read it once, and will need to read it again (and again), but I have but one question now for the first reading; I accept reflexive vertices (self loops), but it seems you axiom 1 denies their existence. I would remove the entire $\neg \overline{E}(x, x) \land$-part from axiom 1. Is there a reason for keeping it? Maybe I underspecified it in the original question. –  Pål GD May 12 '11 at 10:31