Undergraduate Seminar in Discrete Mathematics (18.204)

Spring 2018

Instructor: Thomas McConville
Office: 2-238A
Office Hours: Email me!
Classes: MWF at 1:05-1:55
Room: 2-132

Syllabus
Topics for first talk
Guidelines for talks
Guidelines for the final paper

Midterm

Follow these instructions and read Three-rowed CHOMP by Doron Zeilberger (source)

Writing discussion

Follow these instructions and read Rental Harmony by Francis Su

Schedule

First draft due
Date Name Title
Feb 9 Thomas Chip-firing games on graphs
Feb 12 Bassil
Elizabeth
Stable matching
The Friendship Theorem
Feb 14 Uma
Henry
The Ballot Theorem
Art Gallery Problem
Feb 16 Steven
Robert Z
Arrow's Impossibility Theorem
Latin squares
Feb 20 Robert A
Fernando
Sperner's Lemma
Top-to-random shuffling
Feb 21 Brandon
Caroline
Erdos-Szekeres
Euler's pentagonal number theorem
Feb 23 William
John
Squaring the square
The Perron-Frobenius Theorem
Feb 26 Carly
Catherine
Hall's Marriage Theorem
The Hex Game
Feb 28 Varun Cayley's formula
Mar 2 Thomas The associahedron
Mar 5 Bassil Inherent ambiguity and transcendence
Mar 7 Elizabeth The Grone-Merris-Bai Theorem
Mar 9 Uma The hook length formula
Mar 12 Henry The Hirsch conjecture
Mar 14 Steven Piercing numbers and voting theory
Mar 16 Robert Z Rook polynomials
Mar 19 Robert A Erdos-Renyi graphs
Mar 21 Fernando Spectral analysis of random-to-random shuffling
Mar 23 Brandon An extension of Schensted's theorem
Apr 2 Caroline Partitions with k crossings
Apr 4 William Total Positivity
Apr 6 John Expectation Maximization
Apr 9 Carly Symmetric Venn diagrams and chain decompositions
Apr 11 Catherine Tron
Apr 13 Varun Enumeration of binary de Bruijn sequences
Apr 16 Patriots Day - no class
Apr 18 Thomas
Midterm due
Writing discussion day
Apr 20 Thomas The Laurent Phenomenon
Apr 23 Bassil
Elizabeth
SHA-1
Graph sparsification
Apr 25 Uma
Henry
Burrows-Wheeler transform
Transportation Polytopes
Apr 27 Steven Borda Condorcet revisited
Apr 30 Robert A Barabasi-Albert random graphs
May 2 Brandon
Caroline
Sulzgruber insertion
Statistics on noncrossing partitions
May 4 William
John
The Universal Approximation Theorem
Lindstrom-Gessel-Viennot Lemma
May 7 Carly
Catherine
Aztec Diamond Theorem
Cops and Robbers on graphs
May 9 Peer review
May 11 CANCELLED
May 14 Varun
Robert Z
3D domino tilings
Rook polynomials and chromatic numbers
May 16
Term paper due!
Fernando Frieze patterns