Vés al contingut (premeu Retorn)

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)

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)

Quan
19/05/2016 de 13:15 a 14:15
On
Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor -2)
URL de l'esdeveniment
Lloc web relacionat
Afegeix un esdeveniment al calendari
iCal

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