Proyectos
Un Acercamiento Computacional y Enumerativo a Problemas de Conteo de Estructuras Discretas.
Resumen
Una gran variedad de problemas en matemáticas y ciencias de la computación están relacionados con el modelamiento cuantitativo de estructuras discretas de gran tamaño. El problema básico se puede resumir en saber cuántos elementos de un tamaño fijo existen en una familia de objetos discretos. Estos objetos discretos pueden provenir desde las mismas matemáticas, como por ejemplo el conteo de árboles, grafos, permutaciones, caminos en el plano, entre otros, o de otras áreas como del análisis de algoritmos donde uno de los objetivos es analizar la complejidad computacional de un algoritmo dado, lo cual se puede estudiar desde un contexto puramente combinatorio. Para poder predecir el comportamiento cuantitativo de estas estructuras discretas se han desarrollado en los últimos años diferentes estrategias que permiten modelar de manera unificada estos objetos, aunque sean de diferente naturaleza. El modelamiento se puede condensar en dos grandes fases: un acercamiento experimental, el cual se basa en la generación de los objetos a estudiar mediante algún sistema de computo simbólico. Esta fase permite hacer estimaciones del número de elementos y a su vez hacer conjeturas sobre la forma en la que crece la sucesión de conteo. Para ello se aplican diferentes algoritmos que permiten hacer este tipo de predicciones. La segunda fase consiste en la formalización y demostración de los resultados obtenidos en la fase experimental. Esta fase recae en el estudio enumerativo (matemáticas discretas), analítico (variable compleja) y asintótico de las funciones generatrices asociadas al conteo de las estructuras discretas. Dentro de la gran variedad de objetos discretos que existen, hay uno de gran interés en la comunidad el cual tiene que ver con contar puntos reticulares \cite{Beck}, es decir puntos de coordenadas enteras al interior de poliedros acotados y convexos, o sobre regiones planas asociadas a objetos discretos como grafos, cadenas de texto, composiciones de enteros, permutaciones, etc. Las aplicaciones de este tema van desde la criptografía y programación entera, hasta temas teóricos en la teoría de números y la combinatoria. Este proyecto se concentrará en el análisis de la distribución de puntos reticulares sobre los grafos asociados a las palabras o cadenas de Catalan. Estas palabras fueron introducidas por Baril y otros en el 2019 en el contexto de cadenas que evitan sub-sucesiones de cadenas (pattern avoiding). Las palabras de Catalan están formadas por los números naturales bajo ciertas restricciones de crecimiento de cada símbolo que se inserta a la derecha, y tienen una interpretación natural en términos de gráficos de barras, los cuales a su vez se pueden considerar como grafos en rejillas. Recientemente, Mansour, Callan y otros (2020) han notado que este tipo de objetos tienen una combinatoria muy rica y que el conteo de varios parámetros como área y perímetro presenta dificultad. Esta complejidad del problema ha despertado el interés de la comunidad combinatoria, la cual está concentrando esfuerzos en describir la distribución de diferentes parámetros subyacentes en esta familia de palabras y grafos. Para estudiar estos parámetros se han utilizado entre otras cosas funciones generatrices, fracciones continuas y autómatas infinitos, lo cual deja una interacción rica entre combinatoria, teoría de números y teoría de la computación. La temática de investigación del proyecto está relacionada con los trabajos que se han desarrollado en los últimos años al interior del grupo de investigación \emph{DiscreMath: Matemáticas Discretas y Ciencias de la Computación}. Las técnicas propuestas en esta investigación han sido utilizadas exitosamente en el estudio de otras estructuras discretas como lo son caminatas en el plano \cite{CFJR, Rigo1, Ram1, Ram6, Ram9}, particiones de conjuntos \cite{BRam, BRam2, CMRV, MollRV}, poliminós asociados a composiciones de enteros \cite{Acosta, Bravo}, entre otros.
Convocatoria
Nombre de la convocatoria:CONVOCATORIA DE LA FACULTAD DE CIENCIAS SEDE BOGOTÁ DE LA UNIVERSIDAD NACIONAL DE COLOMBIA PARA APOYAR A PROFESORES QUE NO CUENTEN CON PROYECTOS FINANCIADOS EN LA VIGENCIA 2019-2021
Modalidad:Modalidad única
Responsable