Discrete Geometry Seminar: NP-Completeness and Partial Latin Squares

Event Date: 

Wednesday, February 5, 2014 - 2:00pm to 3:00pm

Event Location: 

  • 4607B South Hall

Event Contact: 

Michael Dougherty

Email: dougherty@math.ucsb.edu

Speaker: Paddy Bartlett

Abstract: A Latin square is a nxn array of symbols {1...n}, such that there are no repetitions in any row or column; a partial Latin square is such an array where we let some of the entries in our array be blank. Filling in the blanks in a partial Latin square so that no repetitions are created in its rows and columns is a mathematical puzzle popularized by Sudoku grids and the like.

In this talk, we will describe why the task of completing a partial Latin square is NP-complete, via results of Holyer and Colbourn. If there is time, we will mention some open problems related to an extension of the talk's material.

This talk will not assume prior familiarity with either NP-completeness or Latin squares.