|
Evènement pour le groupe GT Graphes et Applications
Date | 2011-01-21 14:00-15:00 |
Titre | Rainbow 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. |
Lieu | Salle 178 |
Orateur | Guillem Perarnau |
Url | UPC, Barcelona |
Aucun document lié à cet événement. RetourRetour à l'index
| |