1 INDEPENDENCIA PROMEDIO DE GRAFOS Y POLINOMIO DE JONESINDEPENDENCIA PROMEDIO DE GRAFOS Y POLINOMIO DE JONES. APLICACIONES EN INGENIERÍA Nadia Srour Calvo

2 Observemos las siguientes moléculas:Una es la imagen especular de la otra. ¿Son la misma molécula?

3 Matemáticamente podemos abordar este problema mediante el polinomio de Jones. Jones (medalla Field en 1990) encontró un modo de asociar a cada nudo K un polinomio VK(t) = amtm aMtM Recordar: dos nudos equivalentes tienen el mismo polinomio de Jones.

4 Si K. es la imagen especular del nudo K, entonces VKSi K* es la imagen especular del nudo K, entonces VK*(t) se obtiene de VK(t) intercambiando t y t-1. K K* VK(t) = t + t3 – t4 VK*(t) = t–1 + t–3 – t–4 En consecuencia, si VK(t) no es simétrico en la variable t, entonces VK(t) ≠ VK*(t) y por tanto K ≠ K*.

5 De un nudo o enlace K, podemos obtener un grafo GK mediante un proceso denominado suavización por A-cuerdas: K GK A los grafos obtenibles por este proceso los llamaremos grafos convertibles.

6 Cada grafo G lleva asociado un número entero I(G) llamado independencia promedio de G. A cada subconjunto de vértices independiente de G le asociamos un 1 si su cardinal es par, un -1 si es impar. I(G) se obtiene sumando todos estos ±1. Grafo lineal L6 I(L6) = 1 |C| C Paridad Contribución  1 {1}, {2}, {3}, {4}, {5}, {6} –1 –6 2 {1,3}, {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6} 10 3 {1,3,5}, {1,3,6}, {1,4,6}, {2,4,6} –4 4,5,6 No hay 1, –1, 1

7 Teorema (Bae, Morton) aM = ± I(GK) am = ± I(GK*)Corolario K no tiene simetría especular si |I(GK)| ≠ |I(GK*)| En efecto, |I(GK)| ≠ |I(GK*)| ⇒ aM ≠ am ⇒ VK(t) ≠ VK*(t) ⇒ K ≠ K*

8 NUDO O ENLACE MOLECULAR KMOLÉCULA GRAFO GK GRAFO GK* POLINOMIO DE JONES DEL NUDO K VK(t) =amtm+...+aMtM TEOREMA aM = ± I(GK) am = ± I(GK*) I(GK) I(GK*) INDEPENDENCIAS PROMEDIO CONSECUENCIA Si | I(GK) | ≠ | I(GK*) |, entonces la molécula no presenta simetría especular

9 Herramientas para el cálculo de I(G)Ley de recursión I (G) = I (G – v) – I (G – Nv) Ley de multiplicación I (G1 ∪ G2) = I (G1) · I (G2) Ley de duplicación I (G) = I (G – w) si w duplica a v

10 Ejemplo 1. Leyes de duplicación y multiplicaciónI (L6) = I (L3) · I (L2) = (– 1) · (– 1) = 1 En general I (Ln) = –I (Ln-3) = I (Ln-6)

11 Ejemplo 2. Ley de recursiónI (H) = I (L5) – I (L3) = 1 – (– 1) = 2

12 Planteamiento del problema matemáticoEncontrar grafos convertibles con independencia promedio arbitraria Solución conocida Gr (r hexágonos) I(Gr) = r + 1 G1 = H

13 MEJORA DE LA SOLUCIÓN N4 Esta solución mejora la anterior en el sentido de que tiene menor número de vértices. La construcción se basa en acoplar un Gr–1 por cada factor primo r de I(G). N6 N8

14 I (N6) = I (N6 – w) – I (N6 – Nw) I (N6) = 2 · 3 · (–1) · (–1) – 0 = 6IDEA En general, I(Nk) = I(Nk – w) – I(Nk – Nw) = k – 0 = k I(Nk – w) = (-1)2 · ∏ factores primos de k = k I(Nk – Nw) = 0 por quedar vértices aislados

15 Tabla comparativa de las soluciones

16 Programación con MATLABHemos elaborado dos programas que nos han permitido probar lo siguiente: Los grafos G1 y G2 son los grafos más simples (con menos vértices) con independencias promedio 2 y 3 respectivamente. G1 G2

17 ¿QUÉ GRAFOS SON CONVERTIBLES?CICLOS PUROS Los vértices rojos constituyen un ciclo puro en el grafo F, no en G. Representación estándar de un ciclo puro

18 TEOREMAS PARA DESCARTAR GRAFOS NO CONVERTIBLESTodo grafo convertible es bipartido. Teorema del vértice triple Teorema de los índices de conexión Teorema de perpendicularidad

19 Teorema del vértice tripleEl vértice central es adyacente a tres vértices de un ciclo puro: el grafo no es convertible

20 Teorema de los índices de conexiónÍndices de conexión i = 12, j = 11, k = 6. Como todos son mayores que tres, el grafo no es convertible.

21 Teorema de perpendicularidadLos vértices adyacentes a los vértices x e y alternan en un ciclo puro: el grafo no es convertible