Un grafo conectado (e infinito) $U$ se llamará $n$-universal si cualquier grafo conectado con grado $\leqslant n$ admite un encaje en $U$.
¿Existe un grafo 3-universal con grado acotado?
Respuesta
¿Demasiados anuncios?
Creo que la respuesta es negativa.
Supongamos que existe tal grafo $G$ en el conjunto de vértices $\{v_1,v_2,\ldots\}$. Construimos nuestro grafo no-incrustable $H$ en $\{1,2,\ldots\}$ por pasos. En el paso $i$ solo se agregan finitamente muchos bordes a $H$, está conectado y tiene grados como máximo 3, y no hay una incrustación de este grafo finito $H_i$ en $G$ para la cual $1$ vaya a $i$. Explico cómo realizar el primer paso, los demás son esencialmente iguales.
Tomamos un camino largo $P=1-2-\ldots -(6N)$ y dividimos los $2N$ vértices $2,5,\ldots,6N-1$ en pares arbitrariamente. Obtenemos $(2N-1)!!$ grafos etiquetados diferentes. ¿Cuántos de ellos se pueden incrustar en $G$ de manera que 1 vaya a $v_1$? Deberíamos empezar con un camino de longitud $6N-1$ desde $v_1$ (exponencialmente muchas posibilidades), que debería ser la imagen de $P$, luego $G$ inducido por $P$ tiene linealmente muchos bordes, y por lo tanto exponencialmente muchos subconjuntos de estos bordes. Por lo tanto, solo exponencialmente muchos de estos grafos se pueden incrustar en $G$, y podemos realizar el primer paso.
