18.204, Undergraduate Seminar in Discrete Mathematics
Meeting time: Tuesday/Thursday 11-12:30 in 4-257
Office hours: Tuesday 9-11am in 2-143 (or email me for an appointment -- in particular, this time will also be used for practice presentations during the first month of the semester)
Important dates:
1) Sign up for a date for your 30-minute chalk talk as well as a practice talk via the Google Sheet(s) I email you by September 15th.
You don't need a finalized topic by this point, but please claim a topic by writing into the Google Sheet at least one week before your talk (or 2 days before for those presenting the week of September 22nd). If you want to give a talk on a topic which is not from the list below, please confirm it with me before entering it into the Google Sheet. Repeat topics might be OK on a case-by-case basis; contact me if you want to repeat a topic.
2) You must reach out to me with at least one potential final paper topic by October 8th
3) We will discuss and finalize your paper topic by October 15th
4) Sign up for dates for your two 20-minute talks via the Google Sheet(s) I email you by October 20th. These will be on the same topic as your final paper.
5) The first draft of the final paper is due on November 5th
6) The second draft of the final paper is due on November 17th
7) The final paper is due on December 10th
Potential presentation/paper topics:
These are at varying levels of generality, and are biased towards my own interests within discrete math. Many of these topics are quite deep and a surface-level introduction to the ideas would suffice for a final paper. You shouldn't be scared of any of these topics, even if the sources I've (hastily) compiled are intimidating --- please talk to me (indeed it's required you contact me with potential final paper topics by Oct 8th, and I hope this will lead to a conversation where we finalize your topic together). Some of the sources are entire textbooks, and in many cases it would be appropriate to focus on a single chapter or a few sections. There are many more sources for the listed topics than the ones I've linked, and in some cases the linked source is just a starting point and you will need to find additional ones.
There are many additional topics which would be appropriate for presentations/papers in this course. See e.g. Postnikov's course website from 2018, and feel free to come up with your own topic based on your own interests (in consultation with me). My interpretation of discrete mathematics is extremely broad, since discrete structures show up across pure and applied mathematics, as well as in computer science. I'll accept essentially any topic if it is sufficiently deep and you can convince me that it is related to discrete mathematics in a significant way.
Stanley EC1 and EC2 refer to Stanley's textbook Enumerative Combinatorics, volumes 1 and 2.
Enumerative combinatorics
Generating functions (eg Stanley EC1 chapter 4, EC2 chapter 5, Wilf generatingfunctionology)
Möbius inversion formula and applications (Stanley EC1 chapter 3)
Partially ordered sets and lattices (related to above; Stanley EC1 chapter 3)
Pólya enumeration and Burnside's lemma (Zabrocki's notes, see also wikipedia)
Combinatorial species (intro by Bergeron, Labelle, and Leroux, good wikipedia page)
Parking functions (introduction by Carlson et. al.)
Catalan numbers (Pak's webpage)
Random walks (kind of miscategorized -- good wikipedia page, and various introductions online)
Graph theory
Ramsey theory (Jungic's book)
4-color theorem (Numberphile video)
Probabilistic method (lecture notes by Matoušek and Vondrák)
Graphs on surfaces (Johnson's notes)
Graph algorithms (many interesting examples in Johnson's notes)
Graph minor theorem (notes by Lovász)
Homology/Euler characteristic of a graph (related to simplicial complexes below, don't confuse with graph complexes: see the wikipedia page and a chapter from Sunada's book. Great elementary way to start learning a bit about algebraic topology.)
Matrix-tree theorem/Cayley's formula (Stanley OCW notes)
Chromatic polynomials (Johnson's notes)
Chip-firing and Riemann--Roch for finite graphs (original paper of Baker--Norine, many other sources for chip-firing)
Algebraic combinatorics
Representation theory of the symmetric group (Sagan's book)
RSK algorithm (Stanley EC2 section 7.11)
Symmetric functions (Macdonald chapter 1, Stanley EC2 chapter 7)
Ehrhart theory and related topics (Beck--Robins)
Enumerating faces of polytopes and simplicial spheres (Huh's Numberphile video on g-conjecture, Kalai's blog post, Ziegler's lectures on polytopes, particularly chapter 8)
Scissors congruence (Pemantle's notes, Calegari's notes)
Matroids (Ardila's notes, Ardila's Notices article, Wang's notes on Hodge theory for matroids)
Unimodal and log-concave sequences in combinatorics (Stanley's survey, see also matroids/polytopes above)
Category theory (Riehl's book)
Combinatorial aspects of geometry and topology
Topology and combinatorics of hyperplane arrangements (Stanley EC1 section 3.11, Stanley's notes)
Moduli spaces of stable pointed (genus zero) curves (Cavalieri's notes, McMullen's paper on relationship to power series)
Graph complexes and tropical curves (Chan--Galatius--Payne, Chan's notes, Willwacher's masterclass)
Simplicial complexes and simplicial homology (Kozlov's combinatorial algebraic topology, chapters 2 and 3, Wilson's course, starting from worksheet 8)
Toric varieties (first few chapters of Cox, Little, Schenck)
The space of phylogenetic trees (Billera, Holmes, Vogtmann)