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 *P _{n-2}* and

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 *P _{n}* say that his type of order is convergent to the function

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 R ^{3}*

**Abstract: **We consider sets *L = {l _{1}, ..., l_{n}}* of

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

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.

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.

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*