3 votos

Los grafos aleatorios no son incontablemente categóricos

¿Existe una prueba sencilla de que la teoría de grafos aleatorios no es $\lambda$ -categórico para incontable $\lambda$ ?

4voto

Shery Puntos 16

Que esto cuente o no como una prueba sencilla dependerá probablemente de tu formación.

Una teoría contable incontablemente categórica es necesariamente $\omega$ -estable, de la que el grafo aleatorio está muy lejos, lo que es fácil de ver directamente. Alternativamente, se puede observar que ningún tipo no algebraico es estacionario (pero eso requiere una caracterización de la bifurcación, que requiere cierto esfuerzo establecer).

2voto

GreenAlien Puntos 3

No estoy seguro de que esto cuente como una prueba sencilla, pero desde luego es (más) elemental.

Lema: Dado un gráfico $G$ de cardinalidad $\lambda$ existe un grafo $H$ que es un modelo de la teoría del grafo aleatorio tal que $G$ es un subgrafo inducido de $H$ y $|H|=\lambda$ .

Prueba del lema: Construimos $H$ como una unión creciente de grafos $\{H_n:n\in\mathbb{N}\}$ construido inductivamente. Comenzamos con $H_0=(V(G),E(G))$ . Suponiendo ahora que $H_n$ se ha construido, dejemos que $\{A_n^\alpha:\alpha<\kappa\}$ sea una enumeración de todos los subconjuntos finitos de $V(H_n)$ . Construimos $H_{n+1}$ como sigue:

  • $V(H_{n+1})=V(H_n)\cup\{a_{n+1}^\alpha:\alpha<\kappa\}$ donde los elementos $a_{n+1}^\alpha$ son nuevos vértices que no están en $V(H_n)$ .
  • $E(H_{n+1})=E(H_n)\cup \{(a_{n+1}^\alpha,x):\alpha<\kappa,x\in A_n^\alpha\}$ . Es decir, el nuevo elemento $a_{n+1}^\alpha$ está conectado con todos los elementos de $A_n^\alpha$ y no está conectado a los elementos de $V(H_n)\setminus A_n^\alpha$ . En esta fase no se añaden más aristas. (En particular, cualesquiera dos nuevos vértices distintos $a_{n+1}^\alpha,a_{n+1}^\beta$ no están conectados. Esto será importante más adelante)

Por último, tomamos $\displaystyle{H=\bigcup_{n\in\mathbb{N}}H_n}$ .

Tenga en cuenta que $G=H_0$ es un subgrafo inducido de $H$ ya que las nuevas aristas se encuentran siempre entre nuevos elementos de la construcción. También, $H$ es un modelo del grafo aleatorio, porque dados subconjuntos finitos disjuntos $X,Y$ de $V(H)$ hay $n\in\mathbb{N}$ y $\alpha<\kappa$ tal $X=A_n^\alpha$ y $Y\subseteq V(H_n)\setminus A_n^\alpha$ y así $a_{n+1}^\alpha\in V(H)$ está conectado a todos los vértices de $X$ y no conectado a ningún vértice de $Y$ . $\square$

Ahora, dejemos que $\lambda$ sea un cardinal arbitrario incontable. Sea $G_1$ sea un grafo completo de cardinalidad $\lambda$ y que $G_2$ sea un grafo con $\lambda$ muchos vértices pero ninguna arista. Consideremos los modelos $H_1,H_2$ del grafo aleatorio proporcionado por la construcción del Lemma anterior, con $G_1\subseteq H_1$ y $G_2\subseteq H_2$ como subgrafos inducidos.

Supongamos que $f:H_1\to H_2$ es un isomorfismo, y sea $\{x_\alpha:\alpha<\lambda\}$ sea una enumeración de $G_1$ . Entonces, $f(G_1)$ es un grafo completo de cardinalidad $\lambda$ contenida en $H_2$ . Por la construcción, $H_2$ se obtiene como la unión de una secuencia contable creciente de grafos $\{H_{2,n}:n\in\mathbb{N}\}$ empezando por $H_{2,0}=G_2$ . Así que.., $|\{f(x_\alpha):\alpha<\lambda\}\cap V(H_{2,0})|\leq 1$ y por el principio de Piggeonhole hay alguna $k\in\mathbb{N}$ tal que $$|\{f(x_\alpha):\alpha<\lambda\}\cap (V(H_{2,k+1})\setminus V(H_{2,k}))|\geq \aleph_1.$$ Esto es una contradicción, porque en cada etapa no puede haber dos elementos nuevos que estén conectados.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X