¿Es el grafo de Rado un grafo de Cayley? Si es así, ¿cómo es el grupo? (Y otras preguntas...)

Question

El gráfico aleatorio contable, también conocido como Gráfico de Rado se caracteriza como el único grafo contable en el que cada dos conjuntos finitos disjuntos $A$ y $B$ de vértices admiten un vértice $p$ conectado a cada vértice de $A$ y a ninguno en $B$ . Se trata de una especie de propiedad de saturación, y dos grafos contables cualesquiera que la exhiban son isomorfos por una divertida construcción de ida y vuelta; de hecho, cualquier isomorfismo parcial finito se extiende en esta situación a un isomorfismo completo. El mismo argumento muestra que todo grafo contable tiene muchas copias dentro del grafo de Rado. El grafo de Rado también puede describirse como el resultado casi seguro de construir una arista entre dos enteros cualesquiera con probabilidad independiente $p\in(0,1)$ , esencialmente porque la probabilidad de que se cumpla la propiedad para dos cualesquiera $A$ y $B$ es uno, ya que hay infinitas posibilidades independientes de acertar el patrón. (Nótese que, en esta pregunta, los grafos no tienen bucles triviales ni aristas paralelas).

Mis preguntas son:

• ¿Es el gráfico de Rado un Gráfico de Cayley ? Es decir, ¿se pueden orientar y etiquetar las aristas con generadores de tal manera que el grafo de Rado sea el grafo de Cayley resultante de la presentación del grupo correspondiente? (Espero que la respuesta sea afirmativa, construyendo una acción de grupo simplemente transitiva y empleando el teorema de Sabidussi, pero me interesaría ver un relato elegante de esta idea si funciona).

• Si es así, ¿el grupo resultante es único? ¿Cuál es su naturaleza?

• Por ejemplo, ¿se puede hacer del gráfico de Rado un gráfico de Cayley de un grupo con torsión? sin torsión?

• ¿Presenta el grupo un relato probabilístico, como el gráfico?

• Si el grafo de Rado es un grafo de Cayley, ¿de qué propiedades universales goza el grupo resultante similar a las propiedades universales atractivas del grafo? Por ejemplo, todo grafo de Cayley contable encuentra una copia en el grafo de Rado; ¿podemos encontrar siempre una copia cuyo etiquetado de Cayley se extiende a un etiquetado de Cayley del grafo de Rado completo?

Parece que las ideas del grafo aleatorio se extienden de varias maneras al contexto de los grafos dirigidos. Por ejemplo, se puede pedir que para cada triple disjunta de conjuntos $A$ , $B$ y $C$ hay un nodo $p$ apuntando a todos los nodos de $A$ , apuntado por todos los nodos de $B$ y sin bordes entre $p$ y los nodos en $C$ . Esta propiedad de saturación vuelve a caracterizar el grafo dirigido hasta el isomorfismo mediante una construcción de ida y vuelta. Supongo que este grafo sería también el resultado casi seguro de construir el grafo de Rado probabilísticamente, pero orientando también las aristas con probabilidad independiente $p$ .

• ¿Se ve afectada alguna de las preguntas anteriores por este cambio? Es decir, en esta versión de las preguntas, las orientaciones de los bordes ya están dadas, pero satisfacen la propiedad de saturación.

• ¿Y qué pasa con los análogos incontables del gráfico aleatorio? Por ejemplo, si se cumple la Hipótesis del Continuo, existe un grafo (único) de tamaño $\aleph_1$ que satisface la propiedad de saturación con respecto a todos los subconjuntos disjuntos contables $A$ , $B$ es decir, tener un vértice conectado a todos los vértices de $A$ y a ninguno en $B$ . ¿Es este gráfico un gráfico de Cayley, y así sucesivamente?

Answer 1

Para la cuestión de si el gráfico de Rado es el gráfico de Cayley de cualquier grupo, véase "An essay on countable B-groups" de Cameron-Johnson. Ellos demuestran

Dejemos que $G$ sea un grupo contable que no pueda ser expresado como una unión finita de trasuntos de conjuntos no principales de raíz cuadrada y un conjunto finito. Entonces el conjunto de grafos de Cayley para $G$ que son isomorfas a $R$ es residual.

(Un conjunto de raíz cuadrada no principal es el conjunto de todos los elementos del grupo que cuadran con un elemento específico no identitario).

Hay muchos grupos que satisfacen las condiciones del teorema. También te puede interesar "Homogeneous Cayley objects" de Cameron, donde trata el problema de decidir qué grupos contables pueden actuar regularmente sobre estructuras relacionales homogéneas contables.

Answer 2

Para responder a tu pregunta sobre el hecho de tener una cuenta probabilística: parece que debería funcionar fácilmente con sólo usar $(\mathbb{Z},+)$ como el grupo, con $\pm i$ que pertenece al conjunto de generadores con probabilidad $1/2$ independientemente para cada $i$ . Entonces, al igual que en la construcción del grafo aleatorio de Erdős-Rényi, para cualquier A y B uno tiene infinitas posibilidades independientes de encontrar un vértice adyacente a todo A y a ninguno de B.

Esta construcción de un grafo circulante aleatorio infinito se describe en Zhang y Huang, "Infinite circulants and their properties", Acta Math. Sinica 1995 pero no mencionan ninguna relación con el gráfico de Rado.

Answer 3

La respuesta que empecé a escribir es una combinación de la respuesta de Gjergji y la de David. Dejemos que $G$ sea un grupo contable que no sea una unión finita de los conjuntos de raíces cuadradas no principales y un conjunto finito. Entonces, como dice David, tienes infinitas posibilidades independientes de encontrar $p$ . Al igual que en el montaje original de Joel, también se pueden utilizar lanzamientos de moneda sesgados para hacer los bordes.

Me queda la duda de cuándo un grupo contablemente infinito es la unión finita de los conjuntos de raíces cuadradas no principales y un conjunto finito. Supongo que $C_2^{\infty} \times A$ es un ejemplo, si $A$ es un grupo finito que no es un grupo 2 elemental. Ciertamente, ningún elemental $p$ -(o, aditivamente, ningún espacio vectorial sobre $\mathbb{Z}/p$ ) es un ejemplo, y tampoco lo es $\mathbb{Z}^n$ . Y supongo que $\text{SL}(n,\mathbb{Z})$ tampoco es un ejemplo.

---

Hay dos tipos diferentes de grafos dirigidos, grafos con y sin 2 ciclos. La pregunta planteada considera el tipo sin 2 ciclos, pero no veo ningún problema en definir cualquiera de los dos tipos de grafos Rado en la misma clase de grupos. De hecho, se pueden tener varios tipos de grafos Rado coloreados, en los que algunos de los colores de las aristas son dirigidos y otros no. (Así, permitir 2 ciclos equivale a tener dos colores no dirigidos y un color dirigido).

No creo que eso diga mucho sobre el grupo. Dice que el gráfico de Rado tiene un grupo de automorfismo tan grande que muchos grupos actúan libremente de forma transitiva sobre él. Parece que la condición de Cameron-Johnson sobre el grupo $G$ es en realidad no sólo suficiente para una acción libremente transitiva, sino también necesaria, al menos para obtener el $n$ -de Rado coloreado para cualquier $n$ como un grafo de Cayley de $G$ . Sin embargo, los grupos $G$ que son imposibles son esencialmente imposibles por una razón local.

En cuanto a los análogos incontables del grafo aleatorio, podría suponer que las mismas construcciones siguen funcionando a veces, pero preguntaría a alguien como Joel Hamkins. :-)