Math-Sci Seminar

Speaker: Manouchehr Zaker (Department of Mathematics Institute for
		Advanced Studies in Basic Sciences, Zanjan - Iran)

Title: Transversals in Partial Latin Squares and Rainbow Matchings

Date: Thu 7 Sep, 2006
Time: 16:45
Place: Science Building, Room Z42

Abstract:

In a partial Latin square (PLS) P of order n, a set T of distinct
entries such that no two of which are in a same row or column is
called a transversal.

By the size of T we mean the number of its entries. There are many
famous unsolved problems related to existence of transversals in
Latin squares. We first report some of these problems.

Next we consider the problem of determining the maximum size of a
transversal in PLS's. We show that this problem is NP-hard even for
a special family of sparse PLS's, i.e. duplexes. A duplex D is an
array of order n (on 2n entries) where each row and column consists
of exactly two entries and any entry appears exactly twice in D.

Next, generalizing the concept of transversal, we are led to
introduce concept of rainbow matchings in edge coloring of graphs.
We obtain first some polynomial time results and then show some
applications in determining independence number of graphs and
existence of independent paths between some pair of source and
target vertices.

Please visit http://home.ku.edu.tr/~sci-math for a schedule of
upcoming Science -Math seminars at Koc University.