Segunda conjetura de vecindad de Seymour para grafos infinitos

Question

Sea $G$ sea un grafo dirigido (digamos simple, es decir, sin bucles y cada par de vértices tiene como máximo una arista dirigida entre ellos). Supongamos que $G$ es "localmente finito", en el sentido de que cada vértice sólo tiene un número finito de aristas que salen de él. El primer vecindario $N^+(x)$ es el conjunto de todos los $y\in G$ tal que existe una arista $x\to y$ . El segundo barrio $N^{++}(x)$ es todo lo alcanzable en exactamente dos pasos desde $x$ : todos $z\not\in N^+(x)\cup \{x\}$ de forma que exista algún $y\in G$ con $x\to y\to z$ .

Una conocida conjetura de Seymour afirma que si $G$ es un finito grafo dirigido no vacío entonces existe algún $x\in G$ con $\lvert N^+(x)\rvert \leq \lvert N^{++}(x)\rvert$ . Esta cuestión sigue abierta (pero véase, por ejemplo La segunda conjetura de vecindad de Seymour para algunos resultados parciales).

¿Cuál es la situación de la segunda conjetura de vecindad de Seymour para grafos conexos infinitos (pero aún localmente finitos)?

Eso es,

Si $G$ es un grafo infinito, localmente finito, debe existir alguna $x\in G$ tal que $\lvert N^+(x)\rvert \leq \lvert N^{++}(x)\rvert$ ?

Lo pregunto principalmente porque parece una generalización natural, pero para mi sorpresa no encuentro ningún debate al respecto en la bibliografía. Quizá se deba a que es "trivial" por alguna razón que desconozco. Posibilidades:

1. Es fácilmente falso, hay una construcción simple de un infinito $G$ .
2. Es fácilmente cierto, hay algún argumento sencillo en el caso infinito que no veo.
3. Es equivalente a la conjetura del grafo regular finito mediante un argumento sencillo.
4. Es una conjetura genuinamente diferente, dura.

He añadido la etiqueta de teoría de modelos porque he mencionado esto a un lógico que sugirió que la posibilidad (3) podría mantenerse mediante algún argumento general de teoría de modelos (reduciendo el "modelo infinito" de $G$ a algún modelo finito de alguna manera), pero no conozco los detalles, y quizás esto no funcione.

(La restricción a localmente finito es principalmente para que los tamaños de estos barrios son números finitos, que prefiero pensar. No conozco, pero me interesaría, una respuesta incluso permitiendo que los tamaños de estos vecindarios tengan cardinalidades infinitas).

Agradecería cualquier idea, respuesta o indicación sobre algún lugar de la bibliografía en el que se haya tratado este tema y que yo me haya perdido.

EDIT: Como ha señalado Tony Huynh en los comentarios, la versión infinita implica la versión finita (incluso si pedimos que el grafo infinito sea débilmente conexo). Así que (2) es improbable, y la parte difícil de demostrar la equivalencia es mostrar que el caso finito implica el caso infinito.

Answer 1

Permítanme hacer una observación sobre lo que me parece un ángulo interesante de la cuestión en el contexto sin el axioma de elección, donde hay concepciones opuestas de lo que significa ser finito.

A saber, si utilizamos la noción de finitud de Dedekind, entonces es relativamente coherente con ZF que la conjetura del grafo de Seymour infinito sea falsa. Un conjunto es Dedekind finito cuando no es biyectiva con ningún subconjunto propio.

Teorema. Es relativamente coherente con los axiomas de Zermelo Fraenkel ZF de la teoría de conjuntos sin el axioma de elección que exista un grafo dirigido simple $\Gamma$ tal que

1. El gráfico $\Gamma$ es Dedekind finito.
2. El gráfico $\Gamma$ está débilmente conectada y, de hecho, para dos nodos cualesquiera $x,y$ existe una arista $x\to y$ o $y\to x$ . Por tanto, el gráfico subyacente está completo.
3. Cada nodo $v$ tiene un conjunto vecino finito Dedekind $N^+(v)$ . Además, las cardinalidades de $N^+(v)$ son distintos para vértices distintos $v$ .
4. Cada $N^{++}(v)$ tiene una cardinalidad estrictamente menor que $N^+(v)$ . Efectivamente, $N^{++}(v)=\varnothing$ para cada nodo $v$ .

Prueba. Es bien sabido que es relativamente consistente con ZF que existe un conjunto de números reales $A\subseteq\mathbb{R}$ que es infinito, pero Dedekind finito. Podemos suponer que $A$ no tiene ningún elemento mínimo ya que $A$ puede tener como mucho un orden discreto finito en la parte inferior, que al borrarlo producirá un conjunto finito Dedekind infinito sin elemento menor.

Consideremos el grafo dirigido $\Gamma$ compuesto por $>$ relación sobre $A$ . Es decir, cada elemento de $A$ apunta a los otros elementos estrictamente por debajo de él. Dado que la totalidad de $A$ es Dedekind finito y $A$ no tiene ningún elemento mínimo, se deduce que $N^+(v)$ es infinito pero Dedekind finito para cada vértice $v$ .

Y como cada nodo apunta a todos los nodos inferiores, la relación del grafo es transitiva, se deduce que $N^{++}(v)=\varnothing$ tal y como se define en el PO. Así pues, $N^{++}(v)$ tiene una cardinalidad estrictamente menor que $N^+(v)$ . Así que este gráfico tiene las propiedades deseadas.

Obsérvese que los conjuntos vecinos $N^+(v)$ descienden estrictamente en cardinalidad como $v$ desciende en $A$ ya que si $v<w$ entonces los predecesores de $v$ en $A$ no puede colocarse en biyección con los predecesores de $w$ en $A$ ya que esto conduciría a una biyección no trivial de $A$ con un subconjunto propio de sí mismo, lo que es imposible para un conjunto finito Dedekind. $\Box$

La misma idea funciona como un teorema, y no sólo como un resultado de consistencia relativa, si se permite que los nodos tengan grado infinito. Esto responde a la versión de la pregunta mencionada por Louis D en los comentarios del OP.

Teorema. El dígrafo formado por $>$ sobre un orden lineal infinito tiene las propiedades de que

1. El dígrafo es débilmente conexo, con el grafo subyacente completo.
2. Cada $N^+(v)$ es infinito.
3. Cada $N^{++}(v)=\varnothing$ está vacía.

Prueba. El gráfico formado por $>$ lo que significa que cada nodo apunta a los nodos estrictamente por debajo de él, tiene cada $N^+(v)$ como el conjunto de nodos más pequeños. Se trata de una conexión débil, ya que dos nodos distintos cualesquiera están relacionados de un modo u otro. Como no hay ningún elemento mínimo, todos estos conjuntos son infinitos. Pero $N^{++}(v)=\varnothing$ está vacía, porque la relación es transitiva. $\Box$

Answer 2

Un "dígrafo" es un simple dígrafo sin $2$ -es decir, un grafo orientado. "Localmente finito" significa hacia el exterior localmente finito, es decir, cada vértice $x$ tiene un grado exterior finito $\deg^+(x)\lt\infty$ . Si $x,y$ son vértices de un dígrafo, $d(x,y)$ es la longitud mínima de un camino dirigido desde $x$ a $y$ .

Tu "conjetura de la segunda vecindad infinita" para dígrafos débilmente conectados localmente finitos es equivalente a cierta proposición sobre dígrafos finitos que es ostensiblemente más fuerte que la conjetura de Seymour, a saber:

Conjetura fuerte de la segunda vecindad. Existe una función $f:\mathbb N\to\mathbb N$ tal que, si $x$ es un vértice de grado exterior $\deg^+(x)=d$ en un dígrafo finito $G$ entonces hay un vértice $y$ en $G$ con $d(x,y)\le f(d)$ y $|N^+(y)|\le|N^{++}(y)|$ .

(Si esto es cierto, entonces $f(d)\ge d$ como muestra el gráfico con el conjunto de vértices $X_1\cup\cdots\cup X_{d+1}$ donde el $X_i$ son conjuntos disjuntos con $|X_i|=i$ y con arcos desde todos los vértices en $X_{i+1}$ a todos los vértices de $X_i$ . ¿Podría ser que $f(d)=d$ es válido para $d$ ? Al menos es válido para $d\le4$ .)

Será conveniente replantear la equivalencia en la forma contrapositiva:

Teorema. Para cualquier $d\in\mathbb N$ las siguientes afirmaciones son equivalentes:
(1) existe un dígrafo débilmente conexo localmente finito $G$ que contiene un vértice $x$ de grado exterior $\deg^+(x)=d$ tal que $|N^+(y)|\gt|N^{++}(y)|$ para todos los vértices $y$ en $G$ ;
(2) para cada $n\in\mathbb N$ existe un dígrafo finito $F$ que contiene un vértice $x$ con grado exterior $\deg^+(x)=d$ tal que $|N^+(y)|\gt|N^{++}(y)|$ para todos los vértices $y$ en $F$ con $d(x,y)\le n$ .

Prueba.
(1) $\implies$ (2): Basta con tomar el subgrafo inducido por $\{y:d(x,y)\le n+1\}$ .
(2) $\implies$ (1): Para $n\in\mathbb N$ deje $\mathbb F_n$ sea la clase de digrafos finitos enraizados $(F,x)$ tal que (i) $\deg^+(x)=d$ ii) cada vértice $y$ en $F$ es accesible desde $x$ con $d(x,y)\le n+1$ y iii) $|N^+(y)|\gt|N^{++}(y)|$ siempre que $d(x,y)\le n$ . De (2) se deduce que $\mathbb F_n$ no es vacío para cada $n\in\mathbb N$ . Además, si $(F,x)\in\mathbb F_n$ y si $y$ es un vértice con $d(x,y)\le n$ y si hay un arco $y\to z$ se deduce que $|N^+(y)|\gt|N^{++}(y)|$ que $\deg^+(z)\le2\cdot\deg^+(y)-2$ . De ello se deduce que los elementos de cada $\mathbb F_n$ tienen un tamaño limitado, por lo que cada $\mathbb F_n$ es finito hasta el isomorfismo. Por último, podemos utilizar el lema del infinito de Konig para obtener una secuencia infinita creciente de digrafos finitos enraizados cuya unión es un digrafo $G$ como en (1).