DiscreMath Seminar

Resumen: Continuando con el estudio de la obra de Paul Erdős, exploraremos dos de sus resultados en geometría discreta. Empezaremos con el teorema del final feliz, que asegura que en cualquier conjunto de cinco o más puntos en el plano, siempre que no haya tres colineales, se puede encontrar un polígono convexo de cuatro vértices, y veremos las cotas que Erdős y Szekeres propusieron para el caso general de n vértices. Después pasaremos al teorema de De Bruijn–Erdős, que afirma que un conjunto de n puntos en el plano, siempre que no estén todos alineados, determina al menos n rectas diferentes.

Resumen: En esta charla presentaremos la demostración elemental de Paul Erdős del postulado de Bertrand, el cual afirma que para todo entero n>1 existe al menos un número primo p con n < p < 2n. Siguiendo la exposición de Václav Chvátal en The Discrete Mathematical Charms of Paul Erdős, destacaremos los ingredientes combinatorios y aritméticos fundamentales de la prueba. En particular, subrayaremos el papel de los coeficientes binomiales, las desigualdades y las ideas de conteo ingeniosas que permiten una demostración accesible sin recurrir a herramientas analíticas avanzadas.

Resumen: This talk explores the concept of a projective rectangle (PR), a generalization of the projective plane. Within the context of this incidence structure, which consists of points and lines, we distinguish between special lines, containing a unique special point, and ordinary lines. Notably, in a projective plane---a well-known example of a projective rectangle---any point can assume the role of the special point, particularly in cases derived from finite fields. However, in a more general scenario, there exists a unique special point.

We delve into various examples of projective rectangles, providing insights into their connections with full algebraic matroids, specifically harmonic matroids. Additionally, we explore the relationships between projective rectangles, graph theory, biased graphs, and orthogonal arrays. Throughout this ongoing work, conducted in collaboration with T. Zaslavsky we aim to highlight the current progress and key findings of our research.

Resumen: En esta charla, exploraremos el fascinante mundo de las sucesiones generalizadas de Fibonacci. Comenzaremos con una visión general de estas sucesiones, destacando sus propiedades más notables, que han capturado la atención de matemáticos y entusiastas de la combinatoria, y que dan lugar a áreas activas de investigación. Posteriormente, analizaremos el impacto de estas sucesiones en la descripción de diversos objetos combinatorios, como palabras, árboles, composiciones y, especialmente, poliminós. Además, realizaremos un examen detallado del conteo de diversas estadísticas en la familia de poliminós generada por las sucesiones generalizadas de Fibonacci, abordando aspectos como el área, el semiperímetro, el número de puntos internos y el número de vértices de grado 1, 2 y 3, entre otras estadísticas relevantes.

Resumen: En esta conferencia abordaremos el problema de dividir una grilla de tamaño m.n mediante regiones poligonales (poliminós), las cuales se pueden pintar con k colores diferentes. Luego, mostraremos una generalización de este problema en el contexto de grafos. 

Resumen: En esta charla discutiremos algunos resultados importantes que nos permiten resolver problemas de clasificación vía redes neuronales. Veremos cómo los algoritmos de clasificación pueden ser modelados con funciones discontinuas donde el borde posee una cierta regularidad. Discutiremos diferentes tipos de regularidad para la frontera de decision y presentaremos resultados que ilustran la existencia de redes neuronales que resuelven el problema. Principalmente, utilizaremos redes neuronales cuya función de activación es la ampliamente utilizada función ReLU.  Introduciremos el espacio de funciones tipo Barron y presentaremos resultados donde la frontera de decisión del problema es de dicho tipo.  

Resumen: We will review the use of partial Bell polynomials to enumerate colored compositions and Dyck paths and will discuss part-preserving bijections between these two families.

Resumen: Recientemente, los autores han logrado determinar cuándo una familia específica de variedades de Schubert es esférica utilizando los caminos reticulares de Dyck. Además, han introducido un nuevo concepto conocido como "variedad casi tórica". En términos generales, esto se refiere a la codimensión de la acción del toro máximo en una variedad esférica, que es igual a uno.

En esta charla, se presentarán fórmulas detalladas para calcular la cardinalidad de estas importantes familias y se derivarán sus funciones generadoras correspondientes. Además, durante el proceso de enumeración, surgirán los números de Fibonacci. Este trabajo es el resultado de una colaboración con Mahir Bilen Can.

Resumen: El objetivo de esta charla es dar a conocer una conexión entre el álgebra y la combinatoria dada por la positividad total. Se iniciará hablando de las matrices totalmente positivas, su descomposición y algunas propiedades. Posteriormente, se introducirá una familia de grafos dirigidos llamados redes planares. Estas nociones darán lugar al lema de Lindström que nos permitirá conectar estas dos áreas. Finalmente, usando como herramienta las funciones simétricas, se establecerá un criterio que permitirá determinar si un polinomio tiene todas sus raíces reales positivas haciendo un estudio únicamente sobre sus coeficientes. 

Prerrequisitos: Álgebra lineal básica.

Resumen: Un autómata finito determinista (o simplementeautómata) se dice completamente alcanzable (completely reachable) si cualquier subconjunto propiode estados es la imagen de una palabra del autómata. Daremos una caracterización simple para autómatascompletamente alcanzables con solo dos letras.Después se discutirá un concepto dual al de ser completamente alcanzable y también se dará unacaracterización para esta clase de autómatas. 

Resumen: Se sabe que existe una fuerte conexión entre la música y las matemáticas.  En esta charla hablaremos de cómo ven los músicos los collares y otros objetos combinatorios a la hora de componer.

Resumen: Por la forma en la que fueron creados, los hipergrafos modelan relaciones más generales que los grafos. Lo que proporciona una herramienta de gran utilidad para representar problemas en redes biológicas, redes de telecomunicación, procesos de planificación, estructuras de datos, entre otros problemas donde las relaciones entre los objetos son complejas por lo que resulta mejor representarlas en conjuntos que en parejas. En esta charla se explicará qué son los grafos, los multigrafos y los hipergrafos, algunas de sus propiedades, sus diferencias, y finalmente mostraremos en qué situaciones y por qué es más adecuado usar hipergrafos en lugar de grafos. Para esto hablaremos de algunas matrices que representan los grafos, multigrafos e hipergrafos, y sobre estas matrices estudiaremos propiedades que nos brindan información sobre conexidad y corte en hipergrafos.

Resumen: En diversos campos del conocimiento, las redes son utilizadas para describir relaciones y procesos. Por ejemplo, en ciencias de la computación, el internet se puede entender como una red. Por lo general, estasredes resultan ser complicadas, con estructuras y subestructuras muy complejas. Para simplificarlas, se pueden utilizar grafos, los cuales permitendescomponerlas por operaciones. En esta charla, se describirá una operación de grafos conocida como"potencia simétrica tensorial", se mostrarán algunosejemplos de cómo se ven ciertos grafos bajo estaoperación y se discutirán sus propiedades espectrales y combinatorias. Además, se presentarán resultados de un trabajo conjunto con W. Astaiza, A. Barrios, H. Chimal-Dzul, S. R. García, J. Lopez, V. H. Moll y Y. Puig.

Resumen: Presentamos un estudio sistemático de la distribución del último símbolo en el conjunto de las palabras de Catalan que evitan un patrón consecutivo de longitud a lo más tres. Para cada patrón, proporcionamos una función generatriz bivariada con respecto a la longitud y el último símbolo de dichas palabras. Deducimos sus relaciones de recurrencia y formas cerradas, y presentamos aproximaciones asintóticas para el valor esperado del último símbolo de las palabras de Catalan que evitan esos patrones. Finalmente, caracterizamos sus sucesiones usando arreglos de Riordan. 

Resumen: Building mathematical and computational grounded solutions to the Risk-based Resource Allocation problem suitable to be used for supporting decision-making in the formulation of management and response policies during a pandemic. The solutions are framed in the COVID-19 pandemic in Bogotá, the largest and most crowded city in Colombia. 

Resumen: Secret sharing is a cryptographic primitive, and it is the basis of secure multiparty computation.  The linear secret sharing scheme of Shamir is one of the most beautiful constructions of discrete mathematics, and it is an optimal solution for threshold structures. Can we construct optimal solutions for any access structure? Can we determine the information ratio of the optimal solutions? We comment on some recent results asserting that those problems are unsolvable.  We obtain as easy corollaries two interesting results: the linear region and the entropic region are not semialgebraic.

Resumen: String pattern matching is the problem where, given a text string T[0..n-1] and a pattern string P[0..m-1] both defined on a given alphabet Sigma, the goal is to find all the occurrences of P in T, i.e. the set {0<=j<= n-m | P=T[j..j+m-1]}. This problem has important applications in several areas like information retrieval, bioinformatics, music retrieval, and image processing, to name a few. Several algorithms have been devised to solve this problem, from several approaches, including the utilization of data structures, bit parallelism, the computation of prefixes and suffixes and certain traversal orders. However, the most efficient in practice is the Boyer-Moore algorithm. Its success stems from the following facts: (i) it compares P with T[j..j+m-1] from right to left; (ii) it makes use of the bad character rule ; and (iii) it utilizes the good-suffix rule. This talk will discuss all of these aspects in detail to illustrate how the problem is tackled and some of the ideas used in string matching research.

Resumen:  Se puede considerar las pruebas como el fundamento de la matemática. Sin embargo, esas casi nunca son interactivas. En su artículo seminal, Goldwasseret al. introdujeron la noción de pruebas interactivas para demostrar una declaración sin dar nuevos conocimientos al verificador. Esas «Pruebas de conocimiento cero» (ZKPs) hoy en día tienen un papel importante en la criptografía. Por ejemplo, se las utiliza para “privacy-enhancing technologies”, firmas digitales y como base de protocolos avanzados, asegurando la honradez de las participantes. El objetivo principal de la charla es explicar matemáticamente el funcionamiento de ZKPs. 

Resumen:

We study the problem of learning local languages fromsubsequences. Local languages are captured for theshort-term fragment of first order logic. We can use subsequences to learn languages that are defined in the long-term fragment. How can we collate those twopromissory facts?

Resumen: El estudio y conteo de diferentes parámetros o estadísticas en objetos discretos es un campo importante de investigación en combinatoria enumerativa. Particularmente, se dice que en un objeto combinatorio con una sucesión numérica asociada se da la ocurrencia de un patrón (arreglo de enteros positivos consecutivos que incluyen el 1), si existe una subsucesión tal que su reducción canónica (asignar a cada elemento su posición de menor a mayor en la subsucesión) coincide con el patrón considerado. En este charla se presentarán diferentes técnicas que permiten estudiar y obtener resultados para el conteo de la ocurrencia de los patrones consecutivos 121 (pico simétrico), 132 y 231 (picos asimétricos) en algunos objetos combinatorios discretos de interés, además de definir la noción de simetría desde el estudio de la ocurrencia de estos patrones. Se presentarán los distintos resultados obtenidos para este problema. 

Resumen:

Uno de los objetivos principales de la combinatoria extremal es estudiar la influencia de patrones locales en la estructura global de ciertos objetos.

La densidad de homomorfismos de un grafo H en un grafo G puede entenderse como la probabilidad de encontrar una copia de H en G. Históricamente, el estudio de homomorfismos entre grafos ha sido de gran interés. Por ejemplo, la conjetura de Sidorenko afirma que la densidad de homomorfismos de un grafo bipartito H en un grafo cualquiera G es siempre mayor que la densidad de homomorfismos del grafo K2 en G. El objetivo principal de esta charla es mostrar como se puede utilizar la Teoría de la información, en particular el concepto de entropía, para traducir problemas relacionados a homomorfismos entre grafos en un problema de optimización lineal y ejemplos de aplicación de esta técnica sobre árboles.