4
$\begingroup$

Let $G=(V,E)$ be a countably infinite directed acyclic graph and $L$ be a finite set of vertex labels. The number $\left|V\right|$ of vertices is countable infinity and some vertices may have an infinite number of ingoing edges. I am interested in the existence of labelings $f: V \rightarrow L$ where the label $f(v)$ is determined by the labels of the predecessors of $v$.

More formally, let there be a function $g_v:L^{\mathrm{indeg}(v)} \rightarrow L$ for each vertex $v \in V$. Does there exist a labeling $f : V \rightarrow L$ such that for every vertex $v \in V$ with predecessors $p_0, p_1,\ldots$ the following holds? $$f(v) = g_v(f(p_0), f(p_1), \ldots)$$

Intuitively, it appears very clear to me that the acyclicity of $G$ guarantees the existence of such labelings $f$. But how do I prove that?

For a trivial example, consider the infinite path $G = (\mathbb{Z}, \{(v,v+1):v\in\mathbb{Z}\})$, $L = \{0, 1\}$ and $g_v:L\rightarrow L:x\mapsto 1 - x$. In this case there are exactly two labelings, one that assigns 0 and 1 to every even and odd vertex, respectively, and the other with 0 and 1 switched.

If we drop the requirement of acyclicity, a counterexample would be an odd directed cycle graph and $L$ and $g$ as in the example above. Here no labeling exists.

In the case of finite DAGs, I would prove the existence inductively over an topological ordering of $G$, starting by an arbitrary label-assignment for vertices without ingoing edges and then iteratively constructing the labeling for vertices whose predecessors have already been labeled. However, I fail to generalize this technique to infinite graphs in the absence of an induction basis.

$\endgroup$
1
$\begingroup$

A clear and good question.

In general there is a simple counterexample. Let $V=\omega=\{0,1,2,\dots\}$, $E=\{(m,n)\in\omega^2: m>n\}$, $L=\{0,1\}$. Let $\mathcal F$ be a free ultrafilter on the set $\omega$. Define a function $g:L^\omega\to L$ by putting for each labelling $f:V\to L$ $g(f)=1$, if $\{n\in\omega: f(n)=0\}\in\mathcal F$ and $g(f)=0$, otherwise. For each vertex $n\in\omega$ and each labelling $f’:\omega\setminus\{n+1\}\to L$ (that is, $f’\in \{0,1\}^{\{n+1,n+2,\dots\}}$) put $g_n(f’)=g(f)$, where $f:V\to L$ is an extension of the map $f'$ (that is, $f|_{\omega\setminus\{n+1\}}=f’$) (since the ultrafilter $\mathcal F$ is free, the map $g_n$ does not depend on an extension $f$). Assume that there exists a labelling $f:V\to\omega$ such that $f(n)=g_n(f|_{\omega\setminus\{n+1\}})$ for each $n\in\omega$. Let $F=f^{-1}(0)$. Then $f\equiv 1$ provided $F\in\mathcal F$ and $f\equiv 0$ provided $F\not\in\mathcal F$, a contradiction.

It seems the following.

If for each vertex $v\in V$ the set $p(v)=\{w\in V:(w,v)\in E\}$ of all its predecessors is finite, then the answer is positive. To show this we shall procced as follows. Endow the set $L^V$ of all labellings on the graph $G$ by a topology of a Tychonoff power of a finite discrete space $V$. By Tychonoff Theorem, the space $L^V$ is compact. Let $F$ be a finite subset of $V$. Put $C_F=\{f\in L^V: f(v)=g_v(f|_{p(v)})$ for all $v\in F\}$. We claim that the set $C_F$ is closed. Indeed, assume that $f\in L^V\setminus C_F$ be an arbitrary labelling. Since $f\not\in L^V$, there exists a vertex $v\in F$ such that $f(v)\ne g_v(f|_{p(v)})$. Then $O_f=\{h\in L^V: h(w)=f(w)$ for each $w\in \{v\}\cup p(v)\}$ is an open neighborhood of the labelling $f$ and $O_f\cap C_F=\varnothing$. Next we claim that the set $C_F$ is non-empty. To show this we construct a labelling $f\in C_F$ as follows. For each vertex $v\in V\setminus F$ let $f(v)$ be an arbitrary element of the set $L$. Since the graph $G$ has no directed cycles, we can enumerate the set $F$ (that is, to define a bijective map $i:F\to \{0,1,\dots n\}$) such that $i(v)>i(w)$ for each vertices $v\in F$ and $w\in F\cap p(v)$. Then we can inductive define $f|F$ by putting $f(v)=g(f|_{p(v)})$ for each vertex $v\in F$. Put $\mathcal C=\{C_F: F$ is a finite subset of $V\}$. Since $\mathcal C$ is a centered family of closed subsets of a compact space, there is a map $f\in\bigcap\mathcal C$. By construction, $f$ is a required labelling.

It rests for me to consider a case, when the graph $G$ has no undirected cycles.

$\endgroup$
2
$\begingroup$

Counterexample. As in Alex Ravsky's example, let $V=\omega$, $E=\{(m,n):m\gt n\}$, $L=\{0,1\}.$ Now simply define $f(p_0,p_1,\dots)$ to take the value $1$ if all of the inputs are $0$, and to take the value $0$ otherwise.

$\endgroup$
  • $\begingroup$ Nice. :-) I work too much in set-theoretic topology. :-) $\endgroup$ – Alex Ravsky May 8 '15 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.