Conferencias – XVI Seminario de Matemática Discreta

Grafos periódicos, Laplaciano magnético y

lagunas espectrales

Fernando Lledó Macau

Universidad Carlos III de Madrid

Resumen: Un grafo periódico $\widetilde{G}=(\widetilde{V},\widetilde{E})$ es un grafo infinito sobre el que actúa un grupo discreto finitamente generado $\Gamma$ y tal que el grafo cociente $G=\widetilde{G}/\Gamma$ es finito. En esta charla estudiaremos condiciones que garantizan que el espectro del Laplaciano asociado a $\widetilde{G}$ no llena todo el intervalo posible, e.d., que el espectro tiene lagunas espectrales. Para ello estudiaremos el Laplaciano magnético en el cociente e introduciremos un orden espectral en grafos finitos. Como corolario daremos una demostración de la conjetura de Higuchi-Shirai para árboles $\Z$ -periódicos.

Referencias

[1] J. S Fabila-Carrasco, F. Lledó and O. Post, Spectral gaps and discrete magnetic Laplacians, Lin. Algebra Appl. 547 (2018) 183-216.
[2] E. Korotyaev and N. Saburova, Magnetic Schrödinger operators on periodic discrete graphs, J. Funct. Anal. 272 (2017) 1625-1660.
[3] F. Lledó and O. Post, Eigenvalue bracketing for discrete and metric graphs, J. Math. Anal. Appl. 348 (2008) 806-833.
[4] T. Sunada, Topological Crystallography: With a View Towards Discrete Geometric Analysis, Springer, Tokyo (2013).

Autovalores respecto a un peso para

problemas de contorno mixtos discretos

Margarida Mitjana Riera

Universitat Politècnica de Catalunya

Resumen: En este trabajo se estudian sistemas lineales cuya matriz de coeficientes es irreducible y tiene la siguiente estructura por bloques

$A=\left(\begin{matrix}L& -C\\[2ex] -C^T & D\end{matrix}\right)$

donde $D$ es una matriz diagonal con coeficientes positivos, $C\ge 0$ y $L$ es una $Z$ -matriz simétrica. Esta clase de sistemas de ecuaciones lineales aparecen relacionados con problemas de contorno autoadjuntos tipo Dirichlet-Robin asociados a un operador de Schrödinger en una red finita. Concretamente, en primer lugar se define la función traza que está relacionada con el complemento de Schur $A/D$ . La traza permite considerar nulas las condiciones de contorno tipo Robin y reducir la dimensión del problema incorporando las condiciones de contorno al operador de Schrödinger. A continuación se caracteriza cuándo la Energía es semidefinida positiva en el subespacio de funciones que anulan las condiciones de contorno. Para ello, es fundamental la descripción de los potenciales admisibles mediante los potenciales de Doob que verifican una versión discreta de la desigualdad tipo Poincaré. Finalmente, estudiamos problemas de contorno para operadores de Schrödinger semidefinidos positivos y analizamos el problema de autovalores respecto de un peso. Es la primera vez, según la información de que disponemos, que se considera este problema en el contexto de los operadores discretos objeto del presente estudio.

Trabajo conjunto con Ángeles Carmona y Andrés M.Encinas.

Algunos resultados sobre la estructura

cı́clica de dı́grafos fuertemente conexos minimales

Luis M. Pozo Coronado

Universidad Politécnica de Madrid

Resumen: En el contexto de los digrafos fuertemente conexos minimales (MSD), nos centramos en la cuestión de cómo puede estar contenido un ciclo dentro del digrafo, en el sentido de cuál es la estructura del digrafo resultante al eliminar en el digrafo original las aristas del ciclo. Presentamos los resultados obtenidos junto con Jesús Garcı́a y Miguel Arcos, algunos de los cuales han sido publicados en Discrete Applied Mathematics. Los más relevantes de estos resultados implican la obtención de una cota inferior del número de vértices lineales de un MSD, en función de la longitud de cualquier ciclo contenido en él. También puede obtenerse una cota inferior del número de vértices lineales en función del máximo in- o exgrado de un vértice cualquiera. Analizamos algunas relaciones entre estos resultados y otros que afectan a la acotación de coeficientes del polinomio caracterı́stico de un MSD; o a la existencia de algoritmos eficientes de búsqueda de ciclos maximales en estos digrafos.

Trabajo conjunto con Jesús Garcı́a y Miguel Arcos.

Nuevos resultados en el SNIEP

Miriam Pisonero Pérez

Universidad de Valladolid/IMUVA

Resumen: El problema espectral inverso simétrico no negativo consiste en caracterizar las familias de números reales que son el espectro de una matriz simétrica no negativa. Este problema es conocido en la literatura por su acrónimo en inglés SNIEP (Symmetric Nonnegative Inverse Eigenvalue Problem) y debe su origen a Fiedler en 1974.

En esta charla haremos un breve recorrido histórico de este problema describiendo las caracterizaciones que se conocen y mencionaremos qué permanece abierto para familias de tamaño mayor o igual que 5. Nos centraremos en el SNIEP en dimensión 5 y veremos que cuando hay repetición de autovalores podemos asegurar que ciertas familias no son el espectro de una matriz simétrica no negativa. Estos nuevos resultados son un trabajo conjunto con Charles Johnson y Carlos Marijuán.

Espectros universalmente realizables

Carlos Marijúan López

Universidad de Valladolid/IMUVA

Resumen: El problema inverso de los divisores elementales para matrices no negativas (NIEDP) consiste en determinar condiciones necesarias y suficientes para la existencia de una matriz no negativa con divisores elementales prescritos. Si existe una matriz no negativa con espectro $\Lambda$ para cada posible forma canónica de Jordan permitida por $\Lambda ,$ diremos que $\Lambda$ es universalmente realizable $(\mathcal{UR})$ . El NIEDP está estrechamente relacionado con el Problema espectral inverso no negativo (NIEP), que consiste en caracterizar los espectros de matrices no negativas. Si existe una matriz no negativa $A$ con espectro $\Lambda$ diremos que $\Lambda$ es realizable y que $A$ es una realización de $\Lambda$ . Por otro lado, es bien sabido que una matriz no negativa $A$ es coespectral a una matriz no negativa $B$ con suma de filas constante.

En este trabajo, extendemos la coespectralidad entre $A$ y $B$ a una relación de semejanza entre $A$ y $B$ , cuando el radio espectral es un autovalor simple. También nos preguntamos si ciertas propiedades del NIEP, como las tres reglas que caracterizan la $C$ -realizabilidad de espectros, son extensibles o no al NIEDP.

Referencias

[1] J. A.I. Julio, C. Marijúan, M. Pisonero, R.L. Soto, On universal realizability of spectra, Lin. Algebra Appl. 563 (2019) 353-372.

Una teorı́a de perturbación estructurada

para autovalores de matrices simplécticas

Julio Moro Carreño

Universidad Carlos III de Madrid

Resumen: Es bien sabido que, dada una matriz con una estructura especial (simétrica, antisimétrica, Toeplitz, Hankel, etc.), el comportamiento de sus autovalores frente a perturbaciones arbitrarias puede ser muy distinto a su comportamiento frente a perturbaciones estructuradas, esto es, aquellas que preservan la estructura en cuestión.

En esta charla describiremos cómo derivar una teorı́a de perturbación estructurada a primer orden de perturbaciones simplécticas de matrices simplécticas, esto es, cómo obtener fórmulas explı́citas para los términos directores de los desarrollos asintóticos de los autovalores de perturbaciones infinitesimales de una matriz simpléctica que siguen siendo simplécticas.

Los dos ingredientes principales del análisis son: (i) una teorı́a de perturbación multiplicativa para autovalores de matrices cualesquiera, motivada por la estructura multiplicativa subyacente al grupo simpléctico; y (ii) las formas canónicas estructuradas para matrices simplécticas, que nos permitirán escribir los coeficientes directores, en la mayor parte de los casos, en términos de autovectores de la matriz original.

Trabajo conjunto con Fredy Sosa y Christian Mehl

Construcción de grafos coespectrales

John Stewart Fabila-Carrasco

Universidad Carlos III de Madrid

Resumen: El Laplaciano es un operador que actúa en grafos. Existen diversas nociones de Laplaciano (combinatorio, normalizado, magnético, etc.) según la información adicional que tengamos sobre el grafo (pesos en vértices, aristas y vector potencial). El espectro de este operador nos da importante información sobre el grafo (componentes conexas, número de vértices, aristas, bipartita, etc.). Dos grafos no isomorfos se dicen que son coespectrales o isospectrales si tienen el mismo espectro. En esta charla daremos una construcción geométrica que genera grafos coespectrales para el Laplaciano magnético normalizado. Los resultados presentados son parte de un trabajo en proceso [1].

Referencias

[1] J.S. Fabila-Carrasco, F. Lledó and O. Post, Construction of cospectral graphs, Manuscript in preparation (2019).

Una visión general sobre la Teorı́a de

Juegos

Águeda Mata Hernández

Universidad Politécnica de Madrid

Resumen: En esta charla se hará una rápida presentación de la Teorı́a de Juegos general para centrar rápidamente la atención en los juegos combinatorios. Los primeros análisis sobre juegos combinatorios individuales aparecieron publicados en 1902, pero fue en 1930 cuando independientemente R. Sprague y P. M. Grundy desarrollaron una teorı́a para tratar en general los juegos imparciales, que posteriormente fue ampliada por R. K. Guy y C. A. B. Smith. Desde entonces el interés por los juegos combinatorios va en aumento en una gran variedad de ramas de la matemática, y es que la teorı́a desarrollada para la resolución de juegos combinatorios ha permitido la obtención de una clase de números, denominados números surreales, descubiertos por John Horton Conway, que contiene a los reales y con los que pueden ser representados tanto los números transfinitos de Cantor como los infinitésimos. Donald Knuth escribió en 1974 un relato sobre ellos, titulado Números surreales: De cómo dos exestudiantes se dedicaron a la matemática pura y encontraron la felicidad total.

Guardias combinatorios versus guardias

geométricos en problemas de “Galerı́as de

Arte”

Gregorio Hernández Peñalver

Universidad Politécnica de Madrid

Resumen: Los problemas de Galerı́as de Arte se inician con la pregunta formulada en 1973 por Victor Klein: “¿Cuántos guardias son necesarios para vigilar un recinto poligonal de n lados?”. La respuesta es: n/3 guardias son suficientes y a veces necesarios para vigilar cualquier recinto con lados. Las segunda demostración (de Fisk en 1978) es un prodigio de simplicidad: (1) triangúlese el polı́gono, (2) 3-coloréense sus vértices y (3) elı́jase el color menos usado. Ahı́ se esconde un resultado más fuerte que el enunciado, porque a cada guardia (situado en un vértice) solo se le pide que vigile los triángulos incidentes. Es decir, mientras los guardias del enunciado son geométricos (no tienen limitada su visión), los guardias de la demostración son más débiles y se denominan combinatorios porque vigilan (dominan) en el grafo correspondiente a la triangulación del polı́gono. Sin embargo, como existe un ejemplo de polı́gono que necesita realmente n/3 guardias geométricos, el resultado es el mismo tanto para guardias geométricos como combinatorios. Desgraciadamente esta igualdad no es cierta para algunas variantes de los problemas de Galerı́as de Arte, por ejemplo cuando se permite a los guardias patrullar por los lados del polı́gono (guardias-arista). En la charla mostraremos cómo para ciertas variantes, tanto en la forma de vigilar como en el tipo de objetos a vigilar, hay equivalencia entre ambas clases de guardias y, al contrario, hay otras variantes en que las cotas son radicalmente distintas.

Optimizar medidas en redes

Delia Garijo Royo

Universidad de Sevilla

Resumen: Un problema clásico y extremadamente complejo en el diseño de redes, debido al gran número de factores que intervienen, es añadir conexiones para mejorar aspectos de la red como el tiempo de viaje, la capacidad o la conectividad. El modelo de red que se emplea en un escenario geométrico más simplificado es la red euclı́dea plana que es un grafo geométrico plano cuyas aristas tienen como peso asignado la distancia euclı́dea entre sus extremos. El objetivo en este tipo de redes es añadir segmentos para mejorar (o minimizar) alguna medida sobre la red resultante, siendo las medidas relacionadas con distancias las más estudiadas. Se pueden considerar dos variantes del problema, la versión discreta en la que los extremos de los segmentos añadidos son vértices, y la versión continua en la que los extremos de dichos segmentos pueden ser dos puntos cualesquiera sobre la red (no necesariamente vértices). El caso discreto es un problema de aumento que ha sido ampliamente estudiado para medidas como el diámetro o la dilación, más en su versión no geométrica que para grafos geométricos. En cambio, el estudio del caso continuo se inició en 2013 y desde entonces ha habido muy poco avance. Hay que tener en cuenta que el hecho de considerar todos los puntos sobre la red resultante (incluidos los de los segmentos añadidos) para el cálculo de distancias incrementa enormemente la dureza del problema. En esta charla nos centraremos en la versión continua de este problema explicando los resultados existentes, los elementos que hacen difı́cil y lento el avance y un buen número de cuestiones que serı́an muy interesantes de aproximar.

Financiado por MINECO a través del proyecto MTM2015-63791-R.

Control de errores en Computación

Cuántica

Jesús Garcı́a López de Lacalle

Universidad Politécnica de Madrid

Resumen: La Computación Cuántica es un tema de investigación actualmente muy activo, debido fundamentalmente a la fuerte inversión que en este campo están realizando empresas tan importantes como IBM, Microsoft o Google. Sin embargo, el control de errores sigue siendo el principal problema para que esta tecnologı́a tan prometedora se haga realidad. En esta charla vamos a analizar en detalle los problemas con los que nos encontramos para controlar los errores en un ordenador cuántico.