Laplacianas de digrafos y topologías de Alexandrov

UNIVERSIDAD DE SEVILLA Facultad de Matem´ aticas Departamento de Geometr ´ ıa y Topolog ´ ıa Laplacianas de digrafos y topolog´ıas de Alexandrov Trabajo Fin de Grado realizado por Mar´ıa Vela Felardo Tutor: Antonio Quintero Toscano 2017-18 ´ Indice general Introducci´on 1 1. Teor´ıa de grafos 3 1.1. Definiciones b´asicas sobre grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Caminos y conceptos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3. Gradodeunv´ertice .................................. 7 1.4. Representaci´on matricial de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2. Conjuntos ordenados y digrafos 10 2.1. Definiciones b´asicas sobre estructuras ordenadas . . . . . . . . . . . . . . . . . . 10 2.2. Relacionesydigrafos.................................. 11 3. Topolog´ıa general 13 3.1. Espaciostopol´ogicos .................................. 13 3.2. Basedeunatopolog´ıa ................................. 14 3.3. Axiomasdeseparaci´on................................. 15 3.4. Aplicaciones continuas y homeomorfismos . . . . . . . . . . . . . . . . . . . . . . 16 4. Espacios de Alexandrov, ´ordenes y digrafos 17 4.1. EspaciosdeAlexandrov ................................ 17 4.2. A-topolog´ıas y pre´ordenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3. Ejemplos y tabla resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5. Laplacianas en digrafos y topolog´ıas de Alexandrov 26 5.1. Las matrices laplacianas de un digrafo . . . . . . . . . . . . . . . . . . . . . . . . 26 5.2. Conectividad fuerte en digrafos transitivos . . . . . . . . . . . . . . . . . . . . . . 27 5.3. Estructura de bloques de laplacianas . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.4. A-topolog´ıas y laplacianas en digrafos . . . . . . . . . . . . . . . . . . . . . . . . 32 5.5. Algunosejemplos.................................... 33 5.6. N´ucleos de laplacianas de digrafos transitivos . . . . . . . . . . . . . . . . . . . . 36 5.7. N´ucleos de laplacianas de digrafos transitivos y ac´ıclicos . . . . . . . . . . . . . . 39 6. Laplacianas de digrafos (caso infinito) 41 6.1. A-espacios, ´ordenes y digrafos localmente finitos . . . . . . . . . . . . . . . . . . 41 6.2. Una propuesta para extender la teor´ıa espectral de grafos infinitos a digrafos . . 43 6.2.1. Ap´endice: Operadores en espacios de Hilbert . . . . . . . . . . . . . . . . 46 Bibliograf´ıa 49 Resumen (abstract) 50 Introducci´on Las relaciones de orden aparecen en multitud de situaciones en Matem´aticas. Por ello es de inter´es buscar procedimientos para representar estas relaciones por medio de objetos matem´aticos de distinta naturaleza y aplicar los conocimientos disponibles sobre estos para el estudio de la relaci´on de orden original. Una manera muy habitual es representar las relaciones de orden por medio de grafos dirigidos. Sin embargo, es mucho menos frecuente estudiar los conjuntos ordenados usando la topolog´ıa intr´ınseca que poseen. Esta topolog´ıa fue analizada por primera vez en 1937 por P.S. Alexandrov e independientemente por A.W. Tucker [4], quienes demostraron que los conjuntos ordenados pod´ıan ser identificados como aquellos espacios topol´ogicos en los que la intersecci´on arbitraria de abiertos era tambi´en un conjunto abierto. En particular los espacios con esta propiedad han pasado a denominarse espacios de Alexandrov o A-espacios. Los espacios finitos corresponden a los conjuntos ordenados finitos y los espacios discretos son entonces los ´unicos A-espacios dotados de la propiedad de separaci´on de Hausdorff y, por tanto, los ´unicos espacios m´etricos entre los A-espacios. Como los espacios m´etricos son los espacios fundamentales del an´alisis y la geometr´ıa, los A-espacios quedaron olvidados tras el trabajo inicial de Alexandrov. Despu´es de treinta a˜nos aparecieron dos trabajos sobre la topolog´ıa algebraica de los A-espacios debidos a M. McCord y R. Stong que destacaban que, a pesar del fallo de la propiedad de Hausdorff, los A-espacios tienen propiedades de conexi´on sorprendentemente similares a los espacios de inter´es de la topolog´ıa algebraico-geom´etrica. Referimos a [8] para una referencia general sobre A-espacios y sus propiedades. Esta memoria contiene un “dicccionario” con tres entradas correpondiente a las tres facetas de los espacios de Alexandrov: la ordinal como conjuntos ordenados, la combinatoria como digrafos y la suya propia como espacios topol´ogicos. Al poderse tratar los digrafos como A-espacios, se est´a en condiciones de reescribir las construcciones y resultados de la teor´ıa de grafos en t´erminos topol´ogicos. Como una muestra de este hecho, la segunda parte de la memoria est´a dedicada a dar una detallada exposici´on de los resultados en [6] sobre matrices laplacianas de digrafos, recalcando su reformulaci´on topol´ogica. Las matrices laplacianas de un (di)grafo y sus espectros est´an entre las herramientas de la llamada teor´ıa algebraica de grafos, que es un intento de utilizar el ´algebra lineal , en particular la teor´ıa de matrices , en el estudio de las propiedades de los grafos. Dado un (di)grafo Gexisten varias matrices asociadas a su estructura combinatoria. La m´as habitual es la matriz de adyacencia, construida a partir de una indexaci´on de los v´ertices de G, colocando un 1 en el lugar (i, j) si existe una arista entre los v´ertices i-´esimo y j-´esimo y un 0 en caso contrario. En general, dada una matriz A= [aij] indexada por los v´ertices de G, se llama A-espectro de Gal conjunto de autovalores de la matriz A. Varias maneras de asociar matrices a grafos y sus correspondientes espectros puede verse en [7]. 1 2´ INDICE GENERAL Pasamos a detallar el contenido de la memoria: el Cap´ıtulo 1 recoge los resultados b´asicos sobre digrafos que hemos utilizado. La terminolog´ıa sobre conjuntos ordenados aparece en el Cap´ıtulo 2. Los requisitos de topolog´ıa est´an resumidos en el Cap´ıtulo 3. El Cap´ıtulo 4 contiene las nociones fundamentales de espacios de Alexandrov y la comparaci´on de los tres lenguajes equivalentes para su estudio. El cap´ıtulo concluye con una tabla-resumen que sirve para traducir los conceptos y resultados de un lenguaje a otro. Finalmente, en el Cap´ıtulo 5 exponemos detalladamente resultados de [6], que introduce el lenguaje de A-espacios en la teor´ıa algebraica de grafos al estudiar el espectro de un digrafo en t´erminos de su A-topolog´ıa. Los grafos infinitos son considerados en el Cap´ıtulo 6, que es solo el boceto de una posible extensi´on de la teor´ıa espectral de los grafos localmente finitos dada en [9] a los digrafos. Cap´ıtulo 1 Teor´ıa de grafos La teor´ıa de grafos constituye uno de los temas m´as importantes de la Matem´atica Discreta. Esta parte de las matem´aticas tiene su origen en un trabajo publicado en 1736 por el matem´atico suizo Leonhard Euler relacionado con el popular problema conocido como ”los siete puentes de K¨onigsberg” (para m´as detalles, consultar cualquier libro de Matem´atica Discreta como [5]). 1.1. Definiciones b´asicas sobre grafos En esta secci´on introduciremos nociones b´asicas sobre grafos (la terminolog´ıa utilizada en la teor´ıa de grafos no est´a estandarizada, pudiendo variar de unos textos a otros). Definici´on 1.1.1. Sea Vun conjunto no vac´ıo formado por elementos denominados v´ertices onodos y sea E⊆V×Votro conjunto formado por elementos denominados arcos oaristas. Entonces el par (V, E) recibe el nombre de grafo sobre V, y se indica por G= (V, E). Si E es un conjunto de pares ordenados de los elementos de V, diremos que Ges un grafo dirigido odigrafo. Dada una arista edel digrafo G, se escribe o(e) para el v´ertice inicial y t(e) para el v´ertice final. Ejemplo 1.1.2. Por ejemplo, la siguiente figura es un grafo sobre el conjunto de v´ertices V={1,2,3,4}(1.1) y cuyas aristas son el conjunto E={{1,2},{1,3},{1,4},{2,3}} (1.2) de pares no ordenados. 3 4CAP´ ITULO 1. TEOR´ IA DE GRAFOS Figura 1.1. Ejemplo 1.1.3. La figura que sigue constituye un ejemplo de digrafo sobre V={1,2,3,4}(1.3) cuyas aristas son los elementos del conjunto E={(1,2),(1,3),(1,4),(2,3),(3,2)}(1.4) de pares ordenados. Figura 1.2. La direcci´on de cada arista se indica mediante una flecha. Definici´on 1.1.4. Dado un grafo G, se dice que una arista forma un lazo cuando est´a asociada a dos v´ertices id´enticos, es decir, cuando sus extremos coinciden. Dos aristas son paralelas cuando son incidentes con los mismos v´ertices. Un grafo formado por un solo v´ertice, recibe el nombre de trivial odegenerado. Definici´on 1.1.5. Un grafo G= (V, E) es un multigrafo si, para a, b ∈Vcon a6=b, existen dos o m´as aristas de la forma (a, b), para un digrafo, o bien {a, b}, para un grafo. En lo que sigue en este trabajo, no consideraremos grafos con lazos ni multigrafos. 1.2. CAMINOS Y CONCEPTOS RELACIONADOS 5 Definici´on 1.1.6. Cuando un grafo no posee ni aristas paralelas ni lazos se dice que se trata de un grafo simple. Definici´on 1.1.7. Sea G= (V, E) un digrafo y sea x∈Vun v´ertice. Diremos que xes una fuente si no existe y∈Vtal que (y, x)∈E. Diremos que xes un sumidero si no existe y∈V tal que (x, y)∈E. Definici´on 1.1.8. Sea G= (V, E) un digrafo. Se dir´a que S⊆Ves una absorbente inferior si (y, x)∈Econ x∈Simplica que y∈S. De forma an´aloga, Se dir´a que S⊆Ves una absorbente superior si (x, y)∈Econ x∈S implica que y∈S. Definici´on 1.1.9. El dual de un digrafo G= (V, E) es un digrafo G= (V, E) donde E= {(x, y)/(y, x)∈E}. Definici´on 1.1.10. Se define homomorfismo entre grafos a una funci´on φ:G→Hentre dos grafos GyHque satisface que si uyvson dos v´ertices de Gunidos por una arista, entonces φ(u) y φ(v) son dos v´ertices de Hy tambi´en est´an unidos por una arista. An´alogamente si GyHson digrafos, φser´a homomorfismo entre digrafos si adem´as tambi´en conserva las direcciones de las aristas. Se dir´a que φes un antihomomorfismo entre digrafos si invierte las direcciones de las aristas. 1.2. Caminos y conceptos relacionados Existe una necesidad de definir conceptos sobre grafos relacionados con la forma de recorrerlos, partiendo de un origen y llegando a un destino. Definici´on 1.2.1. Dado un grafo G, se denomina camino en Gde vawa una secuencia alternada de v´ertices viy aristas eide G v1, e1, v2, e2, ..., vn, en, vn+1 (1.5) con v1=v,vn+1 =w, que contiene naristas ei={vi, vi+1},1≤i≤n. (1.6) Un camino es cerrado si v=wyn > 1. Si Ges un digrafo, un camino entre vywser´a una secuencia alternada v1e1v2...vn+1 con v1=v,vn+1 =wy cada eies una arista ordenada donde viyvi+1 son sus v´ertices. Cuando o(ei) = viyt(ei) = vi+1 se dir´a que el camino es un camino dirigido. Definici´on 1.2.2. Dado un grafo G, recibe el nombre de camino simple todo camino sin aristas repetidas, es decir, un camino que no pasa dos veces por la misma arista. Llamaremos camino elemental a todo camino simple sin v´ertices repetidos, es decir, un camino simple que no pasa dos veces por el mismo v´ertice. Nota 1.2.3. Si hay un camino simple entre dos v´ertices de un grafo, entonces tambi´en hay un camino elemental entre dichos v´ertices. La demostraci´on la podemos encontrar en [5]. Definici´on 1.2.4. Dado un grafo G, un circuito es un camino simple cerrado. Se denominar´a ciclo a todo camino elemental cerrado. Una cadena es un camino elemental abierto. 12 CAP´ ITULO 2. CONJUNTOS ORDENADOS Y DIGRAFOS Proposici´on 2.2.11. Dado un conjunto Xcon una relaci´on de orden ≤, sea x∈X. Entonces el ideal principal generado por x,x↓, se corresponde con el dominio de influencia bajo xen el digrafo asociado. De igual forma, el filtro principal generado por x,x↑, se corresponde con el dominio de influencia sobre xen el digrafo asociado. Ejemplo 2.2.12. Dado el siguiente preorden: a≤b, a ≤c, a ≤d, a ≤e, a ≤f, b ≤fyc≤e, obtenemos el digrafo Figura 2.1. Podemos observar que, efectivamente, los elementos maximales del preorden son los sumideros del digrafo asociado (d,eyf) y que los elementos minimales del preorden son las fuentes en el digrafo asociado (a). Adem´as, por ejemplo, tenemos que el conjunto {c, d}es una anticadena en el preorden y no existe un camino dirigido entre cyd(tambi´en se cumple con el resto de anticadenas). Tambi´en podemos observar que el conjunto decreciente {a, d}es una absorbente inferior en el digrafo (an´alogamente el conjunto creciente {c, e}es una absorbente superior en el digrafo asociado).Por ´ultimo, podemos ver que c↓={a, c}, que es el dominio de influencia bajo cen el digrafo, de la misma forma vemos que c↑={c, e}, que es el dominio de influencia sobre cen el digrafo. Cap´ıtulo 3 Topolog´ıa general En esta secci´on veremos las definiciones y resultados principales de topolog´ıa que usaremos en este trabajo. Estos pueden consultarse, por ejemplo, en [1] o [2]. Aqu´ı solo demostraremos los resultados que no suelen aparecer en la bibliograf´ıa habitual. 3.1. Espacios topol´ogicos Definici´on 3.1.1. Una topolog´ıa sobre un conjunto Xes una familia de subconjuntos de X, T, que cumple las siguientes propiedades: 1. ∅yXest´an en T. 2. La intersecci´on finita de conjuntos de Test´a en T. 3. La uni´on arbitraria de conjuntos de Test´a en T. Al par (X, T) se le llama espacio topol´ogico. Los conjuntos de Tson llamados conjuntos abiertos de (X, T). Notaci´on 3.1.2. Cuando la topolog´ıa Tse supone impl´ıcitamente, o no es relevante en el contexto, denotamos simplemente por Xal espacio topol´ogico, que tambi´en es abreviadamente referido como “espacio”. Los dos ejemplos extremos de topolog´ıa son los siguientes: La topolog´ıa discreta en Xes la topolog´ıa en la que todos los conjuntos son abiertos, o equivalentemente, todos los conjuntos unitarios son abiertos. La topolog´ıa indiscreta otrivial en Xes la topolog´ıa en la que ´unicamente ∅yXson los abiertos. Es obvio que la topolog´ıa discreta es la mayor topolog´ıa posible, y la indiscreta, la menor. Recordemos que un espacio topol´ogico Xse dice compacto si de todo recubrimiento de X por abiertos se puede extraer un subrecubrimiento finito. Definici´on 3.1.3. Al complementario de un conjunto abierto en el espacio topol´ogico (X, T) se le llama conjunto cerrado. N´otese que una topolog´ıa es discreta si y solo si cualquier conjunto es cerrado. 13 14 CAP´ ITULO 3. TOPOLOG´ IA GENERAL La familia Fde cerrados de un espacio cumple las siguientes propiedades: 1. ∅yXest´an en F. 2. La uni´on finita de conjuntos de Fest´a en F. 3. La intersecci´on arbitraria de conjuntos de Fest´a en F. Definici´on 3.1.4. Si (X, T) es un espacio topol´ogico, dados A⊆Xyx∈X, se dice que x es interior a A en (X, T) (o que Aes entorno de x) si existe un abierto Gcon x∈G⊆A. Se llama interior de Aen (X, T) al conjunto int(A) = {x∈X;xes interior a A}. Una familia V de entornos de xse dice base de entornos de xsi para todo entorno Nde x, existe V∈ V con V⊆N. Un conjunto A⊆Xse dice entorno de x∈Xsi x∈int(A). Por otro lado, x∈Xes llamado punto adherente aAsi todo abierto Gcon x∈Gcumple G∩A6=∅. Se llama clausura de Aal conjunto A={x∈X;xes adherente a A}. Lema 3.1.5. Se cumple que int(A)⊆A⊆A. Un conjunto A⊆Xes cerrado en (X, T) si y solo si A=Ay es abierto si y solo si int(A) = A. 3.2. Base de una topolog´ıa La topolog´ıa de los espacios de inter´es (por ejemplo, los espacios m´etricos) no est´a dada expl´ıcitamente sino descrita a partir de ciertos abiertos generadores de acuerdo con la siguiente definici´on. Definici´on 3.2.1. Dado un espacio topol´ogico (X, T), una subfamilia B ⊆ T se dice que es una base de la topolog´ıa T(o base de abiertos) si todo abierto no vac´ıo de Tes uni´on de abiertos de B. Lema 3.2.2. Bes una base de Tsi y solo si para cada abierto Uy para cada x∈U, existe un B∈ B tal que x∈B⊆U. Definici´on 3.2.3. Una base Bde Tse dice minimal si para cualquier B∈ B la familia B−{B} deja de ser base de T. Ejemplo 3.2.4. Una base de la topolog´ıa discreta es la formada por todos los conjuntos unitarios {x},x∈X. Adem´as, esta base es minimal. Definici´on 3.2.5. Una base Bpara una topolog´ıa sovre Xes una colecci´on de subconjuntos de X, llamados elementos b´asicos, que cumplen las siguientes propiedades: 1. Para x∈X, hay al menos un elemento b´asico Bque contiene a x. 2. Si xpertenece a la intersecci´on de dos elementos b´asicos B1yB2, entonces existe un elemento b´asico B3que contiene a x, tal que B3⊆B1\B2. Si Bsatisface estas dos condiciones, la familia T(B) formada por los conjuntos U⊆Xtales que para cada x∈Uexiste B∈ B con x∈B⊆U, es la ´unica topolog´ıa sobe Xque tiene a B como base y se denomina topolog´ıa generada por B. A˜nadiendo una tercera condici´on a la Definici´on 3.2.5 se tiene la siguiente caracterizaci´on de base minimal para una topolog´ıa: 3.3. AXIOMAS DE SEPARACI ´ ON 15 Lema 3.2.6. Un conjunto Bde subconjuntos no vac´ıos de Xes una base minimal para una topolog´ıa si y solo si se cumplen las tres propiedades siguientes: 1. Todo punto de Xest´a en alg´un conjunto Bde B. 2. Si xpertenece a la intersecci´on de dos elementos B1, B2∈ B, entonces existe B3∈ B, tal que x∈B3⊆B1TB2. 3. Si una uni´on de conjuntos Bide Best´a tambi´en en B, entonces la uni´on es igual a uno de los Bi. Demostraci´on. Las dos primeras condiciones son las de la Definici´on 3.2.5. Vamos a probar ahora la tercera condici´on. Su pongamos que la base Bno cumple la propiedad (3), es decir, existe alg´un B0∈ B con B0=[ i∈I Bi,Bi∈ B yB06=Bi, para todo i∈I. Entonces, la familia B −{B0}sigue siendo base de la topolog´ıa T(B), luego Bno es minimal. Rec´ıprocamente, si se cumple (3) y B0es una base de T(B) con B0⊆ B, dado cualquier B∈ B tenemos B=[ α∈Λ B0 αcon B0 α∈ B0⊆ B por ser B0base. Entonces por la condici´on (3), existe α0∈Λ con B=B0 α0∈ B0. Es decir, B∈ B0, y por tanto B=B0. 3.3. Axiomas de separaci´on Es bien sabido que la unicidad de puntos l´ımite es consecuencia de la famosa propiedad de separaci´on de Hausdorff. Decimos que un espacio Xtiene esta propiedad (o que es un espacio T2) si para dos puntos distintos cualesquiera x, x0∈Xexisten abiertos G1, G2de Xtales que x∈G1,y∈G2yG1∩G2=∅. La nomenclatura T2se debe a que la propiedad de Hausdorff es parte de una jerarqu´ıa de propiedades de separaci´on que van de T0aT5, estando los espacios m´etricos en lo m´as alto de la escala. Definici´on 3.3.1. Sea (X, T) un espacio topol´ogico. 1. Xes un espacio T0si para dos puntos distintos x, y ∈X, existe un abierto Gtal que, o bien x∈Gyy /∈G, o bien y∈Gyx /∈G. 2. Xes un espacio T1si dados dos puntos distintos x, y ∈X, existen abiertos G1, G2∈(X, T) tales que: x∈G1, y /∈G1, y tambi´en y∈G2, x /∈G2. Obviamente, T2⇒T1⇒T0. Adem´as, Lema 3.3.2. Se tienen las siguientes equivalencias: 1. Xes T0si y solo si para cualesquiera dos puntos x, y ∈Xo bien x /∈ {y}, o bien y /∈ {x}. 2. Xes T1si y solo si para todo x∈X, entonces {x}es cerrado, es decir, {x}={x}, lo que a su vez equivale a pedir que para todo x∈X,{x}=∩x∈GxGsiendo Gxla familia de abiertos que contiene a x. 3. Xes T2si y solo si para todo x∈X,{x}=∩G∈GxG. 16 CAP´ ITULO 3. TOPOLOG´ IA GENERAL 3.4. Aplicaciones continuas y homeomorfismos Por medio de una topolog´ıa se da una estructura de proximidad entre los puntos de un conjunto. La aplicaciones continuas entre espacios topol´ogicos son aquellas que preservan la proximidad. Recordamos aqu´ı la definici´on general de continuidad. Definici´on 3.4.1. Sean XeYdos espacios topol´ogicos. Una aplicaci´on f:X−→ Yes continua si f−1(V) es un abierto de X, para cada abierto Vde Y. Una aplicaci´on continua es un homeomorfismo si fes biyectiva y su inversa f−1es tambi´en continua. Una clase especial de aplicaciones continuas son aquellas que determinan la topolog´ıa del espacio de llegada en funci´on de la topologia del dominio de la aplicaci´on (en particular, esta clase incluye a los homeomorfismos). Estas aplicaciones son las llamadas aplicaciones cociente. Recordemos su definici´on. Definici´on 3.4.2. Sean XeYespacios topol´ogicos y sea p:X→Yuna aplicaci´on sobreyectiva. La aplicaci´on pse dice que es una aplicaci´on cociente (o de identificaci´on) si un subconjunto U⊆Yes abierto en Ysi y solo si p−1(U) es abierto en X. Definici´on 3.4.3. Si Xes un espacio, Yun conjunto y p:X→Yes una aplicaci´on sobreyectiva, entonces existe exactamente una topolog´ıa Tsobre Yrespecto a la cual pes una aplicaci´on cociente; se denomina topolog´ıa cociente inducida por p. En particular, si “∼” es una relaci´on de equivalencia sobre un espacio topol´ogico X, el conjunto cociente X/∼con la topolog´ıa cociente inducida por la proyecci´on natural p:X−→ X/∼se denomina espacio cociente de X. Podemos describir la topolog´ıa cociente de otro modo: Un subconjunto Ude X/∼es una colecci´on de clases de equivalencia, y el conjunto p−1(U) es justo la uni´on de los representantes de las clases pertenecen a U. As´ı, el conjunto abierto caracter´ıstico de X/∼es una colecci´on de clases de equivalencia cuya uni´on es un conjunto abierto de X. N´otese que p:X−→ Yes una aplicaci´on cociente si y solo si Yes homeomorfo al espacio cociente X/∼donde “∼” es la relaci´on de equivalencia definida por x∼x0si p(x) = p(x0). La siguiente propiedad es caracter´ıstica de los espacios cociente. Proposici´on 3.4.4. Sea f:X→Yuna aplicaci´on continua compatible con la relaci´on de equivalencia “∼” sobre X, es decir, f(x) = f(x0) si x∼x0. Entonces la aplicaci´on e f:X/∼ −→ Y dada por e f([x]) = f(x) (llamada aplicaci´on inducida por f) es continua para la topolog´ıa cociente. Cap´ıtulo 4 Espacios de Alexandrov, ´ordenes y digrafos 4.1. Espacios de Alexandrov Un espacio topol´ogico es un espacio de Alexandrov oA-espacio si la topolog´ıa Tes cerrada tambi´en bajo intersecciones arbitrarias. Es decir, la intersecci´on arbitraria de abiertos es un conjunto abierto. Es obvio que todo espacio finito es un A-espacio, ya que toda intersecci´on de abiertos se puede expresar como una intersecci´on finita. Por tanto, todo lo que se establezca para A-espacios, seguir´a siendo v´alido para los espacios finitos. Ver [3] para varias referencias. En gran medida, cuando pensamos en un espacio topol´ogico, solemos considerar espacios con la propiedad de Hausdorff. Un ejemplo de esto son los espacios m´etricos. La intuici´on que solemos tener de este tipo de espacios puede resultar un poco enga˜nosa cuando tratemos con espacios de Alexandrov. Para empezar, el siguiente lema nos har´ıa dudar del inter´es de los A-espacios. Lema 4.1.1. Si un A-espacio es T1, entonces es discreto. Demostraci´on. Por el Lema 3.3.2 (2) cada {x}es abierto y cerrado. Otra caracter´ıstica distintiva de los A-espacios es la existencia de una base m´ınima para su topolog´ıa. Definici´on 4.1.2. Sea Xun A-espacio. Para todo x∈X, se define el abierto m´ınimo de x,Ux, como la intersecci´on de todos los conjuntos abiertos que contienen a x. Lema 4.1.3. Si Xes un A-espacio, entonces Ux=Uysi y solo si {x}={y}. En particular, X es T0si y solo si Ux=Uy, o, equivalentemente, x=y. Demostraci´on. Supongamos Ux=Uyy sea z∈ {x}cualquiera. Entonces tenemos que Uz∩{x} 6= ∅, es decir, x∈Uz. Utilizando nuestra hip´otesis, Ux=Uy⊆Uz. De aqu´ı obtenemos que y∈Uz. Ahora, Uz∩ {y} 6=∅. Por tanto z∈ {y}. Hemos demostrado inclusi´on {x} ⊆ {y}. La otra inclusi´on se prueba an´alogamente y tenemos la igualdad {x}={y}. Si ahora suponemos {x}={y}, entonces se sigue que y∈ {x}, y, de la misma manera x∈ {y}. Esto quiere decir que Uy∩{x} 6=∅yUx∩{y} 6=∅. Por tanto, x∈Uyey∈Uxy, por la definici´on de los abiertos m´ınimos, Ux⊆UyyUy⊆Ux; esto es, Ux=Uy. Si el espacio Xfuese T0entonces la igualdad {x}={y}equivale a x=ypor el Lema 3.3.2. Rec´ıprocamente, si Xno es T0entonces existen x, y ∈Xcon x6=yy tales que todo abierto 17 18 CAP´ ITULO 4. ESPACIOS DE ALEXANDROV, ´ ORDENES Y DIGRAFOS que contiene a xcontiene a yy viceversa; en particular, y∈Uxyx∈Uy, por lo que Ux⊆Uyy Uy⊆Uxy, por tanto, Ux=Uyaunque x6=y. Lema 4.1.4. La familia de los conjuntos abiertos m´ınimos Uxes una base del espacio X. De hecho, es la ´unica base minimal (es decir, m´ınima) de X. Demostraci´on. Ver que es base es inmediato, a partir del Lema 3.2.2. La minimalidad de Bes inmediata a partir del Lema 3.2.6. En efecto, si ∪x∈JUx=Uy, con y∈Jdebe existir x0∈J con y∈Ux0y por tanto Uy⊆Ux0. Por otra lado, Ux0⊆ ∪x∈JUx=Uyy se sigue la igualdad Uy=Ux0. Veamos que Bes la ´unica base minimal. Supongamos que existe otra base minimal M. Entonces para todo Ux∈ B existe M∈ M tal que x∈M⊆Ux. As´ı pues, M=UxyB ⊆ M. Como hab´ıamos supuesto que Mes minimal, se tiene, necesariamente, la igualdad M=B. Proposici´on 4.1.5. Xes un A-espacio si y solo si para todo punto x∈X, existe un abierto m´ınimo Uxque lo contiene. Demostraci´on. Ya sabemos por la Definici´on 4.1.2 que en todo A-espacio se puede encontrar un abierto m´ınimo para cada punto. Rec´ıprocamente, sea {Gα}α∈Λuna familia cualquiera de abiertos de X, con ∩α∈ΛGα6=∅y tomemos x∈ ∩α∈ΛGα. Entonces, Ux⊆Gα, para todo α∈Λ, y por tanto x∈Ux⊆ ∩α∈ΛGα, luego x∈int(∩α∈ΛGα). Hemos probado que ∩α∈ΛGαes un abierto. Proposici´on 4.1.6. Sea f:X−→ Yuna aplicaci´on entre A-espacios. Entonces fes continua si y solo si f(Ux)⊆Uf(x)para todo x∈X. Demostraci´on. Si fes continua, entonces f−1(Uf(x)) es abierto y x∈f−1(Uf(x)), luego Ux⊆ f−1(Uf(x)). Esto es, f(Ux)⊆Uf(x). Rec´ıprocamente, si Ω es cualquier abierto de Yyx∈f−1(Ω), tenemos f(x)∈Ω. Luego f(Ux)⊆Uf(x)⊆Ω. Aqu´ı usamos la hip´otesis y la minimalidad de Uf(x). Por tanto, Ux⊆f−1(Ω) yf−1(Ω) es abierto, lo que quiere decir que fes continua. Proposici´on 4.1.7. Si p:X−→ Yes una aplicaci´on cociente y Xes un A-espacio, entonces Ytambi´en lo es. Demostraci´on. Sea {Ωα}α∈Λuna familia de abiertos en Y, es decir, p−1(Ωα) es abierto de X para cada α∈Λ. Entonces p−1(∩α∈ΛΩα) = ∩α∈Λp−1(Ωα) es abierto de Xpor ser A-espacio. Por definici´on de topolog´ıa cociente, ∩α∈ΛΩαes abierto de X/∼. Proposici´on 4.1.8. En la proposici´on anterior, la familia de im´agenes {p(Ux)}x∈Xde la base m´ınima de Xes base m´ınima de Ysi y solo si la aplicaci´on cociente es tambi´en abierta. Recordemos que una aplicaci´on (continua o no) f:X→Yse dice abierta si para todo abierto Gde Xsu imagen f(G) es un abierto de Y. Demostraci´on. Si la familia dada fuese una base m´ınima entoces cada imagen p(Ux) ser´ıa un conjunto abierto y como todo abierto Gde Xse puede expresar como una union G=∪x∈JUx se sigue que p(G) = ∪x∈Jp(Ux) es abierto. Para probar el rec´ıproco, sabemos que cada p(Ux) es un abierto que contiene a p(x). Si Up(x) es el abierto m´ınimo de p(x) en Ydado por la Proposici´on 4.1.7, la continuidad de pnos dice que p(Ux)⊆Up(x)por la Proposici´on 4.1.6. La minimalidad de Up(x)nos da p(Ux) = Up(x). 4.2. A-TOPOLOG´ IAS Y PRE ´ ORDENES 19 Ejemplo 4.1.9. Un ejemplo donde p(Ux) no es abierto es la siguiente aplicaci´on cociente. Sean los espacios finitos X={a, b, c, d}eY={x, y, z}con topolog´ıas TX={∅, X, {a},{a, b}} y TY={∅, Y, {x}}. Entonces p:X→Ydada por p(a) = x,p(b) = p(c) = yyp(d) = zes una aplicaci´on cociente y p(Ub) = {x, y}no es abierto de Ycon Ub={a, b}. Proposici´on 4.1.10. Todo A-espacio Xtiene un cociente can´onico X0que es T0. Demostraci´on. Definimos la relaci´on x∼ysi Ux=Uy. Sea X0=X/∼el espacio cociente correspondiente. Sabemos que X0es un A-espacio por la Proposici´on 4.1.7. M´as a´un, la proyecci´on can´onica p:X−→ X0es una aplicaci´on abierta ya que p−1(p(Ux)) = Ux, pues si y∈p−1(p(Ux)) entonces existe z∈Uxcon p(y) = p(z), esto es, Uy=Uz⊆Uxy as´ı y∈Ux. Tenemos, por la Proposici´on 4.1.8, que {p(Ux)}x∈Xes la base m´ınima de X0. El espacio X0es T0como consecuencia inmediata del Lema 4.1.3 pues p(Ux) = p(Uy) es equivalente a [x] = [y]. 4.2. A-topolog´ıas y pre´ordenes Dedicaremos la secci´on a describir la identificaci´on entre A-espacios y conjuntos preordenados debida a Alexandrov y Tucker [4]. Lema 4.2.1. Si ≤es un preorden en X, entonces la familia de los ideales principales en X: ↓x={y∈X;y≤x}, x ∈X es base m´ınima para una A-topolog´ıa sobre Xpara la cual los abiertos son exactamente los conjuntos decrecientes (o, equivalentemente, los cerrados son los conjuntos crecientes). M´as a´un, si “≤” es un orden parcial, entonces esta topolog´ıa es T0. Demostraci´on. Para ver que la familia anterior forma una base minimal usaremos el Lema 3.2.2. Obviamente x∈↓x. M´as a´un, si z∈↓x, claramente tenemos ↓z⊆↓x. Esto prueba tanto la segunda condici´on del lema como que los conjuntos Ux=↓xforman una base minimal. Si adem´as (X, ≤) es un poset, entonces si x∈Uyey∈Uxtenemos que x≤yyy≤x. Por tanto x=y, es decir, la topolog´ıa as´ı construida es T0. Finalmente, si Aes un conjunto decreciente se prueba f´acilemente que A=∪a∈A↓a, esto es, Aes un abierto de esta topolog´ıa. Definici´on 4.2.2. A la topolog´ıa anterior la llamaremos topolog´ıa del preorden “≤” y la denotaremos por T≤. Nota 4.2.3. Tambi´en es base m´ınima para una topolog´ıa sobre Xla familia de filtros principales ↑x, que ser´ıa la topolog´ıa del preorden opuesto definido por x≤op ysi y≤x. De manera inversa tenemos el siguiente lema. Lema 4.2.4. En todo A-espacio (X, T) se puede definir un preorden ≤T(preorden de especializaci´on de T) estableciendo x≤Tysi se cunple una de las siguientes condiciones equivalentes: Ux⊆Uy⇔x∈Uy⇔y∈ {x} ⇔ {y} ⊆ {x} M´as a´un, si (X, T) es T0entonces el preorden ≤Tes de hecho un orden parcial. Demostraci´on. La propiedad reflexiva sigue de x∈Ux. Para ver la propiedad transitiva, supongamos x≤Tyey≤Tz. Entonces tenemos x∈Uyyy∈Uz, respectivamente. En particular, por ser Xun A-espacio, Uy⊆Uz. Por tanto tenemos x∈Uy⊆Uz, es decir, x≤Tz. Si adem´as (X, T) es T0, y tenemos x≤yey≤x, entonces x∈Uyey∈Uxy por ello Ux⊆UyyUy⊆Ux. As´ı que Ux=Uy, y por el Lema 4.1.3 tenemos x=y. 20 CAP´ ITULO 4. ESPACIOS DE ALEXANDROV, ´ ORDENES Y DIGRAFOS Proposici´on 4.2.5. Toda relaci´on de preorden “≤” sobre un conjunto Xcoincide con el preorden de especializaci´on de su topolog´ıa. M´as a´un, toda A-topolog´ıa Tsobre Xes la topololog´ıa de su preorden de especializaci´on. Adem´as, f: (X, ≤)−→ (Y, ) es ordenada si y solo si f: (X, T≤)−→ (Y, T) es continua. Si el espacio (X, T≤) es T0, entonces se corresponde con un poset. Demostraci´on. Denotemos por ”” el preorden de especializaci´on de T≤y supongamos que xy, esto es, x∈Uy. Como el abierto m´ınimo de yen T(≤) es el ideal principal de ycon respecto al preorden ”≤”, Uy=↓y, se sigue que x≤y. Si ahora Aes un abierto de la topolog´ıa del preorden de especializaci´on de Tpodemos ecribrir Acomo la uni´on A=∪a∈A↓adonde los ideales prinicpales est´an tomados respecto a ”≤T”. Pero, respecto a este orden, es inmediato probar que ↓a=Uaes el abierto m´ınimo de a en la A-topolog´ıa T, y as´ı Aes abierto de esta topolog´ıa. Ahora, si f: (X, T≤)−→ (Y, T≤) es continua, entonces, la continuidad y la definici´on de la topolog´ıa del preorden nos dan ↓x=Ux⊆f−1(Uf(x)) = f−1(↓f(x)). Luego si y≤x, entonces f(y)f(x). El rec´ıproco es an´alogo. Corolario 4.2.6. Los abiertos de un espacio finito (X, T) est´an en correspondencia biun´ıvoca con las anticadenas de su preorden asociado. M´as precisamente, la anticadena asociada a un abierto Ges el conjunto Max(G). Demostraci´on. Sea Ala familia de anticadenas de X(incluyendo la anticadena vac´ıa). Sea ψ:T → A la aplicaci´on que lleva Gen Max(G). Para ver que ψes sobreyectiva, dada una anticadena A∈ A consideramos el abiero G=∪x∈AUx. Por definici´on del preorden, tenemos que Max(G) = A. La inyectividad de ψsigue inmediatamente si comprobamos la igualdad G=∪x∈Max(G)Ux. Para ver esta igualdad, sea y∈G, y Cuna secuencia de longitud m´axima de elementos comparables en Gconteniendo a y. Entonces el elemento m´aximo de C, digamos m, es maximal en G, pues si no es as´ı existe x∈Gcon m≤xy la secuencia Cpuede ser alargada a˜nadiendo x. Entonces y∈Umy tenemos la inclusi´on G⊆ ∪x∈Max(G)Ux. La otra inclusi´on es obvia. Corolario 4.2.7. Un A-espacio Xes conexo (o, equivalentemente, conexo por caminos) si y solo si existe una secuencia de elementos comparables para el orden de especializaci´on entre dos puntos cualesquiera de X. 4.3. Ejemplos y tabla resumen Como vimos en el cap´ıtulo 2, todo conjunto preordenado (X, ≤) puede ser representado como un digrafo cuyos v´ertices son los elementos de Xy aparece una arista dirigida de aabsi a<b. Por tanto, a todo A-espacio (X, T) le corresponde el digrafo de su preorden de especializaci´on “≤T”. Por supuesto este digrafo permite visualizar la topolog´ıa original: un conjunto Ude v´ertices del digrafo es abierto si cada arista que tiene su punto final en un elemento de Utiene su punto inicial tambi´en en U. Ejemplo 4.3.1. Para la topolog´ıa T={{b},{a, b},{b, c, d}, X, ∅} sobre X={a, b, c, d}los abiertos m´ınimos son Ua={a, b},Ub={b},Uc=Ud={b, c, d}. Por tanto su preorden es b<a, b < c,b < d,c < d yd<cy su grafo dirigido asociado es: 4.3. EJEMPLOS Y TABLA RESUMEN 21 Figura 4.1. Con el fin de simplificar la estructura de los digrafos asociados a los posets se utilizan los llamados diagramas de Hasse. Definici´on 4.3.2. Dado un poset (X, ≤), se define su diagrama de Hasse,H(X), como el digrafo obtenido a partir del digrafo asociado G(X) una vez eliminadas aquellas aristas dirigidas que son redundantes por transitividad. De hecho esta es la manera habitual de proceder cuando se define un orden transitivo y ac´ıclico ya que se pueden obviar las relaciones generadas por transitividad. Ejemplo 4.3.3. Dado el poset (X, ≤) con las siguientes relaciones: d≤b, d ≤c, e ≤b, e ≤c, b ≤ ayc≤a. Por transitividad, se deben incluir adem´as las relaciones d≤aye≤a. El digrafo asociado G(X) es Figura 4.2. 28 CAP´ ITULO 5. LAPLACIANAS EN DIGRAFOS Y TOPOLOG´ IAS DE ALEXANDROV b) A(~ei−~ej) = ~ej−~ei. c) L+(~ei−~ej) = (gra+(vi) + 1)(~ei−~ej). d) L−(~ei−~ej) = (gra−(vi) + 1)(~ei−~ej). e) (L−)t(~ei−~ej)=(gra−(vi) + 1)(~ei−~ej). f) (L+)t(~ei−~ej)=(gra+(vi) + 1)(~ei−~ej). g) At(~ei−~ej) = ~ej−~ei. Demostraci´on. (a =⇒b). Sean viy (A(~ei−~ej))k=X l akl(δil −δjl) = aki −akj Si k6=i, j, entonces aki =akj debido a la transitividad. Si k=i, entonces aki = 0 yakj = 1. An´alogamente, si k=j, entonces aki = 1 y akj = 0. En todos los casos, (A(~ei−~ej))k= (~ej−~ei)k. (b =⇒c). Supongamos que A(~ei−~ej) = ~ej−~ei, entonces: A(~ei−~ej) = D+(~ei−~ej)−(gra+(vi) + 1)(~ei−~ej) o, lo que es lo mismo, (D+−A)(~ei−~ej)=(gra+(vi) + 1)(~ei−~ej) y, por definici´on, obtenemos que L+(~ei−~ej)=(D+−A)(~ei−~ej) = (gra+(vi) + 1)(~ei−~ej). (c =⇒d). Supongamos que L+(~ei−~ej) = (gra+(vi) + 1)(~ei−~ej). Por definici´on, tenemos: (D+−A)(~ei−~ej)=(gra+(vi) + 1)(~ei−~ej) =⇒ =⇒A(~ei−~ej) = D+(~ei−~ej)−(gra+(vi) + 1)(~ei−~ej) =⇒ =⇒A(~ei−~ej) = ~ej−~ei. Por tanto, A(~ei−~ej) = D−(~ei−~ej)−(gra−(vi) + 1)(~ei−~ej) o, lo que es lo mismo, 5.2. CONECTIVIDAD FUERTE EN DIGRAFOS TRANSITIVOS 29 (D−−A)(~ei−~ej)=(gra−(vi) + 1)(~ei−~ej). Y, por definici´on, nos queda que L−(~ei−~ej)=(gra−(vi) + 1)(~ei−~ej). (d =⇒e). Supongamos que L−(~ei−~ej) = (gra−(vi)+1)(~ei−~ej). Por definici´on, tenemos que: (D−−A)(~ei−~ej)=(gra−(vi) + 1)(~ei−~ej) =⇒ =⇒A(~ei−~ej) = D−(~ei−~ej)−(gra−(vi) + 1)(~ei−~ej) =⇒ =⇒A(~ei−~ej)=(~ej−~ei) =⇒ak,i −ak,j =δjk −δik. Si k=i, entonces aki −akj =−akj =−1, por tanto, (vi, vj)∈E. Si k=j, entonces aki −akj =aki = 1, por tanto, (vj, vi)∈E. Con lo que deducimos que viyvjest´an fuertemente conectados, por tanto, tambi´en est´an fuertemente conectados en el digrafo dual de G, con lo que tenemos que: At(~ei−~ej) = ~ej−~ei=⇒At(~ei−~ej) = D−(~ei−~ej)−(gra−(vi) + 1)(~ei−~ej) = = (D−)t(~ei−~ej)−(gra−(vi) + 1)(~ei−~ej) =⇒ =⇒(D−−A)t(~ei−~ej)=(gra−(vi) + 1)(~ei−~ej)=(L−)t(~ei−~ej). (e =⇒f). Supongamos que (L−)t(~ei−~ej)=(gra−(vi) + 1)(~ei−~ej). Tenemos, por definici´on, que: (D−−A)t(~ei−~ej)=(gra−(vi) + 1)(~ei−~ej) =⇒ =⇒At(~ei−~ej) = (D−)t(~ei−~ej)−(gra−(vi) + 1)(~ei−~ej) =⇒ =⇒At(~ei−~ej)=(~ej−~ei) = D+(~ei−~ej)−(gra+(vi) + 1)(~ei−~ej) = = (D+)t(~ei−~ej)−(gra+(vi) + 1)(~ei−~ej) =⇒ =⇒(D+−A)t(~ei−~ej)=(gra+(vi) + 1)(~ei−~ej) = (L+)t(~ei−~ej). 30 CAP´ ITULO 5. LAPLACIANAS EN DIGRAFOS Y TOPOLOG´ IAS DE ALEXANDROV (f =⇒g). Supongamos que (L+)t(~ei−~ej) = (gra+(vi) + 1)(~ei−~ej). Tenemos entonces, por definici´on: (D+−A)t(~ei−~ej)=(gra+(vi) + 1)(~ei−~ej) =⇒ =⇒At(~ei−~ej)=(D+)t(~ei−~ej)−(gra+(vi) + 1)(~ei−~ej) =⇒ =⇒At(~ei−~ej)=(~ej−~ei). (g =⇒a). Supongamos que At(~ei−~ej) = ~ej−~ei. Entonces, tenemos que at ki −at kj =δjk −δik. Si k=i, entonces at ki −at kj =−at kj =−1, por tanto, (vj, vi)∈E. Si k=j, entonces at ki −at kj =at ki = 1, por tanto, (vi, vj)∈E. Queda probado que viyvjest´an fuertemente conectados. 5.3. Estructura de bloques de laplacianas En esta secci´on nos centraremos en estudiar la estructura de laplacianas de digrafos transitivos no necesariamente ac´ıclicos. Recordemos que ya vimos al final del Cap´ıtulo 4 que todo digrafo transitivo Gda lugar a un digrafo transitivo y ac´ıclico G0obtenido al tomar cada componente fuertemente conexa Cde G(trivial o no) como un v´ertice vCde G0y una arista dirigida en G0entre vCyvC0es justamente una arista dirigida en Gentre un v´ertice de Cy otro de C0. Si X(G) es el A-espacio asociado a Gentonces X(G0) es justamente el A0-espacio X(G)0 definido en la Proposici´on 4.1.10. Si cambiamos el lenguaje a espacios ordenados, G0corresponde al poset formado por las componentes fuertemente conexas de Gy el orden C≤C0⇔vC≤vC0en el poset asociado a G0. A partir del orden anterior sobre las componentes fuertemente conexas de Gindexamos las componentes fuertemente conexas de Gde manera coherente con ese orden C1, C2, . . . , Cs. Dentro de cada componente Cjindexamos sus v´ertices de la forma {vj 1, . . . , vj i}i∈Ij, donde Ij es un subconjunto finito de N. De esta manera los v´ertices de Gquedan indexados de manera consistente con el preorden, es decir, el ´ındice del v´ertice ves menor el ´ındice del vector v0 si v≤v0, quedando adem´as los v´ertices pertenecientes a la misma componente Ccon ´ındices consecutivos. Usaremos este procedimiento de indexaci´on para describir las laplacianas de digrafos transitivos por medio de matrices por bloques con ceros por debajo de esos bloques. Los bloques corresponden a las componentes fuertemente conexas, y en el caso de que estas componentes se reduzcan a un punto, es decir, tengamos un grafo transitivo y ac´ıclico, tendremos matrices triangulares superiores. Empezaremos por el caso particular de los digrafos transitivos fuertemente conexos. Recordemos que dos digrafos fuertemente conexos con el mismo conjunto de v´ertices tienen la misma topolog´ıa de Alexandrov, exactamente la indiscreta {∅, V }(ver Nota 4.3.10). Notaci´on 5.3.1. Diremos que un vector es no negativo si ninguna de sus componentes es negativa. 5.3. ESTRUCTURA DE BLOQUES DE LAPLACIANAS 31 Lema 5.3.2. Si Kndenota al digrafo completo de n v´ertices, entonces L+(Kn) = L−(Kn) tiene la siguiente forma:       n−1−1−1... −1 −1n−1−1... −1 −1−1n−1... −1 ... ... ... ... −1 −1−1−1... n −1       A partir de esta expresi´on expl´ıcita se tiene el siguiente resultado. Proposici´on 5.3.3. Las matrices L−(G) y L+(G) de un digrafo transitivo G fuertemente conexo tienen autovalores λn= 0, con autovector ~vn= (1, ..., 1), y λi=ncon 1 ≤i≤n−1 con autovectores {~vi}que tiene componentes (~vi)j=δij −δij−1, es decir, ~vi= (0, ..., 0,1 |{z} i ,−1 |{z} i+1 ,0, ..., 0). Nota 5.3.4. Recu´erdese que la topolog´ıa asociada a un digrafo a un digrafo completo Knes la indiscreta, con el ´unico abierto no vac´ıo V(Kn), mientras que el ´unico autovector no negativo de sus laplacianas L+yL−es ~ b(V(Kn)) = (1, ..., 1). Vayamos ahora al caso general de digrafos transitivos. N´otese que una componente fuertemente conexa de un digrafo se corresponde con un Kndirigido (v´eanse las Definiciones 1.2.8 y 1.2.9), ya que en una componente fuertemente conexa de un digrafo, todo par de v´ertices est´a fuertemente conectado. Adem´as, por el Lema 5.1.8 podemos considerar la matrices laplacianas L−=L−(G) y L+=L+(G) de un digrafo transitivo Gconstruidas a partir de la indexaci´on de los v´ertices vista en la introducci´on de este cap´ıtulo. De esta manera L−yL+aparecen como matrices por bloques (cuadrados) triangulares superiores. M´as a´un, se tiene como consecuencia del Lema 5.1.9 la siguiente descripci´on de L+-espectro y L−-espectro de G. Proposici´on 5.3.5. Dado un digrafo transitivo Glos autovalores de las laplacianas L−=L−(G) yL+=L+(G) son enteros no negativos. M´as a´un, si si C1,...Cmson las componentes conexas fuertes y σjes el grado de salida total de los v´ertices de Cjy #Cjes su cardinal, tenemos que el espectro de L+est´a formado por σj+ 1 con multiplicidad #Cj−1 y σj−#Cj+ 1 con multiplicidad 1 para 1 ≤j≤n. An´alogamente para la laplaciana L−y los grados de entrada. Demostraci´on. Como hemos indicado, usando la indexaci´on dada al principio de esta secci´on, tenemos que L−yL+son matrices por bloques triangulares superiores las matrices. Adem´as los bloques diagonales vienen dados por las componentes fuertes (posiblemente triviales) que son digrafos completos. Ahora bien, si Ces una componente fuerte con nv´ertices, el bloque BC determinado por Cno es exactamente el de Knya que el grado de salida en los v´ertices de Ces el grado total de salida de los v´ertices de Cen G, que es el mismo en todos los v´ertices de C, digamos k≥n−1. As´ı pues el bloque BCes la matriz       k−1−1... −1 −1k−1... −1 −1−1k ... −1 ... ... ... ... −1 −1−1−1... k       que tiene por autovalores k−n+ 1 y k+ 1. Adem´as el primero tiene multiplicidad 1 (correspondiente al vector de coordenadas todas 1) y el segundo tiene multiplicidad n−1 (correspondiente 32 CAP´ ITULO 5. LAPLACIANAS EN DIGRAFOS Y TOPOLOG´ IAS DE ALEXANDROV a los vectores ~vi= (0, ..., 0,1 |{z} i ,−1 |{z} i+1 ,0, ..., 0) con 1 ≤1≤n−1); comp´arese con la Proposici´on 5.3.3. Ahora, aplicamos el Lema 5.1.9 y tenemos que los autovalores de la laplaciana L+son los autovalores de los bloques diagonales, que son todos enteros no negativos. Expl´ıcitamente, los bloques est´an determinados por las componentes C1,...Cmy tenemos que los autovalores de L+son σj+ 1 con multiplicidad #Cj−1 y σj−#Cj+ 1 con multiplicidad 1 para 1 ≤j≤n. An´alogamente para la laplaciana L−. Proposici´on 5.3.6. Dado un digrafo transitivo G= (V, E), los autovalores de L−=L+(G) son menores o iguales a 1 + max{gra+(v)|v∈V}. Demostraci´on. De acuerdo con la proposici´on anterior Cada componente fuertemente conexa de mv´ertices con grado de salida total en G k ≥maporta autovalores k−m+ 1 y k+ 1 con multiplicidades 1 y m−1, respectivamente. Por tanto el mayor autovalor de L+es el m´aximo grado de salida, por lo que λ≤1 + max{gra+(v)|v∈V}para todo autovalor λ. La siguiente proposici´on tiene una prueba similar. Proposici´on 5.3.7. Dado un digrafo transitivo G= (V, E), los autovalores de L−(G) son menores o iguales a 1 + max{gra−(v)|v∈V}. 5.4. A-topolog´ıas y laplacianas en digrafos Considerando el producto de matrices laplacianas con vectores caracter´ısticos, tenemos las siguientes proposiciones. Proposici´on 5.4.1. Si G= (V, E) es un grafo dirigido transitivo y Tsu A-topolog´ıa, entonces S∈ T ⇔ L+~ b(S)≥0, para la laplaciana L+=L+(G). Demostraci´on. [ =⇒] Sea S∈ T, entonces (L+~ b(S))i=X {j|vj∈S} (D+)ij −aij =X {j|vj∈S} δijgra+(vi)−X {j|vj∈S} aij (5.1) Si vi∈Sentonces (L+~ b(S))i=gra+(vi)−X {j|vj∈S} aij ≥0 por la definicion de grado de salida. Si vi/∈Sy (vi, vj)∈Eentonces vj/∈S, por tanto X {j|vj∈S} aij = 0. [⇐= ] Sea L+~ b(S)≥0, entonces para todo vi X {j|vj∈S} aij ≤X {j|vj∈S} δijgra+(vi) (5.2) Por tanto, si vj0∈Sy (vi, vj0)∈Eentonces aij06= 0, con lo cual X {j|vj∈S} aij >0 y X {j|vj∈S} δijgra+(vi)>0. Por tanto, existe un vj1∈Scon δij1= 1, y entonces vi=vj1∈S. Por transitividad, si vj∈Syvh≤vjentonces vh∈S, por lo tanto Ses abierto. 5.5. ALGUNOS EJEMPLOS 33 La siguiente proposici´on se prueba de forma an´aloga (ver Proposici´on 5.1.3). Proposici´on 5.4.2. Sea G= (V, E) es un digrafo transitivo con A-topolog´ıa T. Entonces S∈ T ⇔ (L−)t~ b(S)≤0⇔L+~ b(S)≤0, para la laplacianas L−=L−(G) y L+=L+(G), siendo Gel digrafo dual de G. Combinando 5.4.1 y 5.4.2 con los resultados obtenidos en la secci´on anterior obtenemos los siguientes resultados relacionando los autovectores de las laplacianas L−=L−(G) y L+=L+(G) de un digrafo transitivo Gy la A-topolog´ıa de este T. Proposici´on 5.4.3. Dado un digrafo transitivo G= (V, E). Para un conjunto S⊆V, si ~ b(S) puede ser expresado como una suma de autovectores no negativos de L+(G), entonces S∈ T . Demostraci´on. Sea ~ b(S) = P~vidonde ~vison autovectores no negativos. Entonces L+~ b(S) = L+P~vi=Pλi~vi≥0 (para L+=L+(G)), que implica que S∈ T. Proposici´on 5.4.4. Dado un digrafo transitivo G= (V, E). Para un conjunto S⊆Vcon complementario C(S), si ~ b(C(S)) puede ser expresado como suma de autovectores no negativos de (L−(G))t, entonces S∈ T . Demostraci´on. Sea ~ b(C(S)) = P~vidonde ~vison autovectores no negativos. Entonces como ~ b(S)=1−~ b(C(S)), tenemos que ~ b(S) = ~ 1−P~vi. Como (L−)T~ 1 = ~ 0 entonces (L−)T~ b(S) = −(L−)TP~vi=−Pλi~vi≤0 (para L−=L−(G)), lo que implica que S∈ T. 5.5. Algunos ejemplos Con los siguientes ejemplos se quiere ilustrar los resultados de las dos secciones anteriores. Figura 5.1. Ejemplo 5.5.1. Denotaremos al digrafo de la figura anterior como G= (V, E), donde V= {1,2,3,4}es el conjunto de los v´ertices y E={(1,2),(1,3),(1,4),(2,3),(3,2)}es el conjunto de las aristas. Elegimos este ejemplo porque los autovectores de L+(G) y L−(G) (a) ayudan a demostrar la importancia de las condiciones de la Proposici´on 5.4.3 y (b) tienen propiedades que han sido observadas pero no ha sido demostrado que sean v´alidas en casos m´as complicados. L+(G) y L−(G), en este caso, vienen dadas por las siguientes matrices: 34 CAP´ ITULO 5. LAPLACIANAS EN DIGRAFOS Y TOPOLOG´ IAS DE ALEXANDROV L+(G) =     3−1−1−1 0 1 −1 0 0−1 1 0 0 0 0 0     L−(G) =     0−1−1−1 0 2 −1 0 0−1 2 0 0 0 0 1     Los autovalores de L+(G) son λ1= 3 para ~v1= (1,0,0,0)t,λ2= 2 para ~v2= (0,1,−1,0)t yλ3=λ4= 0 para ~v4= (1,1,1,1)ty~v3= (1,3/2,3/2,0)t. Notar que (~v3+ (3/2)~v2+ 2~v1)/3 = (1,1,0,0) = ~ b(S) para S={1,2}que no es abierto; esta suma de autovectores produce un vector can´onico, pero los autovectores no son todos no negativos. Esto muestra la importancia de la especificaci´on en la Proposici´on 5.4.3 de que los autovectores de la suma son no negativos. Los autovalores de L−(G) son λ1= 3 para ~v1= (0,1,−1,0)t,λ2=λ3= 1 para ~v2= (−2,1,1,0)ty~v3= (−1,0,0,1)t, y λ4= 0 para ~v4= (1,0,0,0)t. Notar que (−1/2)~v1+(1/2)~v2+ ~v3+ 2~v4= (0,0,1,1)t=~ b(C(S)) para S={1,2}que no es abierto; esta suma de autovectores produce un vector can´onico, pero los autovectores no son todos negativos. Esto muestra la importancia de la especificaci´on en la Proposici´on 5.4.4 de que los autovectores de la suma son no negativos. A continuaci´on transformaremos el digrafo Gpara hallar L+(G0) y L−(G0), ya que Ges un digrafo transitivo y contiene un K2. Convirtiendo dicho K2(que se encuentra en los v´ertices 2 y 3) en un ´unico v´ertice (2), nos queda el siguiente digrafo G0: Figura 5.2. cuyas matrices L+(G0) y L−(G0) vienen dadas por: L+(G0) =   2−1−1 0 0 0 0 0 0   5.5. ALGUNOS EJEMPLOS 35 L−(G0) =   0−1−1 0 1 0 0 0 1   que, como podemos observar, son triangulares superiores. Ahora podemos ver reflejado en el ejemplo lo que se expuso al comienzo de la secci´on. Efectivamente los v´ertices que formaban el K2pertenecen al conjunto {m+ 1, m + 2}, con m= 1. Ahora obtenemos que los autovalores de L+(G0) son λ2=λ3= 0 con autovectores ~v3= (1,1,1)ty~v2= (0,1,−1)t, y λ1= 2 con autovector ~v1= (1,0,0)t. Por tanto, por el autovector ~v1vemos que los digrafos transitivos que no son fuertemente conexos, no cumplen la ´ultima propiedad de la Proposici´on 5.3.3. Los autovalores de L−(G0) son λ3= 0 para ~v3= (1,0,0)tyλ1=λ2= 1 para ~v2= (−1,0,1)t y~v1= (−1,1,0)t. Ejemplo 5.5.2. Adem´as de los Kndirigidos, un tipo de digrafo digno de considerar es el digrafo transitivo cuyo preorden es un orden total de sus v´ertices, de acuerdo a la direcci´on de las aristas. Un orden total es un orden parcial que cumple la comparabilidad, es decir, cada par de v´ertices est´a relacionado. Dado un digrafo transitivo Gcon orden total de sus v´ertices, entonces las matrices L−(G) y L+(G) son de la siguiente forma: L+(G) =       n−1−1... −1−1 0n−2... −1−1 ... ... ... ... ... 0 0 ... 1−1 0 0 ... 0 0       L−(G) =       0−1... −1−1 0 1 ... −1−1 ... ... ... ... ... 0 0 ... n −2−1 0 0 ... 0n−1       Los autovectores y los autovalores de las matrices anteriores son, para 1 ≤i≤n,λi=n−i para autovectores con componentes (~vi)j= Θj,i, para L+(G), y λi=n−ipara autovectores con componentes (~vi)j= Θji, para (L−)T, donde Θji =1 si j≤i 0 si j > i Θji =1 si j≥n−i+ 1 0 si j < n −i+ 1 Es f´acil ver que estos autovectores son de la forma ~ b(S), para L+(G), y 1−~ b(S), para L−(G), donde S∈ T. En este caso cada uno de los autovectores corresponde exactamente a un conjunto abierto; como son no negativos, es trivial confirmar las Proposiciones 5.4.3 y 5.4.4. Ejemplo 5.5.3. A continuaci´on mostraremos un ejemplo de un digrafo transitivo G= (V, E) con orden total, donde V={1,2,3,4}yE={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}: 36 CAP´ ITULO 5. LAPLACIANAS EN DIGRAFOS Y TOPOLOG´ IAS DE ALEXANDROV Figura 5.3. Tenemos que sus laplacianas vienen dadas por L+(G) =     3−1−1−1 0 2 −1−1 0 0 1 −1 0 0 0 0     L−(G) =     0−1−1−1 0 1 −1−1 0 0 2 −1 0 0 0 3     cuyos autovalores son λ1= 3, λ2= 2, λ3= 1 y λ4= 0, con autovectores ~v1= (1,0,0,0), ~v2= (1,1,0,0), ~v3= (1,1,1,0) y ~v4= (1,1,1,1), para L+(G), y λ1= 3, λ2= 2, λ3= 1 y λ4= 0, con autovectores ~v1= (0,0,0,1), ~v2= (0,0,1,1), ~v3= (0,1,1,1) y ~v4= (1,1,1,1), para (L−(G))t. Podemos observar que los autovectores hallados nos dan los conjuntos abiertos que son {1},{1,2},{1,2,3},V(este solo lo obtenemos de L+(G)) y ∅(este solo lo obtenemos de (L−(G))t), y as´ı vemos que se cumple la nota final en el Ejemplo 5.5.2. 5.6. N´ucleos de laplacianas de digrafos transitivos Sea Gun grafo transitivo con componentes conexas fuertes C1, . . . , Cmya ordenadas como se hizo en la Secci´on 5.3. 5.6. N ´ UCLEOS DE LAPLACIANAS DE DIGRAFOS TRANSITIVOS 37 Definici´on 5.6.1. Una componente sumidero Ces una componente fuertemente conexa para la que no existe una componente fuertemente conexa C0con C≤C0. Una componente fuente Ces una componente fuertemente conexa para la que no existe una componente fuertemente conexa C0con C0≤C. Debe observarse que las componentes sumidero son las que aparecen en los ´ultimos lugares para el orden anterior. Ahora estamos en condiciones de demostrar el siguiente resultado sobre la dimens´on del n´ucleo de la laplaciana L+=L+(G) de un digrafo transitivo G. Proposici´on 5.6.2. La dimensi´on del n´ucleo de L+es menor o igual al cardinal del conjunto de componentes sumidero de G. Demostraci´on. De acuerdo con la Proposici´on 5.3.5, si C1,...Cmson las componentes conexas fuertes y σjes el grado de salida total de los v´ertices de Cjy #Cjes su cardinal, tenemos que los autovalores de L+son σj+1 con multiplicidad #Cj−1 y αj=σj−#Cj+1 con multiplicidad 1 para 1 ≤j≤n. EL n´ucleo de L+se obtiene para el autovalor 0. Como σj≥1, la ´unica opci´on es αj= 0. Esto ocurre si y solo si σj= #Cj−1; esto es, no hay aristas de salida desde los v´ertices de Cjy por tanto es una componente sumidero. Cada japortar´a un autovector al n´ucleo y tenemos as´ı el resultado (en principio dos componentes podr´ıan aportar el mismo autovector). A continuaci´on se probar´a que de hecho se tiene la igualdad, dando un m´etodo para obtener una base del n´ucleo de L+. Para ello se dan la siguiente definici´on. Definici´on 5.6.3. Si Ces una componente fuertemente conexa de G, su dominio de influencia bajo Cson los v´ertices que aparecen en todas las componentes C0≤C. An´alogamente se define el dominio de influencia sobre una componente fuertemente conexa. Obs´ervese que el dominio de influencia bajo Ccoincide con el abierto m´ınimo de cualquier x∈C(todos son iguales). An´alogamente, el dominio de influencia sobre Ces la clausura {x} para cualquier x∈C. Proposici´on 5.6.4. Sea S=SCel dominio de influencia bajo una componente sumidero C del digrafo transitivo G= (V, E). Entonces existe un vector ~wS∈[0,1]Vtal que d~wSe=~ b(S) y L+~wS=~ 0. M´as a´un, si Σ denota la familia de componentes sumidero de GyS={SC|C∈Σ}es la familia de los correspondientes dominios de influencia, entonces {~wS}S∈S es una base del n´ucleo de L+. Demostraci´on. Si C1, . . . , Cmson las componetes de Gordenadas como m´as arriba, dentro de cada componente Cjindexamos sus v´ertices de la forma {vj 1, . . . , vj i}i∈Ij, donde Ijes un subconjunto finito de N. Indexamos los v´ertices de Gde acuerdo con este criterio, es decir, primero se indexan las componentes fuertemente conexas C1, . . . , Cmy despu´es dentro de Cjpor medio de un doble ´ındice vj icon i∈Ij⊆N. Tenemos as´ı el orden lexicogr´afico respecto a los ´ındices de los v´ertices de G; esto es, vj i≤vj0 i0 si j≤j0oj=j0ei≤i0. Por tanto las entradas de la laplaciana L+vienen dadas por cuatro ´ındices (j, i),(j0, i0). Supongamos que las componentes sumidero las ´ultimas k, esto es, Cm−k+1, . . . , Cm. Denotemos por Sm−k+jal dominio de influencia de Cm−k+jpara j≤k. Contruiremos los vectores ~wj=~wCm−j+1 (1 ≤j≤k) como sigue. Escribimos S=SCmy observamos: 44 CAP´ ITULO 6. LAPLACIANAS DE DIGRAFOS (CASO INFINITO) Habitualmente se considera el espacio de Hilbert `2(V); esto es, las sucesiones de n´umeros complejos (xv)v∈V(xv∈C) de cuadrado numerable; es decir, P|xv|2<∞, y norma k(xv)kv∈V= X v∈V|xv|2!1 2 . Se puede usar tambi´en el espacio de Hilbert `p(V) con 1 ≤p≤ ∞, con P|xv|p<∞ y norma k(xv)v∈Vk= X v∈v|xv|p!1 p , donde para p=∞,`∞(V) corresponde a las sucesiones (xv)v∈Vacotadas con la norma del m´aximo k(xv)v∈Vk∞= max{|xv|;v∈V}. A partir de la matriz de adyacencia A(G) se construye en [9] un operador lineal A(G) de `2(V) en s´ı mismo. Para empezar, el grafo Gdebe ser localmente finito, (cada v´ertice solo tiene un n´umero finito de aristas incidentes en ´el). De esta forma las matrices A=A(G) son localmente finitas, esto es, solo tienen un n´umero finito de entradas no nulas en cada fila y columna. Adem´as para la base ortonormal de `2(V), {ei}i∈N,ei= (0,...,0,1 |{z} i ,0,...,0), tenemos que Aeies la i-´esima columna de Ay por tanto un elemento de `2(V). As´ı pues si H0es el subespacio de `2(V) generado por las combinaciones lineales finitas de la base {ei}i∈N, es bien conocido (y f´acil de probar) que H0es denso en `2(V) y obviamente A:H0−→ H0es un endomorfismo de espacios vectoriales. El punto crucial del desarrollo de la teor´ıa espectral de grafos localmente finitos en [9] es la posibilidad de extender Aa un operador cerrado Ade `2(V) en s´ı mismo. En [9] ello es consecuencia del hecho de que la matriz de adyacencia de un grafo es sim´etrica. A diferencia de los grafos, la matriz de adyacencia Ade un digrafo no es sim´etrica (si aij = 1, entonces aji = 0). Sin embargo podemos probar que Atambi´en puede ser extendido a un operador cerrado, esto es Aes un operador clausurable. En detalle, sea Hel espacio de Hilbert de las sucesiones complejas de cuadrado sumable con norma k(zi)k= ∞ X i=1|zi|2}. Sea Auna matriz localmente finita cuyas entradas no nulas son 1 y sea Vel espacio vectorial complejo de base ei= (0,...,0,1 |{z} i ,0,...,0). Entonces Ves denso en Hy tenemos el operador lineal A:V→ H. Lema 6.2.1. Aes clausurable. Demostraci´on. Hay que demostrar que para cualquier sucesi´on {sn}n≥1⊆Vcon sn→0 y Asn→lse tiene que l= 0. Sean sn= (zn i)∞ i=1, l = (li)∞ i=1. Adem´as, si Asn= (an i)∞ i=1, tenemos que an i=X j∈Ji zn jcon #Ji=ri<∞finito (ries el n´umero de entradas no nulas en la i-´esima fila de A). Supongamos por reducci´on al absurdo que lt6= 0 para alg´un t. Sea λ=|lt|y sea ε=λ2 4. Por hip´otesis existe n0tal que ∞ X i=1|zn i|2<ε r2 t 6.2. UNA PROPUESTA PARA EXTENDER LA TEOR´ IA ESPECTRAL DE GRAFOS INFINITOS A DIGRAFOS45 y∞ X i=1|an i−li|2< ε para todo n≥n0. En particular para el ´ındice t, X j∈Jt|zn j|2<ε r2 t y |an t−lt|2≤ ∞ X i=1|an i−li|< ε. As´ı que para todo j∈Jt,|zn j|2<ε r2 t y por tanto |an t|=|X j∈Jt zn j| ≤ X j∈Jt|zn j|< rt √ε rt =√ε. Ahora, |lt|≤|an t−lt|+|an t|<√ε+√ε= 2√ε= 2λ 2=λ, lo que es una contradicci´on. Volvamos a la matriz de adyacencia del digrafo localmente finito G,A(G). Una vez demostrado que A(G) es un operador clausurable, se puede iniciar la teor´ıa espectral de los digrafos localmente finitos extendiendo el m´etodo introducido por Mohar para grafos localmente finitos en [9], que pasamos a describir. Consideramos la clausura del operador A(G), A(G), que llamaremos el operador de adyacencia de G, entonces el espectro de G,σ(G), ser´a el espectro de su operador de adyacencia. Como hemos visto en el Ap´endice, este conjunto queda dividido en tres partes: el espectro puntual σp(G), el espectro residual σr(G) y el espectro continuo σc(G). Adem´as σ(G) es un conjunto cerrado de Cpor ser A(G) un operador cerrado. En particular los elementos de σp(G) se llamar´an autovalores de G. Debemos observar que en [9] se elige como definici´on de σc(G), σc(G) = σ(G)−(σp(G)Sσr(G)); ver Nota 6.2.13. Al igual que para grafos, el espectro del digrafo Gno depende de la numeraci´on de los v´ertices ya que una permutaci´on de los mismos induce una transformaci´on unitaria, es decir un isomorfismo lineal cuyo inverso es su adjunto, y es sabido que los espectros son invariantes por estas transformaciones (ver [9]). Por tanto el espectro es un invariante del digrafo G. A partir de ahora se pueden plantear para el operador de adyacencia de un digrafo localmente finito Glas mismas cuestiones que para el caso de grafos. En particular es de gran importancia saber si el operador de adyacencia del digrafo Ges acotado y/o autoadjunto debido a las propiedades de esta clase de operadores. Es sabido que para grafos localmente finitos la acotaci´on de las valencias de todos los v´ertices por un n´umero kes equivalente a la acotaci´on del operador de adyacencia y en tal caso ser´an autoadjuntos (ver [9], Teorema 3.2). Dejamos para aquellos interesados el establecer resultados precisos en esta l´ınea de investigaci´on, que podr´ıa ser extendida a las matrices laplacianas de entrada y salida. 46 CAP´ ITULO 6. LAPLACIANAS DE DIGRAFOS (CASO INFINITO) 6.2.1. Ap´endice: Operadores en espacios de Hilbert En este ap´endice se recogen varias nociones y resultados de la teor´ıa de operadores en espacios de Hilbert ( [10]) para la construcci´on de un operador adecuado a partir de la matriz de adyacencia de un digrafo, extendiendo el m´etodo usado en [9]. Definici´on 6.2.2. Unoperador lineal de un espacio de Hilbert H1en un espacio de Hilbert H2es una aplicaci´on lineal Tde un subespacio vectorial de H1, denominado dominio de Ty denotado por D(T), en H2. Se denotar´an por R(T) y N(T) la imagen y el n´ucleo de T. Sean TySdos operadores lineales de H1en H2. Se dir´a que Tes una extensi´on de Sy se escribir´a S⊆Tcuando D(S)⊆ D(T) y S(x) = T(x) para todo x∈ D(S). Definici´on 6.2.3. Un operador Tde H1en H2se denomina cerrado si para toda sucesi´on de vectores xn∈ D(T) con l´ım n→∞ xn=xen H1y l´ım n→∞(xn) = yen H2se tiene x∈ D(T) y Tx =y. Esta propiedad es equivalente a pedir que el grafo de Tsea cerrado en la suma directa H1⊕H2 con la norma h(x, y)i=hxi1+hyi2. Siendo tambi´en equivalente a decir que D(T) con la norma hxiThxi1+hT(x)i2sea completo y as´ı un espacio de Hilbert para esa norma. Definici´on 6.2.4. Sea Hun espacio de Hilbert y sea T:D(T)−→ H un operador lineal con dominio D(T)⊆ H. Entonces Tse dice clausurable si para toda sucesi´on {xn}n≥1⊆ D(T) convergiendo a 0 tal que Txn−→ y, entonces y= 0. Definici´on 6.2.5. Sea T:H1→ H2un operador clausurable. Sea el conjunto D(T) formado por los vectores x∈ H1para los que existe una sucesi´on (xn)n∈≥1en D(T) tal que x= l´ım xnen H1y (T(xn))n∈Nconverge en H2. Para dicha sucesi´on (xn), se denomina clausura del operador Tal operador Tde dominio D(T) dado por T(x) := l´ım n→∞ T(xn) para todo x∈ D(T). Nota 6.2.6. Las nociones anteriores est´an claramete relacionadas con la continuidad de los operadores. Recordemos que un operador lineal Tes continuo (es decir, si l´ımn→∞ xn=x, entonces l´ımn→∞ T(xn)) si y s´olo si es acotado (esto es, existe una constante c > 0 tal que hT(x)i2≤chxi1para todo x∈ D(T)). No es dif´ıcil probar que todo operador continuo es clausurable. As´ı pues la propiedad de ser clausurable es una versi´on d´ebil de la continuidad ya que s´olo se pide que cuando l´ımn→∞ xn= 0 en caso de converger la sucesi´on T(xn) lo haga al l´ımite esperado, esto es, 0. Por otro lado, si el operador Test´a acotado, entonces la norma h·iT sobre D(T) es equivalente a h·i1. Por tanto un operador acotado (o, equivalentemente, continuo) es cerrado si y s´olo si su dominio D(T) es cerrado en H1. Rec´ıprocamente, si Tes un operador lineal con dominio cerrado, entonces el teorema del grafo cerrado implica que Test´a acotado. En particular, un operador lineal cerrado que no sea acotado no puede estar definido en todo el espacio de Hilbert H1. Todo operador densamente definido Tentre los espacios de Hilbert (H1,h·,·i1)y(H2,h·,·i2) tiene asociado un operador T∗entre H2yH1llamado adjunto de Tcuyo dominio de definici´on es el conjunto D(T∗) cuya construcci´on es como sigue: Sean (H1,h·,·i1) y (H2,h·,·i2) espacios de Hilbert. Sea Tun operador lineal de H1en H2tal que el dominio D(T) es denso en H1. Se establece D(T∗) = {y∈ H2:∃u∈ H1/hTx, yi2=hx, ui1, x ∈ D(T)}. Por el teorema de Riesz, un vector y∈ H2pertenece a D(T∗) si y solo si hay una constante cy>0 tal que |hTx, yi2| ≤ cykxk1para todo x∈ D(T). Dar una descripci´on expl´ıcita del conjunto D(T∗) es en general complicado. 6.2. UNA PROPUESTA PARA EXTENDER LA TEOR´ IA ESPECTRAL DE GRAFOS INFINITOS A DIGRAFOS47 Como D(T) es denso en H1, el vector u∈ H1que cumple hTx, yi2=hx, yi1para todo x∈ D(T) est´a determinado ´unicamente por y. Por tanto, estableciendo T∗y=u, se obtiene un operador bien definido T∗de H2aH1. Es f´acil ver que T∗es lineal. Definici´on 6.2.7. Sea Tun operador lineal densamente definido en H. El operador lineal T∗ se denomina operador adjunto de T. El operador Tse denomina autoadjunto si T=T∗. Por la definici´on anterior se tiene hTx, yi2=hx, T∗yi1,∀x∈ D(T), y ∈ D(T∗). Un n´umero de propiedades importantes y ´utiles de operadores clausurables y adjuntos est´an recogidas en el siguiente teorema. Teorema 6.2.8. Sea Tun operador lineal densamente definido de H1aH2. (i)Tes clausurable si y solo si D(T∗) es denso en H2. (ii) Si Tes clausurable, entonces (T)∗=T∗, y definiendo T∗∗ := (T∗)∗, se tiene T=T∗∗. (iii)Tes cerrado si y solo si T=T∗∗. (iv) Supongamos que N(T) = {0}yR(T) es denso en H2. Entonces T∗es invertible y (T∗)−1= (T−1)∗. Terminamos este ap´endice con la definici´on de espectro de un operador cerrado Tde un espacio de Hilbert Hen s´ı mismo. Definici´on 6.2.9. Se llama conjunto resolvente del operador Tal conjunto de n´umeros complejos λtales que el operador T−λI tiene inversa acotada definida en todo H. Esta inversa se denomina resolvente de Ten λy se denota por Rλ(T). El conjunto σ(T) := C\ρ(T) es denominado espectro del operador T. Es sabido que el espectro de un operador cerrado es un conjunto cerrado. Cuando Hes cerrado entonces el requisito de que la inversa de T−λI es acotada es redundante. Los puntos del espectro de un operador se clasifican en tres tipos de acuerdo a las siguientes definiciones. Definici´on 6.2.10. Se llama espectro puntual del operador Tal conjunto σ(T) := {λ∈C: N(T−λI)6={0}}. Cada λ∈σp(T) se llama un autovalor de T, la dimensi´on de N(T−λI) su multiplicidad, y cualquier elemento no nulo de N(T−λI) un autovector de Ten λ. Se dir´a que un operador cerrado Ttiene un espectro puramente discreto si σ(T) consiste solamente de autovalores de multiplicidades finitas que no tienen punto de acumulaci´on finito. Si λes un punto del espectro σ(T), entonces o bien T−λI no es inyectivo o no es sobreyectivo. Entonces, el espectro puntual de Tes precisamente el conjunto de todos los λ∈σ(T) para los cuales T−λI no es inyectivo. Miremos ahora los n´umeros donde la sobreyectividad del operador T−λI falla. Definici´on 6.2.11. Se denomina espectro residual del operador Tal conjunto de todos los λ∈C para los cuales T−λI tiene una inversa acotada que no est´a definida en todo H. Se denota por σr(T). Es sabido que σr(T) es un conjunto abierto y que para operadores autoadjuntos es siempre vac´ıo. 48 CAP´ ITULO 6. LAPLACIANAS DE DIGRAFOS (CASO INFINITO) Definici´on 6.2.12. El conjunto de los λ∈Cpara los cuales el rango de T−λI no es cerrado, esto es, R(T−λI)6=R(T−λI), se denomina espectro continuo de Ty se denota σc(T). Entonces σ(T) = σp(T)Sσr(T)Sσc(T), pero los conjuntos σc(T) y σp(T) son en general no disjuntos. Nota 6.2.13. Algunos autores definen σc(T) como el complementario de σp(T)Sσr(T) en σ(T); entonces σ(T) se convierte en la uni´on disjunta de las tres partes. Bibliograf´ıa [1] J.R. Munkres. Topolog´ıa. Pearson Educaci´on, 2001. [2] R. Engelking. General Topology. Heldermann, 1989. [3] G.N. Rubiano. Sobre el n´umero de topolog´ıas en un conjunto finito. Bolet´ın de Matem´aticas, 13(2006), 136-158. [4] P.S. Alexandroff. Diskrete Raume. Math. Sbornik, 2(1937), 501-519. [5] Garc´ıa Merayo, F., Matem´atica discreta, Paraninfo, 2015. [6] Aaron Ostrander, Laplacian matrices and Alexandrov topologies of digraphs, Linear Algebra Appl. 481 (2015) 174-185. [7] D. M. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs. Theory and Applications. Academic Press, 1979. [8] J. P. May, Finite Spaces and larger contexts. Preliminary draft submitted to the AMS, 2014. http://math.uchicago.edu/ may/FINITE/FINITEBOOK/FiniteAugBOOK.pdf. [9] Bojan Mohar, The Spectrum of an Infinite Graph. Linear Algebra and its Applications, 1982. [10] Konrad Schm¨udgen, Unbounded Self-adjoint Operators on Hilbert Space. Spinger Science+Business Media Dordrecht 2012. 49 Resumen (abstract) La teor´ıa algebraica de grafos se ocupa de la relaci´on entre las propiedades de la estructura combinatoria de un grafo y aquellas de los objetos algebraicos (polinomios, matrices, etc.) construidos a partir de ella. Cuando las aristas del grafo est´an dotadas de una direcci´on, lo que se conoce como un digrafo, de la combinatoria de ese grafo surge una estructura de orden o, equivalentemente, una estructura topol´ogica. De esta manera la teor´ıa algebraica de los digrafos tiene una lectura m´ultiple seg´un el lenguaje matem´atico elegido. Este trabajo quiere ser una breve ilustraci´on de este hecho: empieza con la equivalencia entre las facetas combinatoria, ordinal y topol´ogica de un digrafo y concluye con una exposici´on detallada de los resultados del art´ıculo [6], donde se establecen propiedades de las matrices laplacianas de entrada y salida de un digrafo en t´erminos del espacio topol´ogico asociado al digrafo. Tambi´en se indica un camino para tratar los digrafos localmente finitos. Algebraic Graph Theory deals with the relationship between the properties of the combinatorial structure of a graph and the properties of the algebraic objects (polynomials, matrices, etc.) derived from latter. When the edges of a graph are endowed of a direction (i.e., a digraph) the combinatorics of that graph yields an order structure or, equivalently a topological structure. This way the algebraic theory of digraphs has a variety of approaches, according to the chosen mathematical language. This work intends to be a brief survey of this fact: it starts with the equivalences among the combinatorial, order and topological faces of a digraph and it ends with a detailed exposition of the results from [6], where some properties of the outward and inward laplacian matrices of a digraph are stated in terms of the topological space associated to the digraph. The case of locally finite digraphs is suggested. 50