Descripción: Los grafos perfectos fueron definidos por Claude Berge en 1960. Un grafo G es perfecto cuando para todo subgrafo inducido H de G, el número cromático de H es igual al tamaño de un subgrafo completo máximo de H. Los grafos perfectos son de gran interés desde el punto de vista algoritmo: si bien los problemas de determinar la clique máxima y el número cromático de un grafo son NP-completos, éstos se resuelven en tiempo polinomial para grafos perfectos. Desde entonces, fueron definidas y estudiadas gran cantidad de variantes de los grafos perfectos. Entre ellas, los grafos clique-perfectos. Una clique en un grafo es un subgrafo completo maximal con respecto a la inclusión. Un transversal de las cliques de un grafo G es un subconjunto de vértice que interseca a todas las cliques de G. Un conjunto de cliques independientes es un conjunto de cliques disjuntas dos a dos. Un grafo G es clique-perfecto si el tamaño de un transversal de las cliques mínimo coincide con el de un conjunto de cliques independientes máximo, para cada subgrafo inducido de G. El término "clique-perfecto" fue introducido por Guruswami y Pandu Rangan en 2000, pero la igualdad de esos parámetro fue estudiada previamente por Berge en el contexto de hipergrafos balanceados. En 2002, Chudnovsky, Robertson, Seymour y Thomas demostraron una caracterización de los grafos perfectos por subgrafos prohibidos minimales, cerrando una conjetura abierta durante 40 años. También durante el año 2002 fueron presentados dos trabajos, uno de ellos de Chudnovsky y Seymour, y el otro de Cornuéjols, Liu y Vuskovic, que mostraban que el reconocimiento de esta clase era polinomial, resolviendo otro problema abierto formulado mucho tiempo atrás. La lista de subgrafos prohibidos minimales para la clase de grafos clique-perfectos no se conoce aún, y También es una pregunta abierta la complejidad del problema de reconocimiento. En esta tesis presentamos resultados parciales en estas direcciones, es decir, caracterizamos los grafos cliqueperfectos por subgrafos prohibidos minimales dentro de ciertas clases de grafos, a saber,

Descripción: Un grafo es balanceado si su matriz clique no contiene como submatriz ninguna matriz de incidencia arista-vértice de un ciclo impar. Se conoce una caracterización para estos grafos por subgrafos inducidos prohibidos, pero ninguna que sea por subgrafos inducidos prohibidos minimales. En esta tesis probamos caracterizaciones por subgrafos inducidos prohibidos minimales para los grafos balanceados restringidas a ciertas clases de grafos y mostramos que dentro de algunas de ellas conducen a algoritmos lineales para reconocer el balanceo. Un grafo es clique-perfecto si en cada subgrafo inducido el mínimo número de vértices que intersecan todas las cliques coincide con el máximo número de cliques disjuntas dos a dos. Contrariamente a los grafos perfectos, para estos grafos no se conoce una caracterización por subgrafos inducidos prohibidos ni la complejidad del problema de reconocimiento. En esta tesis caracterizamos los grafos clique-perfectos por subgrafos inducidos prohibidos dentro de dos clases de grafos, lo que implica algoritmos de reconocimiento polinomiales para la clique-perfección dentro de dichas clases. Un grafo tiene la propiedad de Kőnig si el mínimo número de vértices que intersecan todas las aristas iguala al máximo número de aristas que no comparten vértices. En esta tesis caracterizamos estos grafos por subgrafos prohibidos, lo que nos permite también caracterizar los grafos arista-perfectos por arista-subgrafos prohibidos.

Descripción: En esta tesis estudiamos caracterizaciones estructurales para grafos arcocirculares, grafos circulo, grafos probe de intervalos, grafos probe de interva 10s unitarios, grafos probe de bloques y grafos probe co-bipartitos. Un grafo es arc0 circular (circulo) si es el grafo de interseccion de una familia de arcos (cuerdas) en una circunferencia. Dada una familia hereditaria de grafos G, un grafo es probe G si sus vertices pueden particionarse en dos conjuntos: un conjunto de vertices probe y un conjunto de vertices nonprobe, de forma tal que el conjunto de vertices nonprobe es un conjunto independiente y es posible obtener un grafo en la clase G agregando aristas entre ellos. Los grafos probe G forman una superclase de la familia G. Por lo tanto, 10s grafos probe de intervalos y 10s grafos probe de intervalos unitarios generalizan la clase de 10s grafos de intervalos y 10s grafos de intervalos unitarios respectivamente. Caracterizamos parcialmente a 10s grafos arco-circulares, grafos circulo, grafos probe de intervalos y probe de interval0 unitario mediante subgrafos prohibidos dentro de ciertas familias hereditarias de grafos. Finalmente, es presentada una caracterizacion de 10s grafos probe co-bipartitos que lleva a un algoritmo de reconocimiento de tiempo polinomial para dicha clase y 10s grafos probe de bloques son caracterizados mediante una lista de subgrafos prohibidos.

Descripción: En esta tesis estudiamos la evolución, convergencia y optimalidad de algoritmos de búsqueda en grafos aleatorios a través de ejemplos y aplicamos estos resultados al estudio de cotas de desempeño para protocolos de comunicación en redes inalámbricas. En particular, estudiamos los siguientes problemas: - La determinación de la optimalidad asintótica del algoritmo grado-egoísta en una amplia clase de Modelos de Configuraciones y el computo de sus respectivos cocientes de independencia. Aunque el problema de hallar conjuntos independientes de tamaño máximo es en el caso general una tarea NP-difícil, mostramos que en cierta clase de grafos aleatorios el algoritmo grado egoísta construye conjuntos independientes asintóticamente máximos en tiempo polinomial. Además, utilizamos estos resultados para caracterizar el cociente de independencia de grafos de Erdös-Rényi (de grado medio menor a e) y para encontrar procedimientos numéricos que permitan calcular cotas superiores en Modelos de Configuraciones generales. - La evaluación del desempeño de variantes locales del algoritmo egoísta aplicados al problema de aproximar la capacidad de redes WiFi y su posible impacto en la justicia de la distribución de conexiones. Por otro lado, aplicamos estos resultados al estudio de una red de comunicación empírica: el sistema de antenas de celulares de Montevideo. - El cálculo de los tiempos de convergencia para algoritmos de respuesta óptima en problemas de optimización distribuida donde las acciones se estructuran como grafos aleatorios ralos. Usando estos resultados probamos, por medio de un lema de optimalidad, cotas inferiores generales para los tiempos de corrida de algoritmos locales de búsqueda. La mayoría de nuestros resultados son aplicados tanto a grafos de Erdös-Rényi como a Modelos de Configuraciones y se centran en el régimen asintótico de grafos grandes. Para establecerlos utilizamos y extendemos teoremas existentes sobre los tamaños asintóticos de ciertos sub-grafos en modelos de grafos aleatorios, junto con límites de escala y concentraciones de variables aleatorios para estudiar las dinámicas en ellos. Los problemas estudiados en esta tesis resultaron en los siguientes tres trabajos: [BJLS19][JS19b][JS19a]. De los cuales el último se encuentra aún en preparación.

Descripción: Un modelo arco-circular es un par M=(C,A) donde C es un círculo y A es una familia de arcos de C. Si ningún arco se encuentra contenido en otro arco entonces decimos que M es propio, mientras que si A satisface la propiedad de Helly entonces decimos que M es Helly. Un grafo G es arco-circular si es el grafo de intersección de los arcos de un modelo arco-circular M. Si además M es propio (resp. Helly) entonces decimos que G es un grafo arco-circular propio (resp. Helly). Los grafos arco-circulares y sus subclases son estudiados con especial atención desde fines de la década de 1960, y al día de hoy la literatura al respecto es muy vasta. Esto se debe a la gran cantidad de aplicaciones que poseen en áreas tan diversas como las bases de datos, la genética, la arqueología, la psicología, la economía, etc., y a las propiedades de su estructura combinatoria. El problema de reconocimiento de grafos arco-circulares, y de varias de sus subclases, puede ser resuelto en tiempo lineal. Más aún, un modelo arco-circular puede ser generado en tiempo lineal. En esta tesis estudiamos la clase de grafos arco-circulares desde una perspectiva estructural y algorítmica, concentrándonos principalmente en las subclases de grafos arco-circulares propios y Helly.

Descripción: Una biclique en un grafo es un subgrafo inducido bipartito completo maximal. El estudio de las bicliques ha recibido mucha atención en los últimos tiempos. El grafo biclique de G, KB(G), es el grafo de intersección de las bicliques de G. Este fue definido y caracterizado recientemente. Sin embargo, aún sigue abierta la pregunta sobre la existencia de un algoritmo eficiente que resuelva el problema de reconocimiento de grafos biclique. En esta tesis estudiamos el problema de reconocimiento de grafos biclique de algunas clases de grafos. Se pretende con esto, acercarse al problema de reconocimiento de grafos biclique en general, encontrando clases donde el problema de decidir si un grafo es grafo biclique sea polinomial o se pueda probar que es NP-completo. Entre otras, en este trabajo estudiamos el operador biclique aplicado a los grafos bipartitos cordales, split y bipartitos de permutación. También estudiamos el problema de reconocimiento de la clase biclique inversa de los grafos completos, es decir, dado un grafo, decidir si su grafo biclique es completo. Cabe mencionar que, dado que la cantidad de bicliques de un grafo puede ser exponencial, no siempre es eficiente construir el grafo biclique para responder esta pregunta.

Descripción: Dada una familia de conjuntos no vacíos S= {Si}, se define el grafo de intersección de la familia S como el grafo obtenido al representar con un vértice a cada conjunto Si de forma tal que dos vértices son adyacentes sí y sólo si los conjuntos correspondientes tienen intersección no vacía. Un grafo se dice círculo si existe una familia de cuerdas L= {Cv} veG [fórmula aproximada, revisar la misma en el original] en un círculo de modo que dos vértices son adyacentes si las cuerdas correspondientes se intersecan. Es decir, es el grafo de intersección de la familia de cuerdas L. Existen diversas caracterizaciones de los mismos mediante operaciones como complementación local o descomposición split. Sin embargo, no se conocen aún caracterizaciones estructurales de los grafos círculo por subgrafos inducidos minimales prohibidos. En esta tesis, damos una caracterización de los grafos círculo por subgrafos inducidos prohibidos, restringido a que el grafo original sea split. Una matriz de0’s y1’s tiene la propiedad de los unos consecutivos (C1P) para sus filas si existe una permutación de sus columnas de forma tal que para cada fila, todos sus1’s se ubiquen de manera consecutiva. En esta tesis desarrollamos caracterizaciones por submatrices prohibidas de matrices de0’s y 1’s con la C1P para sus filas que además son2-coloreables bajo una cierta relación de adyacencia, y caracterizamos estructuralmente algunas subclases de grafos círculo auxiliares que se desprenden de estas matrices. Dada una clase de grafos [letra griega pi], una [letra griega pi] -completación de un grafo G= (V;E)es un grafo H= (V;E[F) [fórmula aproximada, revisar la misma en el original] tal que H pertenezca a [letra griega pi]. Una [letra griega pi] -completación H de G es minimal si H0=(V;E[F0) [fórmula aproximada, revisar la misma en el original] no pertenece a [letra griega pi] para todo F0 subconjunto propio de F. Una [letra griega pi] -completación H de G es mínima si para toda [letra griega pi] -completaciónH0= (V;E[F0) de G [fórmula aproximada, revisar la misma en el original], se tiene que el tamaño de F es inferior o igual al tamaño de F0. En esta tesis estudiamos el problema de completar de forma minimal a un grafo de intervalos propios, cuando el grafo de inputes de intervalos. Hallamos condiciones necesarias que caracterizan una completación minimal en este caso, y dejamos algunas conjeturas para considerar en el futuro.

Descripción: El objetivo de esta tesis es investigar y ofrecer nuevas ideas para clasificarredes complejas basadas en sus propiedades topológicas de gran escala. Estamos interesados en estudiar las propiedades de redes de diferentesdominios, y encontrar características comunes que son compartidas por lasredes en cada una de ellas. Con las mismas pretendemos desarrollar algoritmosy técnicas que aprovechen los elementos comunes, para automatizarla clasificación de redes en sus respectivos dominios. Esta informacióntambién será de utilidad para determinar si una red artificial presenta lascaracterísticas esperadas para el dominio al que pretende pertenecer. Revisamos un gran número de métricas de complejidad encontradas enla literatura. De ellas, elegimos 13 que luego derivan en un total de 43métricas. Creamos un conjunto de redes de distintas fuentes, con 240 redesdistribuidas en 11 dominios. Aplicamos un análisis exhaustivo a lasmedidas obtenidas para ellas, analizamos su correlación y distribución estadística, e intentamos predecir las posibilidades de clasificación que tendríaun algoritmo automático a la hora de discriminarlas correctamente en susrespectivos dominios. Intentamos determinar si las mediciones obtenidas pueden ser usadaspara discriminar los distintos dominios estudiados. Para ello, presentamos 3 tipos de algoritmos de clasificación de la literatura (K Nearest Neighbors, Support Vector Machines y el sistema de Evolutionary Rule Learning BioHEL[9]). Las mediciones son utilizadas como valores de entrada para latarea de clasificación de distinguir el dominio al que pertenece cada red. Además, para entender el potencial que tienen para clasificar dominiosde redes, usamos el generador de grafos CiGRAM para crear un conjuntode 160 redes artificiales distribuidas en 8 dominios a modo de ejemplo. Analizamos su distribución estadística y ejecutamos los experimentospropuestos, donde algunos de los algoritmos logran una precisión de hasta 80%. Adicionalmente, observamos que es fácil interpretar los resultados queofrece el sistema BioHEL, ya que su salida está compuesta de reglas legiblespor una persona, que explican cómo clasificar redes en base a los valores delas métricas calculadas. Finalmente, aplicamos los experimentos propuestos usando las técnicasde clasificación revisadas, con los valores de métricas calculados para lasredes reales elegidas. Observamos una clasificación de menor precisióncon respecto a lo obtenido para las redes artificiales, y continuamos conescenarios experimentales adicionales para estudiar posibles mejoras, comoeliminación de outliers y particionamiento manual de los conjunto de entrenamientoy prueba. Luego de ejecutarlos, a pesar de que en promedio losresultados siguen siendo peores a los obtenidos para las redes artificiales,un subconjunto de los experimentos presenta una precisión de 80% comohabíamos obtenido anteriormente. Nuestras conclusiones permiten confirmar que es posible clasificar redesde distintos dominios considerando únicamente las mediciones obtenidas deun conjunto específico de métricas de complejidad, y también ofrecemosposibles mejoras a ser aplicadas en investigaciones futuras.

Descripción: En esta tesis estudiamos dos modelos: uno de propagación de epidemias y vacunación óptima en un grafo aleatorio y otro de intercambio de ideas. Comenzamos explicando los métodos de modelado y prueba de los resultados principales de la tesis. Describimos procesos markovianos con medidas aleatorias de Poisson y mediante propiedades de semi-martingalas probamos la convergencia de las trayectorias en el espacio de Skorokhod, bajo un escalamiento adecuado de las tasas de salto, a un sistema determinístico de ecuaciones diferenciales. El segundo capítulo está dedicado a un modelo epidémico de tipo SIR con vacunación óptima sobre un grafo aleatorio. Obtenemos un sistema infinito y determinístico que reducimos a uno de dimensión finita a través de una versión de la función generadora de la distribución inicial de grados. Posteriormente, mediante el uso de herramientas de la teoría de juegos y de control óptimo planteamos hipótesis muy generales para la existencia de estrategia de vacunación óptima (en un sentido viscoso) dentro de una familia funciones medibles que dependen del grado de los nodos y del tiempo, tanto en el caso individual como el centralizado. Derivamos una fórmula para el tamaño de la epidemia y del valor críıtico R0 que indica si habrá un brote en términos de los parámetros de la enfermedad, las tasas de vacunación y de la conectividad del grafo. El tercero presenta simulaciones de diferentes modelos epidémicos mediante integración numérica junto con un formalismo de modelado de eventos discretos basado en agentes. El cuarto es un modelo de propagación de ideas y análisis de consenso en una población con estructura etaria en la que se consideran nacimientos y muertes. Obtenemos la descripción de un límite fluido que luego caracterizamos con una ecuación en derivadas parciales mediante un método de grazing limit.

Descripción: El estudio del comercio internacional es una de las áreas de investigación clásicas de las ciencias económicas. Su caracterización empírica, a la vez que se remonta en el tiempo, constituye hoy en día un espacio de aplicación para nuevas técnicas, basadas en el uso intensivo de datos. El aumento en la disponibilidad de información curada para el conjunto de los países permite explorar nuevas técnicas de análisis. A su vez, las múltiples dimensiones del problema impiden que una única técnica de análisis permita capturar la totalidad del fenómeno. El presente trabajo se propone realizar diversas propuestas metodológicas para el estudio del comercio internacional, de forma tal que en su conjunto permitan obtener una visión novedosa de los datos. Para ello, se utilizan técnicas ampliamente difundidas en otros campos, como el análisis de grafos y los modelos generativos bayesianos, y se considera el comercio agregado entre países, así como la composición de las canastas exportadoras de los mismos.

Descripción: En esta Tesis estudiamos variantes del problema de coloreo de grafos para varias familiasde grafos, y analizamos el problema del conjunto independiente máximo bajo unenfoque de generación de planos de corte. En el problema del k; i-coloreo, asignamos conjuntos de colores de cardinalidad k a losvértices de un grafo G, de manera que los conjuntos que correspondan a vértices adyacentesen G intersequen en no más de i elementos y la cantidad total de colores usadossea mínima. Esta cantidad mínima recibe el nombre de número k; i-cromático y es denotadapor Xik(G). Este parámetro, que generaliza el número cromático X01(G), es tandifícil de trabajar que su valor es desconocido aún para grafos completos. Desarrollamosun algoritmo de orden lineal para el cómputo de Xik para ciclos y generalizamos esteresultado a grafos cactus. Adicionalmente, estudiamos la relación entre este problemaen grafos completos y un problema abierto clásico de teoría de códigos. Un b-coloreo de un grafo es un coloreo tal que cada clase color admite un vérticeadyacente a por lo menos un vértice perteneciente a cada una de las demás clases color. El número b-cromático de un grafo G, denotado como Xb(G), es el máximo número ttal que G admite un b-coloreo con t colores. Describimos un algoritmo polinomial paracomputar el número b-cromático de la clase de los grafos P4-tidy y estudiamos paraesta clase dos propiedades conocidas: la b-continuidad y la b-monotonía. Estudiamos además la versión sobre aristas del b-coloreo y su índice b-cromático asociado. Presentamos cotas para el índice b-cromático del producto directo de grafosy damos resultados generales para varios productos directos de grafos regulares. Introducimostambién un modelo sencillo de programación lineal para el b-coloreo dearistas, que utilizamos para calcular resultados exactos para el producto directo dealgunas clases de grafos. Finalmente, proponemos un nuevo método de generación de planos de corte para elproblema del conjunto independiente máximo. El algoritmo genera desigualdades derango y otras desigualdades válidas, y utiliza un procedimiento de lifting basado enla resolución del conjunto independiente máximo con pesos sobre un grafo de menortamaño.

Descripción: Esta tesis está dedicada al estudio de representaciones por operadores acotados en espacios Lp del álgebra de Leavitt LQ de un grafo. Sean Q un grafo orientado finito por filas y LQ su álgebra de Leavitt sobre C. Parap ∈ [1,∞) consideramos la noción de representación espacial de LQ por operadores linealesy acotados en un espacio Lp(X, μ), que generaliza la introducida por N.C. Phillips par el casoen que Q es la rosa de d pétalos, y LQ el álgebra de Leavitt Ld. Para cada p consideramos la completación Op(Q) de LQ bajo la norma ||a|| := sup ρ espacial ||ρ(a)|| (a ∈ LQ). Probamos que si LQ es simple y ρ es una Lp representación espacial no nula de LQ entonces ||a||ρ := ||ρ(a)|| no depende de ρ. En particular si LQ es simple, Op(Q) = ρ(LQ) paracualquier representación espacial no nula ρ. Probamos que si Q y F son dos grafos finitos por filas, y p y q distintos, no existe unmorfismo continuo de Op(Q) en Oq(F). Probamos además que Op(Q) es simple si y sólo si LQ lo es. Aquí, una Lp álgebra deoperadores A se dice simple si todo morfismo no nulo de A en otra Lp álgebra de operadoreses inyectivo. Esta definición de simplicidad no coincide con la de álgebras de Banach, puespodrían existir ideales cerrados que no sean el núcleo de un morfismo contractivo entre Lpálgebras de operadores, al contrario de lo que sucede en el caso de C*-álgebras. Probamos que existe una biyección entre la clase de ideales S1 invariantes en Op(Q) yel conjunto de subconjuntos de vértices hereditarios y saturados de Q. Este resultado esun análogo a la biyección ya conocida entre ideales graduados del álgebra de Leavitt y lossubconjuntos de vértices hereditarios y saturados. Para Q finito por filas arbitrario, calculamos la K-teoría topológica de Op(Q) y probamosque coincide con la de la C*-álgebra de Cuntz-Krieger de Q.