TACO
Afternoons on Algebra, Combinatorics and Optimization
The Department of Mathematics, Cinvestav-IPN invites you to the Afternoons on Algebra, Combinatorics and Optimization. This symposium is held on the second Wednesday of each month at 4:00 p.m. at the Auditorium José Adem, Cinvestav-IPN.
Organizing Committee:
Ruy Fabila Monroy
ruyfabila [@] math.cinvestav.edu.mx
September 18, 2018. Auditorium José Ádem, Cinvestav-IPN
16:00 Hrs.
Fabian Klute
Technische Universität Wien, Austria
Bounded cliquewidth of strict outerconfluent drawings
Abstract: 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.
October 5, 2017. Auditorium José Ádem, Cinvestav-IPN
15:00 Hrs.
Irene Parada
Institute for Software Technology. University of Technology, Graz, Austria
A superlineal lower bound for the number of 5-holes
Abstract .
August 15, 2017. Auditorium José Ádem, Cinvestav-IPN
15:00 Hrs.
Cristina Dalfó
BarcelonaTech
Characterizing identifying codes in a digraph or graph from its spectrum
Abstract: 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.
July 20, 2017. Auditorium José Ádem, Cinvestav-IPN
15:00 Hrs.
Frank Duque
Institute of Mathematics, University of Antioquia, Medellín, Colombia
Hexagonal systems with extreme topological indices
Abstract: .
March 16, 2017. Auditorium José Ádem, Cinvestav-IPN
16:00 Hrs.
Josh Tobin
University of California San Diego
Four Conjectures in Spectral Graph Theory
Abstract: 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.
March 2, 2017. Auditorium 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.
January 26, 2017. Auditorium José Ádem, Cinvestav-IPN
15:00 Hrs.
Luis Evaristo Caraballo de la Cruz
Universidad de Sevilla
The resilience of a synchronized communication system
Abstract: 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.
December 18, 2014. Auditorium José Ádem, Cinvestav-IPN
15:00 Hrs.
Alfredo Hubard
GEOMETRICA
INRIA Sophia-Antipolis
Limits of order types
Abstract: The order type is a fundamental invariant in combinatorial and computational geometry, dedicated to studying dependencies, related and convex of points’ sets; without express points by their coordinates.
Given a sequence of sets of points Pn say that his type of order is convergent to the function l if for any χ order, the probability of k random points Pn are kind of χ order, converges to the value l(χ) when n goes to infinity.
This definition is completely analogous to that of dense charts limit graph theory.
We use this context to reformulate the classical problem of Sylvester: what is the probability that k points form the vertices of a convex polygon. In version n of the problem studied, the case k=4 is the number of junction of the complete graph and give new lower bounds for k=5 and k=6 using semi final optimization on the algebra of flags of order types.
On the other hand, we will show to what extent the limits of order types can be represented by measures in the plane.
Joint work with X Goaoc. J. Volec, R. de Joannis de Verclos y J.S. Sereni.
November 5, 2014. Auditorium José Ádem, Cinvestav-IPN
15:00 Hrs.
Frank Duque
Department of Mathematics, Cinvestav-IPN
Upper bounds for the lighting problem with k-modems
Abstract: Whether at home, school, shopping center, among others. Usually it requires a wireless connection using modems. Variables such as the size of the establishment, the walls on it, and the power of the modems, may take several modems need to cover the entire property with a good wireless signal. We define k modem to a wireless device capable of crossing k walls without losing its good sign. The problem of finding the minimum number of k-modems required to cover a region, is known, in computational geometry, as the problem of k-modem lighting. Polygons and arrangements of disjoint segments are two of the most common instances of this problem. In this talk, we present new bounds and asymptotically optimal for these cases of the problem.
September 11, 2014. Auditorium 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
Abstract: 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 di erent order types that can be obtained as cross-sections of L is O (n9), and that this bound is tight.
April 2, 2014. Auditórium José Ádem, Cinvestav-IPN
15:30 Hrs.
Walter Carballosa Torres
Universidad Autónoma de Guerrero
Invariance of the Gromov hyperbolicity in graphs under transformations
Abstract: 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.
August 2, 2013. Room 031, Department of Mathematics, Cinvestav-IPN
11:00 Hrs.
Aron Simis
Universidade Federal da Paraíba, Brazil.
New constructions of Cremona maps
Abstract: 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
Abstract: 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.
August 12, 2013, Auditorium José Ádem, Cinvestav-IPN
11:00 Hrs.
Daniela Ferrero
Texas State University
The power domination problem in graphs
Abstract: 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
Abstract: 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.
March 13, 2013
Dra. María de Luz Gasca Soto
Faculty of Science, UNAM
Variants of the Hypercube: Topological and algorithmic properties
October 17, 2012
Dra. Amanda Montejano
Multidisciplinary Research and Education Department of the Faculty of Science, UNAM-Juriquilla
How to use additive number theory to solve problems in anti-Ramsey theory?
July 25, 2012
Dr. Clemens Huemer
Departament of Applied Mathematics IV, BarcelonaTech
Dimensions for Fiedler parameter for planar graphs. A geometric problem
May 23, 2012
Dra. Mucuy-kak Guevara
Faculty of Science, UNAM
When a digraph has kernel?
August 10, 2011
Dr. Rafael Villarroel Flores
Academic Area of Mathematics and Physics, UAEH
Iterated Clique Graphs and Topology
Abstract: Given a simple graph G, the clique graph K (G) is defined as the intersection graph of maximal complete subgraphs of G, are defined then iterated clique graphs of G for n > = 1 as: K^n(G)=K(G) if n=1 and K^n(G)=K^{n-1}(K(G)) if n>1.
On the other hand, the whole graph G is associated with a simplicial complex \Delta(G) (and therefore a topological space) whose faces complete subgraphs G. It is said that the graphs G_1 and G_2 are homotopic if their respective complex \Delta(G_1), \Delta(G_2) are.
The study of the effect of the operator of clans in the topology of the graphs began with the demonstration of Prisner, published in 1992 that if the graph G is clique-Helly, then G and K (G) are homotopic. This talk will review several results relating the clique-behavior of G with the topology as well as several conjectures about.
June 8, 2011
Dr. David Flores-Peñaloza
Faculty of Sciences, UNAM
Number of quasi-heterochromatic spanning trees in convex position flat
Abstract: This talk will discuss the solution of the following anti-Ramsey problem geometry. Given a rectilinear drawing of a complete graph whose vertices are n points in convex position, what is the minimum number of colors that should color their edges, so that any color for that number of colors, there is always a plane spanning tree has at most two edges of the same color?
Show
1 - The exact solution of the problem.
2 .- The whole structure of color using a color less and to avoid a plane spanning tree "near-heterochromatic".
3.-The solution of the general case which calls for the existence of a plane spanning tree with at most k edges of the same color.
Working together with J.J Montellano, E. Campo and R. Rivera Zuazua.
May 11, 2011
Dolores Lara
UAM-Azcapotzalco
Minimum weight matching of moving dots
Abstract: The problem of Euclidean minimum weight matching is a classic problem in the area of graph theory and optimization. Given a complete geometric graph K, a perfect matching M is generating a subgraph K in which the degree of each vertex is exactly one. We say that two points are paired if there is an edge between them. The weight of M is defined as the sum of the Euclidean distances between the points matched. Given K, the problem of Euclidean minimum weight matching is to find a matching whose weight is minimized.
There are many variations to this problem, however, this talk will present the first variant in which motion is introduced. That is, study the problem when the points all move with constant speed, each on a different beam. Clearly, under this scenario, the minimum weight matching is a function of time. Using linear programming techniques have achieved some results for this variant kinetic problem.
March-December 2010
December 7, 2010
Edgar Possani Espinoza
Department of Mathematics, ITAM
Applications of data envelopment analysis for assessing eco-efficiency
Abstract: This talk will give a brief introduction to the technique of data envelopment analysis. Data envelopment analysis is a technique for evaluating the efficiency based on linear programming. There will be a model for project evaluation, considering environmental impacts with concrete examples of its application.
November 16, 2010
Luis Verde Star
Department of Mathematics, UAM-Iztapalapa
Generalized rational functions and functional equations
Abstract: From a cyclic group P isomorphic to the integers with addition operation, we build a field of functions, generalized rational, which is a subfield of formal Laurent series generated by the group P. In this context, abstract algebra, we study linear equations associated with a modified shift operator L and resolve in full the equations of the form w (L) f = g. Taking concrete realizations of the elements of P, these equations become differential equations, difference equations, fractional equations, and many other types of functional equations of interest in various areas. It uses only basic linear algebra.
October 5, 2010
Javier Cano Vila
IIMAS, UNAM
Guarding curvilinear art galleries
Abstract: One of the classic problems of combinatorial geometry is to determine the number of guards sufficient and sometimes necessary to guard an art gallery with n walls. We model the gallery is modeled as a simple polygon (with it). We call edges walls. We say that a point p in an art gallery A, sees another point q in A, if the segment pq is completely contained in A. Chvàtal proved that $\lfloor \frac{n}{3}\rfloor$ guards are always sufficient and sometimes necessary to monitor any gallery with n walls. Karavelas and Tsigaridas recently proposed a variant of this problem, in which the walls rather than just line segments can also be arcs of convex curves. This presentation will give fair levels for the number of guards sufficient and necessary in these galleries.
September 14, 2010 CANCELED
Carlos Renteria
TBA
June 8, 2010
Fuensanta Aroca
Institute of Mathematics, Campus Cuernavaca, UNAM
Arbitrary Range Tropical Geometry
Abstract: Tropical Classical Geometry studies the tropical half-ring: the real numbers with maximum and sum. These operations are defined for a totally ordered abelian group. We will see some results that are still maintained and some not.
May 11, 2010
Enrique Reyes
Cinvestav-IPN
Toric ideals of graphs and their minimal generators
Abstract: Let G = (V, E) a graph with V = {x 1,. . . , X n} and E = {y1,. . . , ym} the sets of vertices and edges respectively. The toric ideal PG associated to G is the kernel of a morphism of k-algebras. This talk will give a characterization of primitive pairs, minimum, essential and fundamental ideal of PG. Also characterize the graphs whose toric ideals are complete intersections and analyze the graphs that are complete intersections for any guidance.
April 13, 2010
Rodolfo San Agustín Chi
Faculty of Sciences, UNAM
Salmon points and sicigetic beams
Abstract: The Papus is a recurring figure in finite and combinatorial geometries. We will consider, this time from the following: Although Pascal (ca. 1640) gave the condition that six points were in a conic, according to George Salmon; Jacob Steiner was the first that directed the attention of geometers to the entire figure that is obtained by combining six points in a conic, in every way possible. Related work, as well as Pascal Steiner, Kirkman also include, Plucker, Cayley, Salmon, Veronese, Cremona, Richmond, Ladd and some other mathematicians in the second half of the nineteenth and early twentieth centuries. This figure basically consists of 95 points and 95 lines distributed in different subsets of the most diverse interests. Their study has been retrieved from the late twentieth century, along with the resurgence of the settings. The case of a conical reduced but reducible (ie two different lines) in a field of characteristic different from 2 and 3 can be studied from the generic case majoring in fiber. This meeting will raise the problem from the standpoint of the settings for both the generic case (Pascal) to that of Papus and study specialization mentioned above.
March 9, 2010
Ruy Fabila
Cinvestav-IPN
Lighting problems with k-modems
Abstract: The general question of lighting problems is to ask how many "lamps" are necessary and sufficient to "light up" a region of the plane in the presence of obstacles. The work on problems of lighting is classic. In this talk we talk about a new variant that we have introduced which now instead of lamps, use radio signals emitting devices (called k-modems) capable of crossing a predetermined number k of walls. You might think that these modems are points of access to a wireless network where you want to have access to the network from any point of a region in the presence of obstacles. We show progress to date in this new family of problems.
February-July 2009
July 14, 2009
Itnuit Janovitz Freireich
Cinvestav-IPN
Advances in methods of polynomial resolution using tropical tools
June 9, 2009
Pablo Suárez-Serrato
CIMAT
Kaehler Decompositions for finitely presented groups
May 12, 2009 CANCELED
Rodolfo San Agustín Chi
Faculty of Sciences, UNAM
Diagrams in partially linear space categories of order two
April 14, 2009
Javier Elizondo Huerta
Institute of Mathematics, UNAM
Real structures in toric varieties
March 10, 2009
Ernesto Vallejo
Institute of Mathematics, Campus Morelia, UNAM
The bi-algebra of permutations
February 10, 2009
Gelasio Salazar
Institute of Physics, Universidad Autónoma de San Luis Potosí
Turán's brick factory problem