Remainder: Computational geometry seminar 19-05-2016
Title: Rainbow matchings in $r$-partite graph structures Speaker: Pilar Cano Universitat Politècnica de Catalunya and Carleton University (Canadá) Thursday, May 19, 2016, 13:15-14:15 Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor -2)
- https://mat.upc.edu/ca/activitats/remainder-computational-geometry-seminar-19-05-2016
- Remainder: Computational geometry seminar 19-05-2016
- 2016-05-19T13:15:00+02:00
- 2016-05-19T14:15:00+02:00
- Title: Rainbow matchings in $r$-partite graph structures Speaker: Pilar Cano Universitat Politècnica de Catalunya and Carleton University (Canadá) Thursday, May 19, 2016, 13:15-14:15 Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor -2)
19/05/2016 de 13:15 a 14:15 (Europe/Madrid / UTC200)
Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor -2)
Abstract: A rainbow matching in an edge colored hypergraph is a matching such that each pair of its edges have distinct colors.
Brualdi, Ryser and Stein conjectured the existence of a partial $n-1$ Latin transversal in a Latin square $n$-matrix.
This problem can be translated into finding a rainbow matching in a complete bipartite graph. We extend the result of Erd\H{o}s and Spencer on the existence of rainbow matchings in the complete bipartite graph $K_{n,n}$ to complete $r$-partite $r$-uniform graphs, complete bipartite graphs with repeated edges, and $d$-regular bipartite graphs minus a matching. The results use the Lopsided version of the Local Lovász Lemma.
Activities are regularly announced at http://www-ma2.upc.edu/dccg/upc-seminar-on-computational-geometry
Comparteix: