Conferencias – XV Seminario de Matemática Discreta

Digrafos fuertemente conexos minimales y
árboles: comparación de propiedades
estructurales y espectrales

Luis M. Pozo Coronado

Universidad Politécnica de Madrid

Resumen: El trabajo se centra en el estudio de algunas propiedades estructurales y espectrales de los digrafos fuertemente conexos minimales, a partir de la comparación de sus propiedades con las propiedades de los árboles. Se proponen algunas posibles factorizaciones de un digrafo fuertemente conexo minimal en términos de árboles (dirigidos o dobles), que esperamos resulten de utilidad para la comprensión estructural de estos digrafos, y para establecer algoritmos eficientes de búsqueda en ellos.

Trabajo conjunto con J. García López de Lacalle y C. Marijuán López.

Estructura de ciclos en digrafos
fuertemente conexos minimales

Jesús García López de Lacalle

Universidad Politécnica de Madrid

Resumen: En este trabajo mostramos un estudio de la estructura de los ciclos contenidos en un digrafo fuertemente conexo minimal (MSD – Minimal Strong Digraph). La estructura de un ciclo dado está determinada por las componentes fuertemente conexas (CFCs) que aparecen al suprimir los arcos del ciclo. Entre otras propiedades, demostramos que el número de CFCs que contienen vértices del ciclo es mayor o igual que $\lfloor (q+3)/2\rfloor$ , siendo $q$ la longitud del ciclo, que una CFC que contiene k vértices del ciclo tiene, al menos, $k$ vértices lineales (vértice con grados de entrada y salida 1), que el diagrama de Hasse de las CFCs tiene tantos vértices lineales (vértice de grado total 0 o con grados de entrada y salida 1) como maximales (minimales) y que el número de vértices lineales del MSD es mayor o igual que $\lfloor (q+1)/2\rfloor$ .

Trabajo conjunto con M. Arcos Argudo y L. M. Pozo Coronado.

Modelo de computación cuántica discreta de coeficientes enteros

Laura N. Gatti Dorpich

Universidad Politécnica de Madrid

Resumen: Los estados cuánticos de $n$ qubits se modelan como superposiciones de los estados básicos de los qubits $|a_0 a_1\dots a_{n-1}\rangle$ , donde $a_j$ toma los valores 0 ó 1 para todo $0\leq j<n$ . Por tanto, un $n$ -qubit es una superposición de todas las cadenas de bits de longitud $n$ . Si en dicha superposición solo aparece un término (cadena de bits), el estado sería clásico. Estos estados básicos constituyen una base ortonormal denominada base de computación y los $n$ -qubits son vectores unitarios en el espacio de Hilbert complejo de dimensión $2^n$ generado por dicha base.

La creación de algoritmos cuánticos se modela, entonces, mediante la definición de transformaciones unitarias sobre esta base. A estas transformaciones unitarias se las llama compuertas cuánticas. Un tema de investigación fundamental es el estudio de conjuntos universales de compuertas cuánticas, es decir, de conjuntos de compuertas que permiten generar, de forma exacta o aproximada, a todas las demás.

Siguiendo este rumbo, en este trabajo se busca encontrar un conjunto de compuertas que permita simplificar el modelo global. En este afán se buscará definir un conjunto de compuertas con las siguientes características: que sea finito, que conserve las propiedades cuánticas fundamentales (superposición, entrelazamiento y paralelismo) y que sea sencillo, por ejemplo, haciendo que las coordenadas de los $n$ -qubits permitidos (estados discretos) tengan parte real e imaginaria entera, ignorando el factor de normalización.

El modelo que se propone se construye a partir de dos compuertas cuánticas elementales: $H$ y $G$ . La primera es la compuerta de Hadamard y tiene una importancia enorme en computación cuántica ya que permite modelar la superposición de estados cuánticos. La compuerta $G$ es una compuerta de tres qubits, los dos primeros son de control y al tercero se le aplica, en función de los anteriores, la transformación unitaria $V$ :

$V=\left(\begin{array}{cc} 1 &0\\0 & i \end{array}\right)$

La llamamos $G$ porque, como se verá, genera estados discretos cuyas coordenadas son enteros de Gauss ( $\Z[i]$ ), salvo un factor de normalización de la forma $\sqrt{2}^k$ como se buscaba.

Trabajo conjunto con J. García López de Lacalle.

El SNIEP en dimensión baja

Miriam Pisonero Pérez

Universidad de Valladolid

Resumen: SNIEP corresponde a la sigla en inglés de Symmetric Nonnegative Inverse Eigenvalue Problem (problema espectral inverso simétrico no negativo). Este problema consiste en buscar condiciones necesarias y suficientes para que una familia de números reales sea el espectro de una matriz simétrica no negativa. Cuando en este problema se suprime la condición de simetría en la matriz se habla de RNIEP (Real Nonnegative Inverse Eigenvalue Problem = problema espectral real inverso no negativo).

En esta charla haremos un breve recorrido histórico de ambos problemas y mencionaremos que permanecen abiertos para familias de tamaño mayor o igual a 5. El primer resultado sobre el RNIEP se debe a Suleǐmanova en 1949 y es una condición suficiente, mientras que el origen del SNIEP se debe a Fiedler en 1974. Hershkovich en su tesis en 1978 se plantea la pregunta de si ambos problemas, RNIEP y SNIEP, son iguales. Hubo que esperar hasta 1996 cuando Johnson, Laffey y Loewy probaron que ambos problemas son distintos. Se sabe que para familias de tamaño menor o igual que 4 RNIEP y SNIEP son problemas equivalentes y Egleston, Lenker y Narayan en 2004 prueban que para familias de tamaño 5 los problemas son distintos.

Nos centraremos en el SNIEP en dimensiones bajas y daremos las caracterizaciones que se conocen así como las matrices que tengan por espectro dichas familias.

Caracterización del conjunto de listas con traza cero realizables por compensación en el SNIEP

Julio Moro Carreño

Universidad Carlos III de Madrid

Resumen: El Problema Espectral Inverso No Negativo Simétrico (SNIEP, en su abreviatura en inglés) consiste en identificar todos los posibles espectros de una matriz simétrica real de dimensión dada con elementos no negativos. Se dice que una lista de números reales es simétricamente realizable si es el espectro de alguna matriz simétrica no negativa. Una de las condiciones suficientes más generales para la realizabilidad simétrica es la llamada C-realizabilidad, que puede resumirse como realizabilidad por compensación, esto es, una condición que, en circunstancias apropiadas, garantiza que el exceso de positividad de ciertas partes de la lista bajo estudio puede emplearse para compensar la negatividad del resto de la lista.

Presentaremos en esta charla una caracterización de carácter combinatorio del conjunto de listas C-realizables con suma cero. En particular, se demuestra como consecuencia de esta caracterización que el conjunto de listas C-realizables con suma cero es una unión de politopos, y que las caras de dichos politopos vienen descritas por ecuaciones que involucran combinaciones lineales con coeficientes 1 y -1 de los elementos de la lista. Además, enunciaremos de manera explícita las condiciones necesarias y suficientes para que una lista con cuatro elementos positivos o menos sea C-realizable.

Trabajo conjunto con C. Marijuán López.

Matrices no negativas permutativas con espectro prescrito

Ricardo L. Soto Montero

Universidad Católica del Norte, Antofagasta (Chile)

Resumen: Una matriz permutativa es una matriz en la cual cada fila es una permutación de la primera fila. En este trabajo, el resultado dado por Paparella en [Electron. J. Linear Algebra 31 (2016) 306-312] es extendido a listas más generales de números reales y complejos, y se da una respuesta negativa a una pregunta puesta por Paparella.

References

[1] R. Loewy, A note on the real nonnegative inverse eigenvalue problem, Electron. J. Linear Algebra 31 (2016) 765-773.

[2] P. Paparella, Realizing Suleimanova spectra via permutative matrices, Electron. J. Linear Algebra 31 (2016) 306-312.

[3] R.L. Soto, Applications of a Brauer theorem in the nonnegative inverse eigenvalue problem, Linear Algebra Appl. 416 (2006) 844-856.

[4] R.L. Soto, O. Rojo, J. Moro, A. Borobia, Symmetric nonnegative realization of spectra, Electron.J. Linear Algebra 16 (2007) 1-18.

Problemas espectrales inversos no negativos

Carlos Marijuán López

Universidad de Valladolid

Resumen: El Problema Espectral Inverso No-negativo (NIEP) consiste en caracterizar las colecciones de $n$ números complejos (contando multiplicidades) que son los autovalores de una matriz de orden $n$ cuyas entradas son números reales no negativos. Este problema es muy difícil, tiene una larga historia y es probablemente uno de los más destacados problemas del análisis matricial. A diferencia de otros problemas espectrales inversos, en el NIEP las herramientas conocidas son muy limitadas y los pequeños avances son muy apreciados. El NIEP tiene interesantes variaciones como el RNIEP, restringido a espectros reales, o el SNIEP para realizaciones matriciales simétricas de espectros reales (distinto del anterior). Es bien sabido que si un espectro es realizable por una matriz no negativa, entonces puede también realizarse por una matriz estocástica (no negativa con suma de filas 1), i.e., el NIEP equivale al NIEP estocástico. Sin embargo, el NIEP doblemente estocástico (DNIEP), aunque más restricitvo, no es menos difícil. Por otro lado, el NIEP y sus variaciones tienen una versión con traza cero, en la se consideran colecciones de números complejos o reales con suma cero realizables por matrices no negativas con diagonal nula. En algunos casos, esta restricción es suficientemente fuerte como para facilitar el problema. Haremos un extenso, pero informal, recorrido por este intrigante problema poniendo especial énfasis en las cuestiones abordables, y no tan abordables, que permanecen abiertas. Consideraremos especialmente problemas abiertos en diferentes contextos como el DNIEP, condiciones necesarias, resultados en baja dimensión y condiciones suficientes. Finalmente haremos algunas observaciones geométricas.

Distancias resistivas en redes

Ángeles Carmona Mejías

Universitat Politècnica de Catalunya

Resumen: La distancia resistiva es una herramienta útil para analizar propiedades estructurales de los grafos, o más generalmente de las redes, tales como la robustez, véase por ejemplo [2]. En contraste con la distancia geodésica estándar, la distancia resistiva tiene en cuenta todos los caminos entre pares de vértices. La alta sensibilidad de esta métrica con respecto a pequeñas perturbaciones, hace que sea adecuada para discriminar entre redes con formas y estructuras similares. Ésta es una de las principales razones por las que las resistencias efectivas y el correspondiente índice de Kirchhoff, definido como la suma de todas ellas, han emergido como un descriptor estructural en el marco de la Química Orgánica, donde la topología de los compuestos químicos está convencionalmente representada por una molécula en la que los pesos de las ramas corresponden a las propiedades de enlace, véase por ejemplo [3] y las referencias allí citadas. Las resistencias efectivas pueden expresarse en términos de la inversa de grupo de la matriz laplaciana de forma que el índice de Kirchhoff correspondiente es su traza.

Existen otros parámetros estructurales y distancias en redes que han sido estudiados con propósitos similares. Quizás la más relevante es la llamada «forest metric»‘ introducida por P. Chebotarev y E. Shamis a finales de los años 90, o más específicamente en su reformulación como «adjusted forest metric», véase [1]. Este tipo de métricas forman una familia uniparamétrica, donde el parámetro determina la proporción entre caminos largos y cortos entre vértices. Además, la distancia resistiva habitual es el valor asintótico de la métrica cuando el parámetro tiende a infinito. En esta comunicación veremos, en primer lugar, que cada distancia de la familia uniparamétrica corresponde de hecho a la distancia asociada a una resistencia efectiva correspondiente a un operador de Schrödinger en la red, de forma que las propiedades pueden analizarse dentro del marco de la Teoría del Potencial. Finalmente, daremos una caracterización combinatoria de las resistencias efectivas usando una generalización del conocido «Matrix-Tree theorem».

Trabajo conjunto con A. M. Encinas Bachiller y M. Mitjana Riera.

References

[1] P. Chebotarev and E. Shamis, The Forest Metrics for Graph Vertices, Electron. Notes Discrete Math. 11 (2002) 98-107.

[2] W. Ellens, F.M. Spieksma, P. Van Mieghem, A. Jamakovic, R.E. Kooij, Effective graph resistance, Linear Algebra Appl. 435 (2011) 2491-2506.

[3] Y. Yang and D.J. Klein, A recursion formula for resistance distances and its applications, Discrete Appl. Math. 161 (2013) 2702-2715.

Trabajo parcialmente subvencionado por el Ministerio de Economía Industria y Competitividad bajo el proyecto MTM2014-60450-R.

La función de Green de las ecuaciones en diferencias lineales de segundo orden

María José Jiménez Jiménez

Universitat Politècnica de Catalunya

Resumen: Las ecuaciones en diferencias lineales de segundo orden aparecen en una amplia variedad de problemas científicos y matemáticos, tanto en el ámbito general como en el aplicado. Por ejemplo, las ecuaciones homogéneas con coeficientes constantes están relacionadas con diversas sucesiones de números como las de Horadam, Fibonacci, Lucas, Pell y Jacobsthal, y también están íntimamente vinculadas a los polinomios de Chebyshev, presentes en multitud de áreas de las ciencias aplicadas. En el caso de coeficientes variables, las ecuaciones en diferencias lineales de segundo orden y homogéneas abarcan las recurrencias que generan destacados números combinatorios, tales como Fine, central Delannoy, Schröder o Motzkin, que juegan un importante papel en el campo de la combinatoria enumerativa. Además, estas ecuaciones están relacionadas con las denominadas recurrencias de tres términos y, en consecuencia, con funciones especiales, polinomios ortogonales y matrices de Jacobi presentes en modelos matemáticos de sistemas que aparecen en variadas ramas de la ingeniería. De hecho, las ecuaciones en diferencias de segundo orden corresponden a la discretización de las ecuaciones diferenciales de segundo orden y, por tanto, resultan muy útiles en análisis numérico y en la aproximación de la correspondiente aplicación física.

Se conocen expresiones explícitas de las soluciones de ecuaciones en diferencias lineales de segundo orden si los coeficientes son constantes, y son ampliamente utilizadas. Para coeficientes variables, también es bien conocida y fácil de obtener la fórmula cerrada de la solución para ecuaciones de primer orden, pero si la ecuación es de segundo orden, el único caso sencillo se da cuando disponemos de una solución no trivial, puesto que la técnica estándar de reducción del orden nos permite calcular otra solución linealmente independiente. No obstante, en el caso general las fórmulas cerradas son poco comunes y muy incómodas de aplicar. Además, se refieren casi exclusivamente al caso homogéneo.

Presentamos una expresión explícita para las soluciones de ecuaciones en diferencias lineales de segundo orden generales. En primer lugar, seguimos las pautas del caso diferencial, lo que nos permite establecer la definición de la función de Green en el caso discreto. De esta forma, todos nuestros resultados gravitan alrededor de la función de Green de la ecuación en diferencias, ya que esta función nos proporciona una solución particular de la ecuación completa y todas las soluciones de la homogénea. El siguiente paso es la obtención de una fórmula cerrada para el cálculo de la función de Green. Se consigue con una técnica principalmente combinatoria y expresando la función de Green mediante las que hemos denominado funciones de Chebyshev. Este nombre es debido a que cuando la fórmula obtenida se aplica al caso de coeficientes constantes, aparecen los polinomios de Chebyshev.

Por otro lado, también aportamos una caracterización completa de la función de Green y describimos sus propiedades. En particular, mostramos como la función de Green determina completamente los coeficientes de la ecuación, e identificamos aquellas funciones que son función de Green de alguna ecuación.

Trabajo conjunto con A. M. Encinas Bachiller.

Este trabajo está parcialmente financiado por el Programa Estatal de I+D+i del Ministerio de Economía y Competitividad mediante el proyecto MTM2014-60450-R.

Inversas generalizadas en redes de subdivisión

Enric P. J. Monsó Burgués

Universitat Politècnica de Catalunya

Resumen: El objeto de este trabajo es relacionar las matrices inversas de grupo asociadas a una red y las matrices inversas de grupo asociadas a una subdivisión generalizada de ésta.

Dada una red $\Gamma=(V,E,c),$ se define $\Gamma^{S}=(V^{S},E^{S},c^{S})$ una subdivisión generalizada de $\Gamma,$ como una nueva red en la que algunas ramas $\{x,y\}\in E$ (no necesariamente todas), han sido reemplazadas por dos nuevas ramas $\{x,v_{xy}\}$ y $\{v_{xy},y\}$ tras la introducción de nuevos vértices $v_{xy}$ y de tal forma que las nuevas conductancias satisfacen una condición de compatibilidad de tipo eléctrico (con respeto a las conductancias antecedentes).

Toda $M$ –matriz simétrica $A,$ puede relacionarse con un operador de Schrödinger $\mathcal{L}_q$ sobre una red y un potencial adecuados. La resolución de determinados problemas de Poisson $\mathcal{L}_q(u)=f$ (para $f$ convenientemente establecida) permite calcular la llamada función de Green $G(x,y),$ que en términos matriciales es $A^{\#},$ la matriz inversa de grupo de $A$ y que a su vez coincide con $A^{\dag},$ la matriz pseudo-inversa de Moore-Penrose. La función de Green, además, permite el estudio de parámetros estructurales de la red tales como las resistencias efectivas (entre pares de vértices) o el índice de Kirchhoff.

En el caso singular y planteado un determinado problema de Poisson en una red subdivisión generalizada, las correspondientes soluciones pueden definirse a partir de las soluciones de otro problema de Poisson, auxiliar y convenientemente bien establecido, en la red sin subdividir. En este algoritmo se precisa de una contracción de los datos en $\Gamma^{S}$ y de una extensión de la solución al problema en $\Gamma.$

Así pues, para calcular la matriz inversa de grupo asociada a una red de subdivisión generalizada, las soluciones a los determinados problemas de Poisson a resolver en ésta pueden relacionarse con las soluciones de otros problemas de Poisson definidos en la red base, en particular, los involucrados en la determinación de la función de Green, i.e., la matriz inversa de grupo asociada a la red base.

Trabajo conjunto con A. Carmona Mejías y M. Mitjana Riera

Dominación y conectividad en triangulaciones

Gregorio Hernández Peñalver

Universidad Politécnica de Madrid

Resumen: Los problemas de dominación en grafos han recibido mucha atención en los últimos tiempos por su importancia en redes. Han surgido multitud de variantes, muchas de las cuáles se recogen en el libro «Domination in graphs» de Haynes, Hedetniemi y Slater. Se presentarán resultados sobre dominación desde el punto de vista de la conexión, analizando los resultados ya conocidos y prestando especial atención a la dominación en grafos periplanos maximales. Que son interesantes porque corresponden, desde el punto de vista geométrico, a las triangulaciones de polígonos.

Dominación potencial y Zero Forcing en triangulaciones

Sandra Ranilla Cortina

Universidad Politécnica de Madrid

Resumen: Algunos de los problemas más estudiados en Teoría de Grafos son aquellos que hacen referencia al recubrimiento del grafo, siendo uno de los más clásicos el problema del conjunto dominante de un grafo. En este trabajo se han investigado algunas variantes del problema de dominación, como la dominación potencial y el Zero Forcing. Este estudio se ha realizado tanto desde el punto de vista combinatorio como algorítmico y se ha restringido a un tipo particular de grafos, los grafos periplanos maximales. Se expondrán las cotas obtenidas y los algoritmos desarrollados para las variantes citadas en grafos periplanos maximales.

Coloración en triangulaciones

Guillermo Esteban Pascual

Universidad Politècnica de Madrid

Resumen: Algunos de los problemas más estudiados en Teoría de Grafos son aquellos problemas que hacen referencia a la coloración del mismo, siendo uno de los más clásicos el problema de los tres colores. A partir de aquí, nuestra tarea ha consistido en estudiar variantes de coloración que atienden a la suma de los colores o la existencia entre vértices de un camino con distintos colores. Este estudio se ha llevado a cabo tanto desde el punto de vista combinatorio como algorítmico y se ha restringido a un tipo particular de grafos, conocidos como grafos periplanos maximales, grafos de gran importancia en el ámbito de triangulaciones de polígonos. Se mostrarán los cotas obtenidas en las variantes Sum Coloring y Rainbow Coloring para los parámetros fuerza y número de conexión irisada, respectivamente, en grafos periplanos maximales.