Etiquetados de infinito dirigidos acíclicos gráficos

Question

Deje $G=(V,E)$ ser un countably infinito gráfico acíclico dirigido y $L$ ser un conjunto finito de vértices etiquetas. El número de $\left|V\right|$ de vértices es infinito contable y algunos vértices puede tener un número infinito de que entra bordes. Estoy interesado en la existencia de etiquetados $f: V \rightarrow L$ donde la etiqueta $f(v)$ está determinado por las etiquetas de los predecesores de $v$.

Más formalmente, una función de $g_v:L^{\mathrm{indeg}(v)} \rightarrow L$ para cada vértice $v \in V$. ¿Existe un etiquetado $f : V \rightarrow L$ tal que para cada vértice $v \in V$ con predecesores $p_0, p_1,\ldots$ el siguiente tiene? $$f(v) = g_v(f(p_0), f(p_1), \ldots)$$

Intuitivamente, parece muy claro para mí que el acyclicity de $G$ garantiza la existencia de tales etiquetados $f$. Pero, ¿cómo puedo demostrar que?

Para un ejemplo trivial, considere el camino infinito $G = (\mathbb{Z}, \{(v,v+1):v\in\mathbb{Z}\})$, $L = \{0, 1\}$ y $g_v:L\rightarrow L:x\mapsto 1 - x$. En este caso hay exactamente dos etiquetados, que asigna 0 y 1 para cada par e impar de vértices, respectivamente, y el otro con 0 y 1 conmutado.

Si dejamos caer el requisito de acyclicity, un contraejemplo sería una extraña dirigido ciclo de la gráfica de y $L$ $g$ como en el ejemplo anterior. Aquí no etiquetado existe.

En el caso de finito Dag, yo probaría la existencia inductivamente a través de una ordenación topológica de $G$, comenzando por una arbitraria de la etiqueta-la asignación de vértices sin que entra bordes y, a continuación, de forma iterativa, la construcción de las etiquetas de los vértices cuyos predecesores ya han sido etiquetados. Sin embargo, no puedo generalizar esta técnica a infinito gráficos en la ausencia de una inducción.

Answer 1

Contraejemplo. Como en Alex Ravsky del ejemplo, vamos a $V=\omega$, $E=\{(m,n):m\gt n\}$, $L=\{0,1\}.$ Ahora simplemente definen $f(p_0,p_1,\dots)$ a tomar el valor de $1$ si todas las entradas son de $0$, y tomar el valor de $0$ lo contrario.

Answer 2

Una clara y buena pregunta.

En general no es un simple contraejemplo. Vamos $V=\omega=\{0,1,2,\dots\}$, $E=\{(m,n)\in\omega^2: m>n\}$, $L=\{0,1\}$. Deje $\mathcal F$ libre de ultrafilter en el set $\omega$. Definir una función $g:L^\omega\to L$ poniendo para cada uno de etiquetado $f:V\to L$ $g(f)=1$, si $\{n\in\omega: f(n)=0\}\in\mathcal F$$g(f)=0$, de lo contrario. Para cada vértice $n\in\omega$ y cada uno de etiquetado de $f':\omega\setminus\{n+1\}\to L$ (es decir, $f'\in \{0,1\}^{\{n+1,n+2,\dots\}}$) pusieron $g_n(f')=g(f)$ donde $f:V\to L$ es una extensión del mapa $f'$ (es decir, $f|_{\omega\setminus\{n+1\}}=f'$) (desde el ultrafilter $\mathcal F$ es gratis, el mapa de $g_n$ no depende de una extensión de $f$). Suponga que existe un etiquetado $f:V\to\omega$ tal que $f(n)=g_n(f|_{\omega\setminus\{n+1\}})$ por cada $n\in\omega$. Deje $F=f^{-1}(0)$. A continuación,$f\equiv 1$$F\in\mathcal F$$f\equiv 0$$F\not\in\mathcal F$, una contradicción.

Parece que el siguiente.

Si para cada vértice $v\in V$ el conjunto $p(v)=\{w\in V:(w,v)\in E\}$ de todos sus predecesores, es finito, entonces la respuesta es positiva. Para mostrar esto vamos a procced de la siguiente manera. Dotar al conjunto de $L^V$ de todos los labellings en el gráfico de $G$ por una topología de Tychonoff potencia de un número finito de espacio discreto $V$. Por el Teorema de Tychonoff, el espacio de $L^V$ es compacto. Deje $F$ ser un subconjunto finito de $V$. Poner $C_F=\{f\in L^V: f(v)=g_v(f|_{p(v)})$ todos los $v\in F\}$. Pretendemos que el conjunto $C_F$ es cerrado. En efecto, supongamos que $f\in L^V\setminus C_F$ ser arbitraria de etiquetado. Desde $f\not\in L^V$, existe un vértice $v\in F$ tal que $f(v)\ne g_v(f|_{p(v)})$. A continuación, $O_f=\{h\in L^V: h(w)=f(w)$ por cada $w\in \{v\}\cup p(v)\}$ es un barrio abierto de etiquetado de $f$$O_f\cap C_F=\varnothing$. El próximo pretendemos que el conjunto $C_F$ no está vacía. Para mostrar esto se construye un etiquetado $f\in C_F$ como sigue. Para cada vértice $v\in V\setminus F$ deje $f(v)$ ser un elemento arbitrario del conjunto $L$. Dado que el gráfico de $G$ no tiene ningún dirigida ciclos, podemos enumerar el conjunto $F$ (es decir, para definir un bijective mapa de $i:F\to \{0,1,\dots n\}$) tal que $i(v)>i(w)$ para cada uno de los vértices $v\in F$$w\in F\cap p(v)$. Entonces podemos inductivo definir $f|F$ poniendo $f(v)=g(f|_{p(v)})$ para cada vértice $v\in F$. Poner $\mathcal C=\{C_F: F$ es un subconjunto finito de $V\}$. Desde $\mathcal C$ es un centrada en la familia de subconjuntos cerrados de un espacio compacto, existe un mapa de $f\in\bigcap\mathcal C$. Por construcción, $f$ es un tipo de etiquetado.

Descansa para que me considere un caso, cuando el gráfico de $G$ no tiene ningún grafo ciclos.