Una relación unaria es un subconjunto

El enunciado, textual: «Sea $τ = (\emptyset, \emptyset, {r, R}, {(r, 2), (R, 1)})$ .

¿Cuántas estructuras de tipo $τ$ con universo igual a ${1, 2, 3, 4, 5, 6, 7, 8, 9}$ hay? (Puede usar el Lema 1 de la Guía 8)
¿Alguna de ellas es grafo bicoloreado?
Cuales de ellas son "esencialmente" grafos bicoloreados
De una biyección entre el conjunto formado por todos los grafos bicoloreados y un subconjunto del conjunto de todas las estructuras de tipo $τ$ ».

Es el mismo molde que el Ejercicio 17, que tiene el Lema 1 con su prueba y la idea de armar y desarmar la interpretación. Lo nuevo acá son dos cosas: el tipo tiene dos nombres de aridades distintas, y aparece un inciso que pide describir.

01 · Antes de resolver: la aridad de cada nombre

Lo primero es leer la cuarta coordenada del tipo, la que da las aridades: $r$ es binario y $R$ es unario. Una relación unaria sobre $A$ es un subconjunto de $A^{1}$ , o sea de $A$ : el conjunto de los elementos pintados de rojo. Contar como si las dos fueran binarias da $2^{81} \cdot 2^{81} = 2^{162}$ , y es el error que el ejercicio está esperando.

Los otros tres incisos son los del molde. (b) pregunta por la identidad estricta, y la respuesta es no. (c) pide una descripción: una condición sobre $(A, i)$ que se pueda chequear, no un ejemplo. Y (d) pide la biyección, con el universo libre: el dominio son todos los grafos bicoloreados, sobre cualquier conjunto.

02 · Las herramientas

La estructura de tipo τ (Guía 8): un par $(A, i)$ con $A$ no vacío e $i$ una función con dominio ${r, R}$ tal que $i (r) \subseteq A^{2}$ e $i (R) \subseteq A$ . Como conjunto, $i = {(r, i (r)), (R, i (R))}$ . Los nombres van en letra derecha para no confundirlos con lo que nombran.

El grafo bicoloreado (Guía 7). Un grafo es un par $(G, E)$ con $G$ no vacío y $E \subseteq G^{2}$ irreflexiva y simétrica. Un bicoloreo de $(G, E)$ es un $B \subseteq G$ tal que, cualesquiera sean $x, y \in G$ , si $(x, y) \in E$ entonces $x \in B$ e $y \notin B$ , o bien $x \notin B$ e $y \in B$ . Un grafo bicoloreado es una terna $(G, E, B)$ con $(G, E)$ un grafo y $B$ un bicoloreo suyo. Se piensa a $B$ como el conjunto de los rojos.

El Lema 1 de la Guía 8: (1) hay $| B |^{| A |}$ funciones con dominio $A$ e imagen contenida en $B$ , si $A$ y $B$ son finitos no vacíos; (2) hay $2^{| A |}$ subconjuntos de un conjunto finito $A$ . La prueba, con la función característica, está en el Ejercicio 17.

Esencialmente. La Guía 8 da el ejemplo: $({1, 2}, i)$ con $i = {(r, {(1, 2), (2, 1)}), (R, {1})}$ no es un grafo bicoloreado, pero la terna $({1, 2}, i (r), i (R))$ sí, y «a nivel de información» son lo mismo. Las estructuras así son los modelos de la teoría elemental de los grafos bicoloreados, cuyos axiomas son tres sentencias elementales:

\forall x \neg r (x, x) \forall x \forall y (r (x, y) \to r (y, x))

\forall x \forall y (r (x, y) \to ((R (x) \land \neg R (y)) \lor (\neg R (x) \land R (y))))

03 · La mariposa

Para (a): dibujar lo que se elige. Con $A = {1, \dots, 9}$ fijo, elegir la estructura es elegir dos cosas, cada una por su lado: una grilla de $9 \times 9$ para $i (r)$ , con una casilla por par, y una fila de $9$ para $i (R)$ , con una casilla por elemento. Son $81 + 9 = 90$ casillas, cada una encendida o apagada, y ninguna condiciona a otra:

2^{81} \cdot 2^{9} = 2^{90}

Son 1 237 940 039 285 380 274 899 124 224, veintiocho cifras. El exponente es la suma de lo que cada nombre aporta: $| A |^{2}$ por el binario, $| A |^{1}$ por el unario.

Para (b): contar coordenadas. Un grafo bicoloreado es una terna; una estructura, un par. La Guía 8 usa exactamente este argumento con los reticulados terna: un par no es una 3-upla. No hay nada que mirar adentro.

Para (c): desarmar y preguntar. Se desarma $i$ y se pregunta si la terna $(A, i (r), i (R))$ es un grafo bicoloreado. Desplegado, son tres condiciones: $i (r)$ irreflexiva, $i (r)$ simétrica, y cada par de $i (r)$ con un extremo dentro de $i (R)$ y el otro fuera. Las dos primeras dicen que hay un grafo; la tercera, que el subconjunto elegido lo bicolorea. Ojo con lo que dice la tercera: no alcanza con que el grafo sea bicoloreable, el $i (R)$ que vino tiene que bicolorearlo. El mismo grafo con dos rojos distintos son dos estructuras distintas, y puede que una sí y la otra no.

¿Cuántas son? Acá hay cuenta cerrada. Fijado $i (R)$ con $k$ elementos, las aristas permitidas son las que van de un rojo a un no rojo: $k (9 - k)$ pares no ordenados. Cada arista se pone en las dos direcciones o en ninguna —simetría—, nunca hay lazos, y cualquier subconjunto de esas aristas sirve. Eso da $2^{k (9 - k)}$ maneras, y hay $(\binom{9}{k})$ maneras de elegir los $k$ rojos:

\sum_{k = 0}^{9} (\binom{9}{k}) 2^{k (9 - k)} = 309 465 602

Trescientos nueve millones, de un total de veintiocho cifras. La misma fórmula con $n$ en lugar de $9$ se contrastó contra el recorrido completo de las $2^{n^{2} + n}$ estructuras, evaluando en cada una los tres axiomas como fórmulas:

Universo	Estructuras	Modelos	Fórmula
{1}	4	2	2
{1, 2}	64	6	6
{1, 2, 3}	4 096	26	26
{1, …, 4}	1 048 576	162	162

Para (d): armar y desarmar, como en el Ejercicio 17, ahora con dos nombres. A la terna $(G, E, B)$ le corresponde la estructura sobre $G$ que manda $r$ a $E$ y $R$ a $B$ . La imagen es el conjunto de (c).

En el dibujo, un elemento relleno está en i(R). Lo que rompe un axioma va en rojo: un lazo, una flecha sin su vuelta, una arista entre dos del mismo color. Probá dejar el grafo fijo y mover sólo los rellenos: la misma arista pasa de permitida a prohibida, porque lo que se juzga es la pareja entera.

04 · El escarabajo

(a) Sea $A = {1, \dots, 9}$ . Una estructura de tipo $τ$ con universo $A$ es un par $(A, i)$ con $i = {(r, S), (R, T)}$ , donde $S \subseteq A^{2}$ y $T \subseteq A$ . La correspondencia $(A, {(r, S), (R, T)}) \mapsto (S, T)$ es una biyección entre esas estructuras y $𝒫 (A^{2}) \times 𝒫 (A)$ : estructuras iguales dan $i$ iguales, y evaluando $i$ en $r$ y en $R$ , pares $(S, T)$ iguales; y todo par $(S, T)$ da una estructura. Por el Lema 1 (2), $| 𝒫 (A^{2}) | = 2^{81}$ y $| 𝒫 (A) | = 2^{9}$ , porque $| A^{2} | = 81$ y $| A | = 9$ . Luego hay $2^{81} \cdot 2^{9} = 2^{90}$ estructuras de tipo $τ$ con universo $A$ .

(b) No, ninguna. Un grafo bicoloreado es una 3-upla $(G, E, B)$ , y una estructura de tipo $τ$ es una 2-upla $(A, i)$ . Una 2-upla no es una 3-upla. Lo que sí hay son estructuras esencialmente grafos bicoloreados; por ejemplo $(A, i)$ con $i (r) = {(x, y) \in A^{2} : x + y es impar}$ e $i (R) = {1, 3, 5, 7, 9}$ : la relación es irreflexiva ( $x + x$ es par), simétrica ( $x + y = y + x$ ), y si $x + y$ es impar, uno de los dos es impar y el otro par, o sea exactamente uno está en $i (R)$ .

(c) Son las estructuras $(A, i)$ de tipo $τ$ tales que $(A, i (r), i (R))$ es un grafo bicoloreado. Es decir, las que cumplen:

$(x, x) \notin i (r)$ para todo $x \in A$ ;
si $(x, y) \in i (r)$ , entonces $(y, x) \in i (r)$ ;
si $(x, y) \in i (r)$ , entonces $x \in i (R)$ e $y \notin i (R)$ , o bien $x \notin i (R)$ e $y \in i (R)$ .

Equivalentemente, los modelos de la teoría elemental de los grafos bicoloreados. Con universo ${1, \dots, 9}$ son $\sum_{k = 0}^{9} (\binom{9}{k}) 2^{k (9 - k)} = 309 465 602$ .

(d) Sea $𝒮$ el conjunto de las estructuras de (c), con universo cualquiera. Para cada grafo bicoloreado $(G, E, B)$ definamos

Φ ((G, E, B)) = (G, {(r, E), (R, B)})

Está bien definida y cae en 𝒮. $G$ es no vacío, $E \subseteq G^{2}$ es una relación binaria sobre $G$ y $B \subseteq G$ una unaria, así que ${(r, E), (R, B)}$ es una función con dominio ${r, R}$ que respeta las aridades: $Φ ((G, E, B))$ es una estructura de tipo $τ$ . Desarmada da $(G, E, B)$ , que es un grafo bicoloreado; luego está en $𝒮$ .

Es inyectiva. Si $Φ ((G, E, B)) = Φ ((G^{'}, E^{'}, B^{'}))$ , igualando coordenadas $G = G^{'}$ y ${(r, E), (R, B)} = {(r, E^{'}), (R, B^{'})}$ . Evaluando esa función en $r$ sale $E = E^{'}$ , y en $R$ , $B = B^{'}$ . Luego las ternas son iguales.

Es sobreyectiva sobre 𝒮. Sea $(A, i) \in 𝒮$ . Entonces $(A, i (r), i (R))$ es un grafo bicoloreado, y como el dominio de $i$ es ${r, R}$ , $i = {(r, i (r)), (R, i (R))}$ . Por lo tanto $Φ ((A, i (r), i (R))) = (A, i)$ .

Luego $Φ$ es una biyección entre el conjunto de todos los grafos bicoloreados y el subconjunto $𝒮$ de las estructuras de tipo $τ$ , con inversa $(A, i) \mapsto (A, i (r), i (R))$ . ∎

05 · Lo que se lleva a otros ejercicios

La aridad pone el exponente. Un nombre de relación $n$ -aria aporta $2^{| A |^{n}}$ . Con dos nombres, los exponentes se suman: $2^{81 + 9}$ . Es la receta del Ejercicio 17 con un término más. En el Ejercicio 19 lo que cambia es la base.

El coloreo es parte del dato. Una estructura esencialmente bicoloreada no es «un grafo que se puede pintar»: es un grafo junto con una pintura que funciona. Por eso el conteo de (c) suma sobre los rojos y no sobre los grafos. Para saber cuándo un grafo admite alguna pintura, el obstáculo son los ciclos impares, y el triángulo no es el único.

Lo que hace perder puntos. Contar $2^{162}$ tratando a $R$ como binaria. Contestar en (b) con un ejemplo de estructura esencialmente bicoloreada. En (c), dar sólo un ejemplo, o pedir que $i (r)$ «sea bipartito» sin atar la condición a $i (R)$ . En (d), no nombrar el subconjunto, o fijar el universo.

Para tener a mano

$R$ es unaria: $i (R) \subseteq A$ , y aporta $2^{9}$ . $r$ es binaria y aporta $2^{81}$ . Total, $2^{90}$ .
Ninguna estructura es un grafo bicoloreado: es un par, y un grafo bicoloreado es una terna.
Esencialmente: $i (r)$ irreflexiva y simétrica, y cada par de $i (r)$ con exactamente un extremo en $i (R)$ . Son los modelos de los tres axiomas.
Sobre nueve elementos son $\sum_{k = 0}^{9} (\binom{9}{k}) 2^{k (9 - k)} = 309 465 602$ : se elige el conjunto de rojos y después cualquier juego de aristas entre rojos y no rojos.
La biyección: $(G, E, B) \mapsto (G, {(r, E), (R, B)})$ , con universo cualquiera.