Discrete Geometry & Combinatorics Seminar: Winter 2014
← Back to Current 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
Paddy Bartlett | February 5
- 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.