18.304 Undergraduate Seminar in Discrete Mathematics
Instructor: Csaba D. Tóth
2007 Spring, MWF 12
Room 2-132

Requirements: 
Everyone should give four presentations on discrete mathematics.
Please, sign up for your presentaions at least a week in advance;
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 of the term paper should be handed in no later than April 18 23, 2007, Monday.

Suggested topics:

Any chapter from these books (copies available from 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

Schedule of talks:

DATE	SPEAKER	TITLE
Feb 7, W		First Class.
Feb 9, F		A load balancing game
Feb 12, M	Joshua	Cryptography and cryptoanalysis
Feb 14, W	YinFeng	The price of future information
Feb 16, F	Manuel	Pattern avoidance
Feb 19, M	Presidents Day—Holiday
Feb 20, T	Wajahat	Survivable WDM networks
Feb 21, W	Colin	Inversive geometry
Feb 23, F	Craig	NP-completeness
Feb 26, M	Nicholas	Riffle shuffle—introduction
Feb 28, W	Anjani	Distinct triangle areas

Mar 2, F	Joshua	Primality testing
Mar 5, M	Sergio	Lines in the plane and decompositions of graphs
Mar 7, W	Manuel	Combinatorics problems from Stanford
Mar 9,  F	Manuel	Bar visibility representation of triangulations
Mar 12, M	YinFeng	Graph theory problems from Berkeley
Mar 14, W	Anjani	Introduction to Ramsey Theory
Mar 16, F	Wajahat	Capacity of wireless networks
Mar 19, M	Sergio	Turán's Theorem on graphs with forbidden subgraphs
Mar 21, W	Manuel	Coalescent theory: Markov chains in human genetics
Mar 23, F	Wajahat	Throughput bounds in mobile wireless networks
Mar 26-30,	Spring Break

Apr 2, M	YinFeng	Lattice geometry
Apr 4, W	Manuel	talk postponed
Apr 6, F	Joshua	Proofs on primes
Apr 9, M	Sergio	Erdős-Hajnal properties
Apr 11, W	Craig	Graph Theory problems from ETHZ
Apr 13, F	YinFeng	Combinatorial game theory
Apr 16, M	Patriots Day—Holiday
Apr 18, W	Manuel	Circular words avoiding patterns
Apr 20, F	Anjani	Stable matchings
Apr 23, M	Colin	Colliding balls and π
Apr 25, W	Craig	Prime distributions
Apr 27, F	Wajahat	Achieving 100% throughput in an input-queued switch
Apr  30, M	Manuel	Probability problems in dice games

May 2, W	Nick	Two-player zero-sum games
May 4, F	Sergio	Zero-error capacity and Ramsey theory
May 7, M	Anjani	Designs and codes
May 9, W	Craig	Diophantine equations
May 11, F	Wajahat	Maximum matchings in bipartite graphs
May 16, W	Colin	P-adic and G-adic numbers
May 17, R	Nick	Riffle shuffle and strong uniform stopping rules

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