Tomando el Límite de Fraisse (Fraïssé) de la clase de grafos sin Kn como subgrafo

Question

"Arreglar $n \geq 3$ y que $K_n$ sea el grafo completo de $n$ vértices Sea $\mathbb{K}_n$ sea la clase de todos los grafos simples finitos que NO tienen $K_n$ como un subgrafo.

Sea $\Gamma_n$ sea el límite de Fraisse de $\mathbb{K}_n$ . Demuestre que $\Gamma_n$ es el único grafo tal que

1. Todo subgrafo finito de $\Gamma_n$ está en $\mathbb{K}_n$ y
2. Si $X$ y $Y$ son conjuntos finitos disjuntos de vértices de $\Gamma_n$ y $K_{n-1}$ no es incrustable en la restricción de $\Gamma_n$ a $X$ entonces hay un vértice en $\Gamma_n$ que se une a cada vértice de $X$ y a ningún vértice en $Y$ ."

Creo que he resuelto la pregunta 1, parece bastante sencilla. Por definición, todos los subgrafos inducidos (finitos) de $\Gamma_n$ estará en $\mathbb{K}_n$ y esto se puede extender fácilmente a todos los subgrafos.

No sé muy bien cómo enfocar la pregunta 2, la condición " $K_{n-1}$ no es incrustable" me está despistando. Estoy pensando que tenemos que utilizar el hecho de que $\Gamma_n$ es homogénea. He demostrado que $\Gamma_n$ es regular, por si sirve de ayuda.

Si es necesario, he aquí una definición del límite de Fraisse de la Teoría de Modelos: "Sea $L$ sea una firma contable, y sea $\mathbb{K}$ sea un conjunto no vacío, finito o contable, finitamente generado $L$ -que tiene la propiedad hereditaria, la propiedad de integración conjunta y la propiedad de fusión (véase aquí para las definiciones). Entonces existe un $L$ -estructura $\mathcal{D}$ (llamado límite de Fraisse de $\mathbb{K}$ ), única hasta isomorfismo, tal que

• $\mathcal{D}$ es como máximo contable.
• $\mathbb{K} = \text{age}(\mathcal{D})$ Eso es, $\mathbb{K}$ es el conjunto de todas las subestructuras finitamente generadas de $\mathcal{D}$ . Véase también aquí para una definición.
• $\mathcal{D}$ es homogénea; es decir, cualquier isomorfismo entre subestructuras finitamente generadas de $\mathcal{D}$ se extiende a un automorfismo de $\mathcal{D}$ ."

En el lenguaje de los grafos, un $L$ -es un grafo, y una subestructura finitamente generada es un subgrafo inducido.

Gracias.

Answer 1

Te explicaré por qué $\Gamma_n$ cumple la propiedad 2.

Supongamos que $X$ y $Y$ son subconjuntos disjuntos de $\Gamma_n$ y $K_{n-1}$ no es incrustable en el subgrafo inducido en $X$ . Sea $G$ sea el subgrafo inducido en $X\cup Y$ y que $H$ sea el gráfico obtenido a partir de $G$ añadiendo un nuevo vértice $v$ y nuevas aristas que conectan $v$ a cada elemento de $X$ (pero ningún elemento de $Y$ ). A continuación, puede comprobar que $K_n$ no es incrustable en $H$ .

Así que $H\in \mathbb{K}_n$ y, por tanto, existe una incrustación $f\colon H\to \Gamma_n$ . Sea $g\colon G\to \Gamma_n$ sea la restricción de $f$ a $G$ . Entonces $g\colon G\to f(G)$ es un isomorfismo, por lo que se extiende a un automorfismo $\sigma\colon \Gamma_n\cong \Gamma_n$ . Sea $w = \sigma^{-1}(v)$ . Entonces tenemos $wEx$ para todos $x\in X$ y $\lnot wEy$ para todos $y\in Y$ .

Así que ya sabes que $\Gamma_n$ satisface las propiedades 1 y 2. Por supuesto, no has terminado con el problema - todavía tienes que demostrar que $\Gamma_n$ es el único (¡contable!) que satisfaga las propiedades 1 y 2. Pista: utilizar un argumento de ida y vuelta.