18.304 Undergraduate Seminar in Discrete Mathematics
Instructor: Csaba D. Tóth
2006 Fall, MWF 12
Room 2-102

Requirements: 
Everyone should give four presentations. Please, sign up for your presentaions at least a week ahead;
and send me a title and a teaser (a few paragraph summary) before your talk.
Everyone should hand in a 10 page term paper, which may be a summary of your favourite presentation.
The first draft should be ready no later than November 22.

Schedule of talks:

DATE	SPEAKER	TITLE
Sep 6, W		First Class.
Sep 8, F	Jakub	Contour recognition filter
Sep 11, M	Jorge and Jon	Finite element analysis
Sep 13, W	Travis	Coloring algorithms for planar graphs
Sep 15, F	Jakub	Delaunay triangulations with applications in solving PDEs
Sep 18, M	Frances	Regression analysis with binary variable
Sep 20, W	Zheng and Brad	Codes and error correcting codes
Sep 22, F	John talk cancelled	Combinatorics problems
Sep 25, M	Student Holiday — no classes.
Sep 27, W	Cristina	Irrational and transcendental numbers
Sep 29, F	Travis	Planar graphs are 5-colorable

Oct 2, M	Yuncheng	Catalan numbers and their generating function
Oct 4, W	Jon	Cellular automata
Oct 6, F	Jakub	Elliptic curve cryptography
Oct 9, M	Columbus Day—Vacation.
Oct 11, W	Travis	One dimensional random walks
Oct 13, F	Brad	Turing machines
Oct 16, M	Jorge	Finite symmetry groups
Oct 18, W	Zack	Derangements and the Ménage problem
Oct 20, F	Frances	Heteroskedasticity in the linear regression model
Oct 23, M	Jakub	Triangular meshes with few different edge lengths
Oct 25, W	Zack	Hamiltonian graphs and Venn diagrams
Oct 27, F	Yuncheng	Catalan numbers—two bijective proofs
Oct 30, M	Cristina talk postponed to Nov 13	Generalized tic tac toe Unit area triangles

Nov 1, W	Brad and Zheng	Notions of infinity
Nov 3, F	Jon	Tikhonov regularization on least squares for inverse problems
Nov 6, M	Jorge	Finite reflection groups
Nov 8, W	Yuncheng	Planar graphs are 5-colorable
Nov 10, F	Veteran’s Day—Holiday.
Nov 13, M	Cristina	Generalized tic tac toe
Nov 15, W	Travis	Markov Chains
Nov 17, F	Zheng
Nov 20, M	Yuncheng	A 2nd proof for 5-coloring, and bijections for Dyck paths
Nov 22, W	Matt	Voronoi diagrams
Nov 24, F	Thanksgiving Vacation.
Nov 27, M	Jorge	Generators and relations for Coxeter groups
Nov 29, W	Frances	Bayesian static games with incomplete information

Dec 1, F	Cristina	Polynomial time reductions to the k-click and Hamiltonian path problems
Dec 4, M	Zack	Frustration solitaire
Dec 6, W	Matt	Convex hulls
Dec 8, F	Brad	Fermat's Little Theorem
Dec 11, M	Frances	Perfect Bayesian equilibrium in extensive form games
Dec 13, W	Matt	Polygon Triangulation and the Art Gallery problem

Suggested topics:

Any chapter from these books (copies available from me or the library):

• M. Aigner and G. M. Ziegler: Proofs from the BOOK, Springer, 2004.
• M. de Berg, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Application, Springer, 2000.
• L. Lovász,  J. Pelikán, and K. Vesztergombi: Discrete Mathematics: Elementary and Beyond, Springer, 2003.

Any article from these journals (available online, paper copies from the library):

• Journal of Combinatorial Theory (Ser A), (Ser B)
• Graphs and Combinatorics
• Discrete Mathematics
• Discrete and Computational Geometry
• SIAM Journal on Discrete Mathematics

Any research paper from these conference proceedings (available online):

• Annual ACM-SIAM Sympos. on Discrete Algorithms
• Canadian Conference on Computational Geometry

Book the time slots for your talks at class or by e-mail: toth@math.mit.edu.