## [ 18.304 - 3pm]

## Undergraduate seminar in

## Discrete Mathematics

### Course information

- Class schedule: MWF 3pm (room 2-151)
- Office hours: W 4-6pm (room 2-363A)
- Email: rothvoss@math.mit.edu

### Material

- Syllabus (including many details on grading, important dates etc)
- Preliminary schedule
- Reference list
- How to give a good math talk

### Examples for excellent math talks

### Schedule for the next classes

- Fr., February 8: Cancelled due to blizzard Nemo

- Mo., February 11: First 6 students will give a 5-10min short presentation of some theorem/definition
- We., Februrary 13: Second half of students will give a 5-10min short presentation of some theorem/definition
- Fr., February 15: 1st 45min talk by Linda: "Hamiltonian cycles"
- Tue., February 19: 2nd 45min talk by Chen Dan: "The master theorem"
- We., February 20: 3rd 45min talk by Christopher: "Sorting algorithms"
- Fr., February 22: 4th 45min talk by He Oliver: "Generating functions"
- Mo., February 25: 5th 45min talk by Hrishikesh: "Approximation algorithms"
- We., February 27: 6th 45min talk by Shawn: "Combinatorics 101"
- Fr., March 1: 7th 45min talk by Pratiskha: "Markov
Chains"

- Mo., March 4: 8th 45min talk by Jibo: "Cutting triangles"
- We., March 6: 9th 45min talk by Melissa: "Dijkstra's algorithm"
- Fr., March 8: 10th 45min talk by Pak Yan Daisy: "Numerical Methods in Root Finding for Nonlinear Equations"
- Mo., March 11: 11th 45min talk by Rachel: "Konig's Theorem" (cancelled)
- We., March 13: 12th 45min talk by Eric: "AdaBoost algorithm"
- Fr., March 15: Round II, talk 1 by Linda: "Ramsey theory"
- Mo., March 18: Quizz 1 (covering all 11 talks of the first round)
- We., March 20: postponed
- Fr., March 22: postponed
- Mo., April 1: Scientific writing workshop by Susan
- We., April 3: Scientific writing workshop by Susan
- Thursday., April 4, Evening class: 45min talk (round II)
by Chris
and Chen
Dan

- Fr., April 5: 45min talk (round II) by Oliver
- Mo., April 8: Term paper presentation by Chen Dan
- We., April 10: Term paper presentation by Chris and Oliver
- Fr., April 12: Term paper presentation by Hrishikesh and Shawn
- Mo., April 22: Term paper presentation by Rachel and Eric
- We., April 24: Classes
cancelled due to memorial service. The following
talks will be rescheduled on a later date (that is TBD):

45min talk (round II) by Shawn; Term paper presentations by Linda, Pratiksha, Jibo, Melissa, Daisy and the 45min talk (round I) by Rachel - Fr., April 26: 45min talk (round II) by Hrishikesh
- Mo., April 29: 45min talk (round II) by Pratiksha
- We., May 1: 45min talk (round II) by Jibo
- Fr., May 3: 45min talk (round II) by Melissa
- Mo., May 6: 45min talk (round II) by Daisy
- We., May 8: 2nd quizz (covering round II of 45min talks until the talk of Daisy)
- Fr., May 10: 45min talk (round II) by Eric

- Mo., May 13: 45min talk (round II) by Rachel

- We., May 15: 45min talk (round II) by Shawn
- Fr., May 17: 45min talk (round I) by Rachel

### Possible topics for the 2nd talk and/or the term paper

In the following you can find a list of potential topics that you might choose for your 2nd talk and/or your term paper. But the list is not complete; you can still choose any other topic in discrete math that you like, but please make sure that the complexity degree is comparable to the topics below.- The Lovász Local Lemma and applications (Melissa's 2nd talk): See e.g. chapter 5 in the "Probabilistic method" book of Alon and Spencer
- The equivalence of H-representation and V-representation for polytopes: See e.g. chapter 1 & 2 in the book "Lectures on polytopes" by Ziegler
- The diameter of polytopes: See e.g. chapter 3 in the book "Lectures on polytopes" by Ziegler
- Szemeredi's Regularity Lemma (Rachel's term paper): See e.g. chapter 17 in the book "Probabilistic method" of Alon and Spencer
- Testing perfect matchings in general graphs via the Tutte determinant (Oliver He's 2nd talk): See e.g. the lecture notes of Saberi
- Erdös-Renyi Random Graphs (Hrishikesh's term paper): See e.g. chapter 10 in the "Probabilistic method" book of Alon and Spencer
- Davenport-Schinzel Sequences: See e.g. chapter 7 in the book "Lectures in discrete geometry" of Matousek
- The Johnson-Lindenstrauss
Flattening Lemma: See e.g. chapter 15 in the book
"Lectures in discrete geometry" of Matousek

- Minkowski's Theorem and Applications: See e.g. chapter 7 in the book "Lectures in discrete geometry" of Matousek
- Convex independent subsets and the Erdös-Szekeres Theorem: See e.g. chapter 3 in the book "Lectures in discrete geometry" of Matousek
- The crossing number theorem and applications (Jibo's term paper): See e.g. chapter 4 in the book "Lectures in discrete geometry" of Matousek
- Ramsey Theory (2nd talk of Linda): See e.g. chapter 6 in the book "Modern Graph Theory" by Bollobas
- Dependent random choice and applications: See the survey of Jacob Fox in the reference list
- The Kruskal-Katona Theorem (Linda's term paper): See e.g. "A new short proof for the Kruskal-Katona theorem" by Frankl or chapter 5 in the book "Combinatorics" of Bollobas
- The second moment method and applications (Pratiksha's 2nd talk): See e.g. chapter 4 in the book "Probabilistic method" of Alon and Spencer
- Max flow algorithms (Chris' term paper): See e.g. chapter 3 in the book "Combinatorial optimization" by Cook, Cunningham, Pulleyblank, Schrijver
- Matroids (Olivers' term paper): See e.g. chapter 8 in the book "Combinatorial optimization" by Cook, Cunningham, Pulleyblank, Schrijver
- Discrepancy minimization. See this paper of Lovett and Meka.
- The multiplicative weight update algorithm. See this survey.
- Tree embeddings and applications. See this paper or the book "Design of approximation algorithms" by Shmoys and Williamson.
- The Borsuk-Ulam Theorem and applications. See the book "Using the Borsuk-Ulam Theorem" by Matousek.
- Intersection patterns of convex sets. See e.g. chapter 8 in the book "Lectures in discrete geometry" of Matousek
- Geometric selection Theorems. See e.g. chapter 9 in the book "Lectures in discrete geometry" of Matousek
- Epsilon nets and VC-dimension. See e.g. chapter 10 in the book "Lectures in discrete geometry" of Matousek

### How to write the term paper

- Topic: Please pick a topic you like (either from the list above or one of your choice) and inform the lecturer by Monday, March 18.
- Material from the writing workshop:
- The Maximum Overhand paper with annotations
- Homotopy
theories with annotations

- How
to acknowledge sources

- Structure: The
term paper should be written in the style of an actual
research paper, using 8-12 pages written in Latex. The
following structure is recommended

- Abstract: Few paragraphs about the main content
- Introduction: includes motivation and gives an overview
over the literature and potentially a brief outline of the
result(s) of the term paper

- Main body (in general comprising of several sections)

- Reference list

- Content: Your term
paper will in general be a summary (in your own words) of
results in the chosen topic. I do appreciate creativity -- but it is
not required. You can be creative e.g. by

- giving a proof that is different from the one in the literature
- generalizing a known proof

- giving a new application of the theorems
- providing an example where the proven theorem is tight
(i.e. a proven bound is tight or dropping one of the
assumptions makes the claim invalid)

- Latex: The paper should be written in Latex. You can e.g. start with the following template (tex-file, pdf-file, bib-file), but feel free to use your favorite fonts etc. BTW, I do appreciate meaningful figures.
- References: A good source to find bibtex entries of papers is http://dblp.kbs.uni-hannover.de/dblp and http://www.ams.org/mathscinet
- Remark: There will
be more information during the in-class writing workshop
given by Susan Ruff on April 1+3.