Noviembre 2019

Ponente: Jon Wilson
Institución: IM-UNAM

de 12:00 a 13:00
Dónde Auditorio "Alfonso Nápoles Gándara"

Introduced by Dupont and Palesi, quasi-cluster algebras are cluster structures arsing from ‘triangulated’ non-orientable surfaces. Specifically, each cluster variable corresponds to the (laminated) lambda length of an arc on the surface. Fixing an initial triangulation, and therefore an initial set of cluster variables, one can express any subsequent cluster variable in terms of the initial ones. In this talk we will investigate the behaviour of these expressions. In particular, following the work of Musiker, Schiffler and Williams we will assign certain graphs to arcs on the surface. In doing so, we find expansion formulae of the cluster variables in terms of perfect matchings of these graphs. The talk is for a general audience -- no prior knowledge of cluster theory will be assumed.

Ponente: Mika Olsen
Institución: UAM-Cuajimalpa

12/11/2019  de 12:00 a 13:00
Dónde Auditorio "Alfonso Nápoles Gándara"

Cuentan que el estudio de coloraciones en teoría de las gráficas inició hace unos 200 años con el problema de los 4 colores. Hoy en día, las coloraciones son uno de los tópicos mas estudiados tanto por interés teórico como por la cantidad de aplicaciones que tienen y se estudian tanto coloraciones de vértices, coloraciones de aristas como coloraciones de vértices y artistas. Una coloración de los vértices de una gráfica induce una partición del conjunto de vértices en clases cromáticas. Una coloración es *propia* si no hay aristas entre vértices del mismo color, es decir, las clases cromáticas son conjuntos independientes.

El *número cromático* de una gráfica G es el mínimo número de colores de una coloración propia de G. El concepto de coloración propia se puede generalizar a otro tipo de coloraciones sólo cambiando las condiciones sobre las clases cromáticas. Estas generalizaciones a veces han sido impulsadas por interés teórico y a veces por alguna aplicación particular, o ambos. En esta plática voy a dar una breve introducción al número cromático, sus aplicaciones y algunas de sus generalizaciones. Voy a revisar dos coloraciones que surgen de problemas que actualmente tienen mucho interés. El número cromático de empaquetamiento tiene aplicaciones en la asignación de radio frecuencias. Una coloración de los vértices de una gráfica es de *empaquetamiento* si los colores son números naturales y dos vértices del color i están a distancia mayor que i. El *número cromático de empaquetamiento* es el mínimo número de colores de una coloración de empaquetamiento.

Una coloración de las aristas de una gráfica es *arco iris* si entre cualquier para de vértices hay una trayectoria arco iris, es decir, una trayectoria cuyas aristas no repiten color. La *conexidad arco iris* se define como el mínimo número de colores de una coloración arco iris y tiene aplicaciones en el área de seguridad cibernética.

Finalmente, voy a presentar resultados para la conexidad arco iris y para el número cromático de empaquetamiento de una (k,g)-jaulita.

Las jaulas tienen propiedades estructurales que resultan convenientes en redes de comunicación y las jaulitas tienen propiedades estructurales heredadas de geometrías finitas.


Ponente: Matthieu Roy
Institución: LAAS-CNRS, Francia

05/11/2019  de 12:00 a 13:00
Dónde Auditorio "Alfonso Nápoles Gándara"

The topological structure of complex networks has fascinated researchers for several decades, resulting in the discovery of many universal properties and reoccurring characteristics of different kinds of networks. However, much less is known today about the network dynamics: indeed, complex networks in reality are not static, but rather dynamically evolve over time.

Our work is motivated by the empirical observation that network evolution patterns seem far from random, but exhibit structure. Moreover, the specific patterns appear to depend on the network type, contradicting the existence of a “one fits it all” model. However, we still lack observables to quantify these intuitions, as well as metrics to compare graph evolutions. Such observables and metrics are needed for extrapolating or predicting evolutions, as well as for interpolating graph evolutions.

To explore the many faces of graph dynamics and to quantify temporal changes, we propose to build upon the concept of centrality, a measure of node importance in a network. In particular, we introduce the notion of centrality distance, a natural similarity measure for two graphs which depends on a given centrality, characterizing the graph type. Intuitively, centrality distances reflect the extent to which node roles are different or, in case of dynamic graphs, have changed over time, between two graphs.

References :
Y. A. Pignolet, M. Roy, S. Schmid and G. Trédan. « The many faces of graph dynamics ». In : Journal of Statistical Mechanics : Theory and Experiment 2017 (juin 2017). https://hal.archives-
M. Roy, S. Schmid and G. Trédan. « Modeling and Measuring Graph Similarity : The Case for Centrality Distance ». In : FOMC 2014, 10th ACM International Workshop on Foundations of Mobile Computing.

¿Quien está en línea?

Tenemos 77 visitantes y ningun miembro en Línea

Go to top