Las configuraciones de Truemper y sus delta-matroides asociados

Ponente(s): Ma. Guadalupe Rodríguez Sánchez

Sea G una gráfica simple. Sea OG=O una orientación de sus aristas. Para cada ciclo C de G, OC+ es el conjunto de aristas orientadas en el sentido de las manecillas del reloj y OC- el complemento en el ciclo. Se dice que la orientación de G es compatible si se cumple que, para cada ciclo par, existe una orientación O tal que |O+| ≈ |O-| ≈ 0 (mod 2). Una gráfica theta consiste en tres caminos L1,L2,L3, entre dos vértices no adyacentes u y v tales que solo se intersectan en u y v, para 1 ≤ i < j ≤ 3. Una pirámide consta de un 3-ciclo formado por los vértices u1,u2,u3 y tres caminos L1,L2,L3, donde Li es un camino de ui a v para 1 ≤ i ≤ 3 y tal que los vértices de Lj1,Lj2 solo se intersectan en v, para 1 ≤ j1 < j2 ≤ 3. Un prisma consta dos 3-ciclos disjuntos C1 y C2 cuyos vértices son u1,u2,u3 y v1,v2,v3 respectivamente; y tres caminos L1,L2,L3, disjuntos donde Li es un camino de ui y vi para 1 ≤ i ≤ 3. Una rueda parcial W consiste en un ciclo inducido C y un vértice u, tal que u no pertenece a C tal que NW(u) ⊆ V (C) y | NW (x)| ≥ 2, donde V(C) es el conjunto de vértices de C. Al conjunto de gráficas theta, pirámides, prismas y ruedas parciales se les conoce como configuraciones de Truemper. A toda configuración de Truemper se le puede asociar un delta-matroide a través de su matriz de adyacencia. Se dice que una configuración G es IO-compatible si su delta-matroide asociado es representable sobre los campos GF(2) y GF(3). Así, si el universo de trabajo está formado por las configuraciones de Truemper, se tiene que no todas las configuraciones son IO-compatibles. En esta plática se clasifican las configuraciones que son IO-compatibles y las que no lo son. Para las segundas se encuentran menores excluidos dentro del universo, usando el delta-matroide asociado a cada configuración.