## Discrete Geometry & Combinatorics Seminar

### Winter 2014 Schedule

#### An Alternative to the Shapley-Snow Algorithm for Completely Solving Matrix Games

Kyle Chapman | January 22

• Matrix games can often be very large, which isn't a problem if our goal is simply to find one solution, as the simplex algorithm finds one solution quickly. If we want to find the entire solution set, however, we need to use a different algorithm, known as Shapley-Snow algorithm. This algorithm has a very large run time. The talk will present an alternative which uses the one solution given by the simplex algorithm to simplify the computations. The talk will briefly describe the definitions for matrix games and their solutions along with each algorithm involved.

#### An Introduction to Thurston's Shapes of Polyhedra

Arielle Leitner | January 29

• In 1998, Thurston published his seminal paper "Shapes of Polyhedra and Triangulations of the Sphere". In this talk, I will try to give an introduction to some of the ideas in the paper. A good portion of the talk will be spent computing a simpler example.

#### NP-Completeness and Partial Latin Squares

• 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.

#### Hankel Transforms of Orthogonal Polynomials via Riordan Arrays

Michael Dougherty | February 12

• The Hankel transform is a complicated map between integer sequences using large determinants of matrices. Perhaps surprisingly, it produces several elegant results when applied to certain families of sequences. This has led to the application of the Hankel transform to sequences of orthogonal polynomials, and Riordan arrays provide the necessary machinery to understand the result.

In this talk, we will discuss the interplay between these tools and give a (rather nice!) formula for the specific case of the Legendre polynomials. No background in any of the above is needed.

#### Continued Fraction Tricks

Jon McCammond | February 19

• Most of us have seen amazing continued fractions that miraculously converge to unlikely values. In this talk I will take you behind the curtain and show you some of the tricks involved. If all goes well, by the end of the talk many of the various continued fraction evaluations will seem less amazing and you will feel empowered for go forth and create some of your own.

#### Error Correcting Codes, Sphere Packings, and Simple Groups

Ben Coté | February 26

• I will talk about the connection between the three things listed in the title. The talk will be accessible, mainly focusing on the history and the big picture.