TACO
Tardes de Álgebra, Combinatoria y Optimización
El Departamento de Matemáticas del Cinvestav-IPN los invita a las Tardes de Álgebra, Combinatoria y Optimización (TACO).
Comité Organizador:
Ruy Fabila Monroy
ruyfabila [@] math.cinvestav.edu.mx
2022
25 de agosto de 2022. Salón 131, Departamento de Matemáticas. Cinvestav-IPN
13:00 Hrs.
Dr. Jesús de Loera
Departamento de Matemáticas, Universidad de California, Davis
Random Monomial Ideals
Resumen: Randomness is a key algorithmic tool in algebra. In this talk I will discuss our recent work describing the random behavior of monomial ideals. Our work is a natural generalization of classical work on random graphs and random simplicial complexes. Under this model we outlined some basic properties of random monomial ideals. For example, I will present theorems about the probability distributions, expectations and thresholds for events of monomial ideals with given Krull dimension, Hilbert function, and the average behavior of minimal-free resolutions. Joint work with S Petrovic, L Silverstein, D. Wilburne, S. Hosten.
9 de febrero de 2022. Vía Zoom.
https://us02web.zoom.us/j/81779549577
ID de la reunión: 817 7954 9577
16:30 Hrs.
Rosna Paul
Institute for Software Technology. University of Technology, Graz, Austria
Perfect matchings with crossings
Resumen: In this talk, we analyze the number of straight-line perfect matchings with k crossings on point sets of size n = 2m in general position.
We show that for every k ≤ 1 / 64 n2 - θ(n √n), every n-point set admits a perfect matching with exactly k crossings and that there exist n-point sets where every perfect matching has fewer than 5n2 /72 crossings. Finally, we show that convex point sets maximize the number of perfect matchings with $\binom{n/2} {2}$ crossings and with ${\binom{n/2} {2}}-1$ crossings.
This is a joint work with Oswin Aichholzer, Ruy Fabila-Monroy, Philipp Kindermann, Irene Parada, Daniel Perz, Patrick Schnider and Birgit Vogtenhuber.
8 de febrero de 2022. Vía Zoom.
https://us02web.zoom.us/j/84177455075
ID de la reunión: 841 7745 5075
16:30 Hrs.
Alexandra Weinberger
Institute for Software Technology. University of Technology, Graz, Austria
Finding plane subdrawings via generalized twistedness
Resumen: We consider simple drawings, a very intuitive type of graph drawings that has received much attention in the past decades. Simple drawings are drawings of graphs in which edges are Jordan arcs connecting their endpoint such that two edges intersect at most once, either in a common endpoint or in their interior (forming a proper crossing). We focus on the questions about the size of the largest plane matching and the length of the longest plane path in any simple drawing of the complete graph. We introduce a special type of simple drawing, which we call generalized twisted drawing, that we can use to improve the lower bound for both questions. A simple drawing is generalized twisted if there is a point O such that every ray emanating from O crosses every edge of the drawing at most once, and there is a ray emanating from O which crosses every edge exactly once.
2019
28 de marzo de 2019. Salón 131, Departamento de Matemáticas. Cinvestav-IPN
15:00 Hrs.
Jean Cardinal
Université Libre de Bruxelles, Bélgica
The geometry of 3SUM, k-SUM, and related problems
Resumen: We consider the 3SUM and k-SUM problems, defined as fixed-parameter versions of the Subset Sum Problem: Given a set of n numbers, does there exist a subset of k of them whose sum is 0? The 3SUM problem was first considered by computational geometers as a way to argue of quadratic lower bounds for some natural geometric problems. It has since become a cornerstone of the so-called fine-grained complexity theory, dealing with the computational complexity of problems in P. We will consider recent attempts to beat the quadratic barrier for 3SUM-hard problems. As time permits, we will also consider the design of efficient linear decision trees for k-SUM. These results heavily rely on geometric notions, such as dominance detection and hyperplane arrangements.
2018
18 de septiembre de 2018. Auditorio José Ádem, Cinvestav-IPN
16:00 Hrs.
Fabian Klute
Technische Universität Wien, Austria
Bounded cliquewidth of strict outerconfluent drawings
Resumen: Strict outerconfluent drawings are a version of confluent graph drawings, which allow an adjacency preserving bundling of the edges. The result is a plane drawing. We study the cliquewidth of such drawings. Specifically we will show that the cliquewidth of tree-like strict outerconfluent drawings is constant.
In my talk I will introduce parameterized complexity and the basic concept of cliquewidth, a well studied parameter in the area, and how it can be applied in a graph drawing setting.
2017
5 de octubre de 2017. Auditorio José Ádem, Cinvestav-IPN
15:00 Hrs.
Irene Parada
Institute for Software Technology. University of Technology, Graz, Austria
Una cota inferior superlineal para el número de 5-hoyos
Resumen: Sea P un conjunto finito de puntos en el plano en posición general, es decir, tal que no hay tres puntos de P colineales. Decimos que cinco puntos de P forman un 5-hoyo en P si son los vértices de un pentágono convexo vacío. Para un entero positivo n, h5(n) denota el mínimo número de 5-hoyos entre todos los conjuntos de n puntos en el plano en posición general.
A pesar de los muchos esfuerzos en los últimos 30 años, las mejores cotas asintóticas inferior y superior para h5(n) han sido de orden Ω(n) y O(n2) respectivamente. Mostraremos que h5(n) = Ω(n log(4/5) n), obteniendo la primera cota inferior superlineal para h5(n). El siguiente resultado estructural, que podría resultar interesante por si mismo, es un paso crucial en la prueba de esta cota inferior.
Si un conjunto finito de puntos en el plano en posición general está dividido por una línea l en dos subconjuntos de al menos 5 puntos cada uno, entonces uno de los subconjuntos se encuentra en posición convexa o l intersecta un 5-hoyo en P. La prueba de este resultado requiere de la asistencia del ordenador.
15 de agosto de 2017. Auditorio José Ádem, Cinvestav-IPN
15:00 Hrs.
Cristina Dalfó
Universitat Politècnica de Catalunya, Barcelona
Characterizing identifying codes in a digraph or graph from its spectrum
Resumen: A (1, ≤ l)-identifying code in digraph D is a subset C of vertices of D, such that all distinct subsets of vertices of D with cardinality at most l have distinct closed in-neighbourhoods within C. Here we study the relation between identifying codes digraphs and their spectra. The obtained results can also be applied on graphs.
20 de julio de 2017. Auditorio José Ádem, Cinvestav-IPN
Transmisión en vivo por http://www.bfm.cinvestav.mx/transv.html
15:00 Hrs.
Frank Duque
Instituto de Matemáticas, Universidad de Antioquia, Medellín, Colombia
Sistemas hexagonales con índices topológicos extremos
Resumen: Los índices topológicos son parámetros numéricos de las gráficas que caracterizan su topología. En las gráficas moleculares, los índices topológicos han sido ampliamente utilizados para establecer correlaciones entre la estructura de un compuesto molecular y sus propiedades físico-químicas.
Los sistemas hexagonales son gráficas planares donde sus caras interiores están delimitadas por hexágonos regulares. En esta charla hablaremos sobre los valores extremos de índices topológicos en sistemas hexagonales.
16 de marzo de 2017. Auditorio José Ádem, Cinvestav-IPN
16:00 Hrs.
Josh Tobin
Universidad de California, San Diego
Four Conjectures in Spectral Graph Theory
Resumen: We present the proofs of four extremal conjectures in spectral graph theory. The results are motivated by applications such as measures of graph irregularity and graph connectivity. The most significant of the four is determining which planar graph of a given order n has largest spectral radius, which was conjectured to be the join of Pn-2 and P2 by Boots and Royle in 1991, and independently by Cao and Vince in 1993. A common thread in the results is the use of a stability version of a classic inequality of Stanley. Finally, some directions for future work are discussed. This is based on two joint papers with Michael Tait.
2 de marzo de 2017. Auditorio José Ádem, Cinvestav-IPN
14:00 Hrs.
Onur Cagirici
Masaryk University, Faculty of Informatics
Hyperplanar Structures Realization
Resumen: Range-based localization is an important and well-studied problem in computer science. It is defined as follows: given a unit distance graph, assign coordinates to vertices by satisfying pairwise distances. To assign coordinates a vertex in d-dimensional space, we need to reduce the degree of freedom of that vertex from d+1 to zero. A degree of freedom can be reduced either by obtaining a distance to a know point or embedding it a lower dimensional space e.g. a straight line on a plane. Since reducing all degrees of freedom by available distances requires high connectivity, we aim to find group of vertices those can be embedded onto lower dimensional structures. We refer to the problem of partitioning a d-embeddable graph into (d-1)-embeddable induced subgraphs as hyperplanar strucutres realization. For the sake of simplicity, we consider a 2-embeddable graph and try to find a method to determine collinear points by given pairwise distances. Our partial results in this work includes some hard variations of given problem.
26 de enero de 2017. Auditorio José Ádem, Cinvestav-IPN
15:00 Hrs.
Luis Evaristo Caraballo de la Cruz
Universidad de Sevilla
The resilience of a synchronized communication system
Resumen: Consider a bipartite and connected unit disk contact graph with n nodes. Suppose now that we have n robots (one per circle) moving along the circles performing some task with the same constant speed such that every pair of robots in tangent circles are moving in opposite directions i.e one in CW and the other in CCW.
We say that two neighboring robots are synchronized if they arrive at the common tangent point at the same time.
We say that a system is synchronized if every pair of neighboring robots is synchronized.
If one or more robots leave the system then their circles and the corresponding tasks are unattended. To handle such cases in a synchronized system, when a live robot arrives to a tangent point and detects the absence of the neighbor, it switches to the neighboring trajectory and follows the movement direction assigned to the neighboring circle in order to assume the unattended task.
If enough robots leave, it may occur that a live robot enters a state of starvation, failing to permanently meet other robots during flight. To measure the tolerance of the system to this phenomenon we define the k-isolation-resilience as the minimum number of robots whose removal may cause that at least k live robots enter in state of starvation.
Also, may occur that some trajectory sections are no longer visited by any robot. To measure the tolerance of the system to this phenomenon we define the uncovering-resilience as the minimum number of robots whose removal may cause that at least one section of a circle is no longer visited.
This talk addresses the problem of computing these resilience measures.
2014
18 de diciembre de 2014. Auditorio José Ádem, Cinvestav-IPN
15:00 Hrs.
Alfredo Hubard
GEOMETRICA
INRIA Sophia-Antipolis
Límites de tipos de orden
Resumen: El tipo de orden es un invariante fundamental en geometría combinatoria y computacional dedicado a estudiar dependencias afines y convexas de conjuntos de puntos sin necesidad de expresar los puntos por sus coordenadas.
Dada una secuencia de conjuntos de puntos Pn decimos que su tipo de orden es convergente a la función l, si para cualquier tipo de orden χ, la probabilidad de que k puntos aleatorios de Pn tengan tipo de orden χ, converge a el valor l(χ) cuando n va a infinito.
Esta definición es completamente análoga a la de límite de gráficas densas de teoría de gráficas.
Utilizamos este contexto para reformular el problema clásico de Sylvester: cual es la probabilidad de que k puntos formen los vértices de un polígono convexo. En la versión n del problema que estudiamos, el caso k=4 corresponde al número de cruce de la gráfica completa y damos nuevas cotas inferiores para k=5 y k=6 utilizando optimización semi definitiva sobre la algebra de banderas de tipos de órdenes.
Por otro lado, demostraremos hasta que punto los límites de tipos de orden pueden ser representados por medidas en el plano.
Trabajo conjunto con X Goaoc. J. Volec, R. de Joannis de Verclos y J.S. Sereni.
5 de noviembre de 2014. Auditorio José Ádem, Cinvestav-IPN
15:00 Hrs.
Frank Duque
Departamento de Matemáticas, Cinvestav-IPN
Cotas superiores para el problema de iluminación con k-modems
Resumen: Ya sea en un hogar, escuela, centro comercial, entre otros, comúnmente se requiere de una conexión inalámbrica mediante módems. Variables como el tamaño del establecimiento, las paredes en él y la potencia de los módems, pueden llevarnos a necesitar varios módems para cubrir todo el establecimiento con una buena señal inalámbrica. Entendemos por k-módem a un dispositivo inalámbrico capaz de atravesar k paredes sin perder su buena señal. El problema de encontrar la mínima cantidad de k-módems requeridos para cubrir una región, es conocido en geometría computacional como el problema de iluminación con k-módem. Polígonos y arreglos de segmentos disjuntos son dos de las instancias más comunes de este problema. En esta charla presentamos cotas nuevas y asintóticamente óptimas para estos casos del problema.
11 de septiembre de 2014. Auditorio José Ádem, Cinvestav-IPN
15:30 Hrs.
Birgit Vogtenhuber
Institute for Software Technology. University of Technology, Graz, Austria.
Order types and cross-sections of line arrangements in R3
Resumen: We consider sets L = {l1, ..., ln} of n labeled lines in general position in R3, and study the order types of point sets {p1, ..., pn} that stem from the intersections of the lines in L with (directed) planes Π, not parallel to any line of L, i.e., the proper cross-sections of L. As a main result we show that the number of dierent order types that can be obtained as cross-sections of L is O(n9), and that this bound is tight.
2 de abril de 2014. Auditorio José Ádem, Cinvestav-IPN
15:30 Hrs.
Walter Carballosa Torres
Universidad Autónoma de Guerrero
Invariance of the Gromov hyperbolicity in graphs under transformations
Resumen: If X is a geodesic metric space and x, y, z are in X, a geodesic triangle T={x, y, z} is the union of the three geodesics [xy], [yz] and [zx] in X. The space X is d-hyperbolic (in the Gromov sense) if any side of T is contained in the d-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by d(X) the sharp hyperbolicity constant of X, i.e., d(X) := inf {d: X is d-hyperbolic}. The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it.
In this dissertation we study the invariance of the hyperbolicity of graphs under certain transformations. First, we show that the study of the hyperbolicity of graphs can be reduced to the study of the hyperbolicity of simple graphs by removing loops and multiple edges. Besides, we show that any graph G can be transformed into a cubic graphs G' which is quasi-isometric to G and, consequently, G is hyperbolic if and only if G' is hyperbolic. These results allow to reduce the study of the hyperbolicity of graphs to the study of the hyperbolicity of cubic simple graphs.
In the context of graphs, to remove and to contract an edge of the graph are a very natural transformations. Other of the main aims is to obtain quantitative information about the distortion of the hyperbolicity constant of the graph G\e (G~e) obtained from the graph G by deleting (contracting) an arbitrary edge e from it. These inequalities allow to obtain other main result, which characterizes in a quantitative way the hyperbolicity of any graph in terms of local hyperbolicity. Finally, we obtain information about the hyperbolicity constant of the line graph L(G) in terms of properties of the graph G. In particular, we prove that a graph G is hyperbolic if and only if L(G) is hyperbolic.
Marzo-Agosto de 2013
2 de agosto de 2013. Salón 031. Departamento de Matemáticas, Cinvestav-IPN
11:00 Hrs.
Aron Simis
Universidade Federal da Paraíba, Brazil.
New constructions of Cremona maps
Resumen: I will discuss two ways of constructing rational maps derived from other rational maps, in a characteristic-free context. The first introduces the Newton complementary dual of a rational map. One main result is that this dual preserves birationality and gives an involutional map of the Cremona group to itself that restricts to the monomial Cremona subgroup and preserves de Jonquiéres maps. The second construction is an iterative process to obtain rational maps in increasing dimension. As an outcome one is able to produce explicit infinite families of Cohen-Macaulay Cremona maps with prescribed dimension, codimension and degree.
12:00 Hrs.
Dino Lorenzini
Distinguished Research Professor of Mathematics, University of Georgia, USA.
On Laplacian of Graphs and Generalizations
Resumen: I will discuss several problems and tools pertaining to the Smith Normal form of the Laplacian of a connected graph, and of matrices closely related to Laplacians. These related matrices appear naturally in arithmetic geometry, and problems in arithmetic geometry have motivated for the past 20 years a purely combinatorial study of these matrices.
12 de agosto de 2013. Auditorio José Ádem, Cinvestav-IPN
11:00 Hrs.
Daniela Ferrero
Texas State University
The power domination problem in graphs
Resumen: Electric power companies need to monitor the state of their networks continually in order to prevent black-outs. One method to accomplish this task is to place Phase Measurement Units (PMUs) at selected network locations. The synchronized readings provided by these PMUs, in conjunction with Kirchoff’s laws, permit to determine the state of the power network at any element of the network. Because of the high cost of a PMU, it is important to minimize the number of PMUs needed to maintain the ability of monitoring the entire system. Since power networks can be modeled by graphs, this problem translates into a graph theory problem: the power domination problem. In spite of the name, the problem differs substantially from traditional graph domination problems in the sense that the domination rule can be iteratively applied, giving a dynamic formulation to the problem. The power domination problem in graph theory is closely related the zero-forcing problem in algebraic graph theory. In this talk we will survey known results and future challenges in the study of the power domination problem.
12:00 Hrs.
Luis David García
Sam Houston State University
Algebraic Geometry of Linear Structural Equation Models
Resumen: Algebra has seen many applications in statistics, but it is only rather recently that computational algebraic geometry has been used to study statistical models and inference problems. This connection is based on the fact that many statistical models are defined either parametrically or implicitly via polynomial equations.
Linear structural equation models (SEMs) are multivariate regression models that relate random variables
of interest via a linear equation system and can be represented by a graph with two types of edges that correspond to non-zero coefficients in the linear equations and correlations among noise terms. These models are used to test and estimate causal relations using a combination of statistical data and qualitative causal assumptions and have been widely applied to genetics, economics, cognitive and social sciences.
A central problem in SEMs is the analysis of identification. Identifiability holds if the coefficients and correlations associated with the edges of the graph can be uniquely recovered from the covariance matrix they define. In this talk we will give a basic introduction to the field of algebraic statistics. We will focus on the algebraic geometry of structural equation models and its applications to the identifiability problem.
13 de marzo de 2013
Dra. María de Luz Gasca Soto
Departamento de Matemáticas, Facultad de Ciencias, UNAM
Las Variantes del Hipercubo: Propiedades Topológicas y Algorítmicas
Resumen: Los modelos de computación en paralelo se dividen en dos clases: las máquinas de memoria compartida y las redes de interconexión.
Éstas últimas se modelan como una gráfica no dirigida G = (V, A), donde V representa el conjunto de procesadores en la red de interconexión y A es el conjunto de ligas (conexiones) entre procesadores.
El Hipercubo Qn ha sido uno de los modelos clásicos, y más exitosos, para las redes de interconexión. En los últimos años han surgido diversas variantes del hipercubo con interesantes propiedades topológicas (como conectividad, simetría, inmersión, hamiltonicidad) que permiten el diseño de algoritmos de enrutamiento y comunicación de complejidad óptima.
En esta plática se presentan tanto las propiedades del Hipercubo como las de algunas de estas variantes, enfatizando las propiedades topológicas y algorítmicas.
Se propone, además, una gráfica 4-regular como modelo para redes de interconexión.
Mayo-Octubre de 2012
17 de octubre de 2012
Dra. Amanda Montejano
Unidad Multidiciplinaria de Docencia e Investigación, Facultad de Ciencias, UNAM-Juriquilla
¿Cómo usar la teoría de números aditiva para resolver problemas en teoría anti-Ramsey?
Resumen: En esta plática hablaremos de la filosofía general de los problemas tipo anti-Ramsey; definiremos algunos parámetros básicos en el área, y plantearemos problemas concretos. Posteriormente presentaremos algunos resultados pertenecientes a la teoría de números aditiva, y explicaremos cómo se pueden usar para resolver los problemas antes descritos.
25 de julio de 2012
Dr. Clemens Huemer
Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya
Cotas para el parámetro de Fiedler para grafos planos – un problema geométrico
Resumen: El parámetro de Fiedler λ2, también conocido como conectividad algebraica, es el segundo autovalor más pequeño de la matriz Laplaciana de un grafo. Estudiamos el valor máximo que puede alcanzar el parámetro de Fiedler entre todos los grafos planos con n vértices y obtenemos que este valor esta entre 2+θ(1/n^2) y 2+O(1/n). Veremos que este problema se puede plantear como un problema geométrico y que esta relacionado con teoremas de separadores para grafos planos así como con un resultado de Spielman y Teng para el parámetro de Fiedler de grafos planos de grado máximo acotado. Las mismas técnicas permiten calcular cotas para el parámetro de Fiedler para otras clases de grafos, como grafos bipartitos planos, grafos outerplanares, grafos de género acotado y grafos que no tienen un grafo completo Kh como menor.
Trabajo conjunto con Lali Barrière, Dieter Mitsche y David Orden.
23 de mayo de 2012
Dra. Mucuy-kak Guevara
Facultad de Ciencias, UNAM
¿Cuándo una digráfica tiene núcleo?
Resumen: Un núcleo es un conjunto de vértices independiente (no hay flechas entre los vértices) y absorbente (todo vértice fuera de él tiene una flecha hacia un vértice en él). Hay digráficas que tienen como que muchos núcleos, pues ellas tienen núcleo y todas sus subdigráficas inducidas también. Estás digráficas son llamadas núcleo perfectas. En esta plática daremos, después de una breve introducción a los núcleos, condiciones suficientes para que una digráfica sea núcleo perfecta a partir de la ayuda de otro concepto más débil que el de núcleo, seminúcleos módulo un conjunto de flechas.
Mayo-Diciembre de 2011
9 de diciembre de 2011
Dr. Jesús Leaños
Unidad Académica de Matemáticas, UAZ
Aditividad del número de cruces en superficies
Resumen: En esta plática probaremos que si G es una gráfica con un 3-corte de aristas minimal F y G1, G2 son las dos componentes (aumentadas) de G - F, entonces cr(G)=cr(G1)+cr(G2).
Esto junto con resultados conocidos implica que el número de cruces de una gráfica en el plano es aditivo sobre cortes de aristas de tamaño n, para n
Por el otro lado, existen contrajemplos para cada n ≥ 4.
22 de noviembre de 2011
Dra. Rita Zuazua
Facultad de Ciencias, UNAM
Problemas de dominación en gráficas
Resumen: En esta plática presentaremos algunas aportaciones a las siguientes dos preguntas:
1) Si se modifica el concepto clásico de dominación en gráficas, ¿qué nuevos problemas aparecen?
2) ¿Cómo se modifica el número de dominación de una gráfica al realizar algún tipo de operación de gráficas?
14 de septiembre de 2011
Dr. Miguel Angel Pizaña
UAM-I
Contracción de aristas en gráficas iteradas de clanes
Resumen: El operador de clanes $K$, transforma una gráfica $G$ en su gráfica de clanes $K(G)$ que es la gráfica de intersección de sus subgraficas completas maximales. Se definen las gráficas iteradas de clanes por medio de $K^{n+1}(G)=K(K^n(G))$. Una de las preguntas centrales en la teoría de gráficas iteradas de clanes es:
Dada una gráfica $G$ ¿qué pasa al aplicar iteradamente el operador de clanes? ¿El número de vertices crece sin cota (i.e. $G$ es clan-divergente) o la sucesión de gráficas iteradas de clanes se estanca o se encicla en algún momento (i.e. $G$ es clan-convergente)?
A lo largo de casi 40 años de estudio se han desarrollado diversas técnicas para responder esta pregunta en distintas situaciones. Sin embargo no se sabe todavía si existe un algoritmo para decidir el comportamiento de las gráficas bajo el operador de clanes. La teoría de gráficas iteradas de clanes ha sido ya aplicada para atacar problemas de enormalización en Gravitación Cuántica de Bucles.
En esta plática, nos concentraremos en el caso de la rango-divergencia (una noción más fuerte que la clan-divergencia), donde recientemente se han encontrado ciertas condiciones para que pueda uno contraer una arista preservando la rango-divergencia.
10 de agosto de 2011
Rafael Villarroel Flores
Área Académica de Matemáticas y Física - UAEH
Gráficas iteradas de clanes y topología
Resumen: Dada G una gráfica simple, la gráfica de clanes K(G) se define como la gráfica de intersección de las subgráficas maximales completas de G. Se definen entonces las gráficas iteradas de clanes de G para n >= 1 como: K^n(G)=K(G) si n=1 y K^n(G)=K^{n-1}(K(G)) si n>1.
Por otro lado, a toda gráfica G se le asocia un complejo simplicial \Delta(G) (y por lo tanto, un espacio topológico) que tiene como caras las subgráficas completas de G. Se dice que las gráficas G_1 y G_2 son homotópicas si sus complejos respectivos \Delta(G_1), \Delta(G_2) lo son.
El estudio del efecto del operador de clanes en la topología de las gráficas inició con la demostración de Prisner, publicada en 1992, de que si la gráfica G es clan-Helly, entonces G y K(G) son homotópicas. En esta plática repasaremos varios resultados relacionando el clan-comportamiento de G con la topología, así como varias conjeturas al respecto.
8 de junio de 2011
Dr. David Flores-Peñaloza
Facultad de Ciencias-UNAM
Número cuasi-heterocromático de árboles generadores planos en posición convexa
Resumen: En esta plática hablaremos de la solución del siguiente problema anti-Ramsey geométrico. Dado un dibujo rectilíneo de una gráfica completa cuyos vértices son n puntos en posición convexa, ¿cuál es el mínimo número de colores con el que se deben colorear sus aristas, de tal forma que en toda coloración con ese número de colores, siempre haya un árbol generador plano que tenga a lo más dos aristas del mismo color?
Mostraremos
1- La solución exacta el problema.
2.- La estructura de toda coloración que usa un color menos y que evita que exista un árbol generador plano "cuasi-heterocromático".
3.-La solución del caso general en donde se se pide la existencia de un árbol generador plano con a lo más k aristas del mismo color.
Trabajo conjunto con J.J Montellano, E. Rivera Campo y R. Zuazua.
11 de mayo de 2011
Dolores Lara
UAM-Azcapotzalco
Emparejamientos de peso mínimo para puntos móviles
Resumen: El problema del emparejamiento euclidiano de peso mínimo es un problema clásico en el área de Teoría de Gráficas y Optimización. Dada una gráfica geométrica completa K, un emparejamiento perfecto M es una subgráfica generadora de K en la que el grado de cada vértice es exactamente uno. Decimos que dos puntos están emparejados si hay una arista entre ellos. El peso de M se define como la suma de las distancias euclidianas entre los puntos emparejados. Dada K, el problema del emparejamiento euclidiano de peso mínimo consiste en encontrar un emparejamiento cuyo peso sea el menor posible.
Existen muchas variantes para este problema, sin embargo, en esta charla presentaremos la primer variante en la que se introduce movimiento. Es decir, estudiaremos el problema cuando los puntos se mueven todos con velocidad constante, y cada uno sobre un rayo distinto. Claramente, bajo este escenario, el emparejamiento de peso mínimo es una función del tiempo. Usando técnicas de programación lineal hemos logrado algunos resultados para esta variante cinética del problema.
Marzo-Diciembre de 2010
07 de diciembre de 2010
Edgar Possani Espinoza
Departamento de Matemáticas, ITAM
Aplicaciones del análisis envolvente de datos para la evaluación de la eficiencia ecológica
Resumen: En esta charla se dará una breve introducción a la técnica del análisis envolvente de datos. El análisis envolvente de datos es una técnica de evaluación de la eficiencia basada en la programación lineal. Se presentará un modelo para la evaluación de proyectos considerando impactos medio ambientales, con ejemplos concretos de su aplicación.
16 de noviembre de 2010
Luis Verde Star
Departamento de Matemáticas, UAM-Iztapalapa
Funciones racionales generalizadas y ecuaciones funcionales
Resumen: A partir de un grupo cíclico P isomorfo a los enteros con la operación de suma, construimos un campo de funciones racionales generalizadas, el cual es un subcampo de las series formales de Laurent generadas por el grupo P. En este contexto algebraico abstracto estudiamos ecuaciones lineales asociadas a un operador de corrimiento modificado L y resolvemos de manera completa las ecuaciones de la forma w(L)f=g. Tomando realizaciones concretas de los elementos de P, tales ecuaciones se convierten en ecuaciones diferenciales, ecuaciones en diferencias, ecuaciones en derivadas fraccionales, y muchos otros tipos de ecuaciones funcionales de interés en diversas areas. Se utiliza solamente álgebra lineal básica.
05 de octubre de 2010
Javier Cano Vila
IIMAS
Vigilando Galerías de Arte Curvilíneas
Resumen: Uno de los problemas clásicos de geometría combinatoria es determinar el número de guardias suficientes y en ocasiones necesarios para vigilar una galería de arte con n paredes. Modelamos la galería se ve modela como un polígono simple (junto con su interior) y llamamos paredes a las aristas. Decimos que un punto p en una galería de arte A ve a otro punto q en A si el segmento pq está totalmente contenido en A. Chvàtal demostró que $\lfloor \frac{n}{3}\rfloor$ guardias son siempre suficientes y en ocasiones necesarios para vigilar cualquier galería con n paredes. Recientemente Karavelas y Tsigaridas propusieron una variante de este problema, en el cuál las paredes en lugar de ser sólo segmentos de recta pueden ser también arcos de curvas convexas. En esta presentación se darán cotas justas para el número de guardias suficientes y necesarios en este tipo de galerías.
14 de septiembre de 2010
Carlos Renteria
Titulo: Por anunciarse
08 de junio de 2010
Fuensanta Aroca
Instituto de Matemáticas, Campus Cuernavaca, UNAM.
Geometría Tropical en Rango Arbitrario
Resumen: La Geometría Tropical Clásica estudia el semianillo tropical: los números reales junto con máximo y suma. Las mismas operaciones están definidas para un grupo abeliano totalmente ordenado. Veremos algunos resultados que se siguen manteniendo y otros que no.
11 de mayo de 2010
Enrique Reyes
Cinvestav-IPN.
Ideales tóricos de gráficas y sus generadores mínimos
Resumen: Sea G = (V, E) una gráfica, con V = {x1 , . . . , xn } y E = {y1 , . . . , ym } los conjuntos de vértices y aristas respectivamente. El ideal tórico PG asociado a G es el núcleo de un morfismo de k-álgebras. En esta plática daremos una caracterización de los binomios primitivos, mínimos, indispensables y fundamentales del ideal PG. También caracterizaremos a las gráficas cuyos ideales tóricos son intersecciones completas y analizaremos las gráficas que son intersecciones completas para toda orientación.
13 de abril de 2010
Rodolfo San Agustín Chi
Facultad de Ciencias, UNAM.
Puntos de Salmon y haces sicigéticos
Resumen: La de Papus es una figura recurrente en las geometrías finitas y combinatorias. La vamos a considerar, esta vez, a partir de lo siguiente: Aún cuando Pascal (ca. 1640) dió la condición para que seis puntos estuviesen en una cónica, de acuerdo a George Salmon, fue Jacob Steiner el primero que dirigió la atención de los geómetras hacia la figura completa que se obtiene al unir seis puntos en una cónica, de todas las maneras posibles. Los trabajos relacionados, además de Pascal y Steiner, también incluyen a Kirkman, Plucker, Cayley, Salmon, Veronese, Cremona, Richmond, Ladd y algunos otros matemáticos durante la segunda mitad del siglo XIX y principios del XX. Dicha figura consta, básicamente, de 95 puntos y 95 rectas distribuidos en diferentes subconfiguraciones del más diverso interés. Su estudio se ha retomado desde finales del siglo XX, junto con el nuevo auge de las configuraciones. El caso de una cónica reducida pero reducible (i.e. dos rectas distintas) en un campo de característica distinta de 2 y 3 se puede estudiar a partir del caso genérico haciendo una especialización en la fibra. En esta reunión plantearemos el problema desde el punto de vista de las configuraciones, tanto para el caso genérico (de Pascal) como para el de Papus y estudiaremos la especialización mencionada anteriormente.
09 de marzo de 2010
Ruy Fabila
Cinvestav, México
Problemas de iluminación con k-módems
Resumen: La pregunta general de problemas de iluminación es el de preguntarse cuántas "lámparas" son necesarias y suficientes para "iluminar" una región del plano en presencia de obstáculos. El trabajo realizado en problemas de iluminación es ya clásico. En esta plática hablamos de una nueva variante que hemos introducido donde ahora en vez de lámparas se usan dispositivos emisores de señales de radio (llamados k-módems) capaces de atravesar un numero preestablecido k de paredes. Se puede pensar que estos módems son puntos de acceso a un red inalámbrica donde se quiere que se tenga accesos a la red desde de cualquier punto de una región en presencia de obstáculos. Mostramos los avances a la fecha en esta nueva familia de problemas.
Febrero-Julio de 2009
10 de febrero de 2009
Gelasio Salazar
Instituto de Física, Universidad Autónoma de San Luis Potosí
El problema de Turán de la fábrica de ladrillos
10 de marzo de 2009
Ernesto Vallejo
Instituto de Matemáticas Morelia, Universidad Nacional Autónoma de México
La bi-álgebra de permutaciones
14 de abril de 2009
Javier Elizondo Huerta
Instituto de Matemáticas, Universidad Nacional Autónoma de México
Estructuras reales en variedades tóricas
12 de mayo de 2009
Rodolfo San Agustín Chi
Facultad de Ciencias, Universidad Nacional Autónoma de México
Diagramas en categorías de espacios parcialmente lineales de orden dos
9 de junio de 2009
Pablo Suárez-Serrato
Centro de Investigación en Matemáticas, A .C.
Descomposiciones Kaehler para grupos de presentación finita
14 de julio de 2009
Itnuit Janovitz Freireich
Centro de Investigación y Estudios Avanzados del IPN
Avances en métodos de resolución polinomial usando herramientas tropicales