## [ 18.304 - 1pm]

## Undergraduate seminar in

## Discrete Mathematics

### Course information

- Class schedule: MWF 1pm (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 Chandler on "Floyd Warshall Algorithm"
- Tue., February 19: 2nd 45min talk by Noor on "Lucky Tickets"
- We., February 20: 3rd 45min talk by Varun: "Minimum Spanning Trees"
- Fr., February 22: 4th 45min talk by Yuchen: "Counting
with rotational symmetry" (python
file, board
notes)

- Mo., February 25: 5th 45min talk by Daniel: "Combinatorial games"
- We., February 27: 6th 45min talk by Nargiss: "Generating
functions" (file
2, file
3)

- Fr., March 1: 7th 45min talk by Eli: "Fixed points in permutations"
- Mo., March 4: 8th 45min talk by Alicia: "Matching algorithms"
- We., March 6: 9th 45min talk by Yihui: "Clustering
and the K-means algorithm"

- Fr., March 8: 10th 45min talk by Xiaoyue: "Marriage algorithm"
- Mo., March 11: 11th 45min talk by Jonathan: "Spectral graph theory and metrics of centrality"
- We., March 13: 12th 45min talk by Alex: "Dijkstra's algorithm"
- Fr., March 15: Round II, talk 1 by Chandler: "Shortest paths via matrix multiplication"
- Mo., March 18: Quizz 1 (covering the 12 talks of round 1)
- Fr., March 20: 45min talk (round II) by Alicia on "Matchings in general graphs"
- Mo., April 1: Scientific writing workshop by Susan
- We., April 3: Scientific writing workshop by Susan
- Th., April 4: 45min talk (round II) by Yuchen

- Mo., April 8: Term paper presentation by Chandler
- We., April 10: Term paper presentation by Yuchen and Varun
- Fr., April 12: Term paper presentation by Daniel and Nargiss
- Mo., April 22: Term paper presentation by Jonathan and Alex
- We., April 24, 1PM: cancelled (due to memorial service).
The 45min talk (round II) by Daniel is postponed to some
later date (T.B.D.)

- Th., April 25, 8PM-10PM: Term paper presentations by Eli, Yihui, Alicia, Xiaoyue and Noor
- Fr. April 26: 45min talk (round II) by Nargiss
- Mo. April 29: 45min talk (round II) by Eli
- We. May 1: 45min talk (round II) by Yihui
- Fr. May 3: 45min talk (round II) by Noor
- Mo. May 6: 45min talk (round II) by Xiaoyue
(Video)

- We. May 8: 2nd Quizz (covering round II of 45min talks + the term paper presentations of Daniel and Nargiss)
- Fr., May 10: 45min talk (round II) by Jonathan
- Mo., May 13: 45min talk (round II) by Alex
- We., May 15: 45min talk (round II) by Varun
- Fr., May 17: 45min talk (round II) by Daniel

### 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 (Nargiss' term paper): 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: See e.g. chapter 17 in the book "Probabilistic method" of Alon and Spencer
- Testing perfect matchings in general graphs via the Tutte determinant: See e.g. the lecture notes of Saberi
- Erdös-Renyi Random Graphs (Jonathan'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: See e.g. chapter 4 in the book "Lectures in discrete geometry" of Matousek
- Ramsey Theory (Chandler's term paper): 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: 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: See e.g. chapter 4 in the book "Probabilistic method" of Alon and Spencer
- Max flow algorithms (Alex' term paper): See e.g. chapter 3 in the book "Combinatorial optimization" by Cook, Cunningham, Pulleyblank, Schrijver
- Matroids: 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.