Evènement pour le groupe GT Graphes et Applications

Date 2011-01-21  14:00-15:00
TitreRainbow matchings: existence and counting 
RésuméGiven an edge coloring of a graph, a rainbow matching is a matching where all the edges have different color. In particular we focus on the case when the graph is the complete bipartite graph K(n,n). This problem is analogous to find a latin transversal in integer matrices. A result from Erdos and Spencer (1988) states that if no color appears more than n/4e times then the coloring admits a rainbow matching. In this talk we will show some existence and enumeration results subject to these type of constraints. The Lovasz Local Lemma will be used as a main tool in the sense of Poisson Paradigm. Random models of colorings will be introduced and discussed.  
LieuSalle 178 
OrateurGuillem Perarnau  
UrlUPC, Barcelona 

Aucun document lié à cet événement.

Retour à l'index