Undergraduate Seminar in Discrete Mathematics 18.304, Spring 2015, MIT

See also the course Stellar page and the Piazza page.

Instructor. Omer Tamuz, room E18-478. Office hours are Monday 10 to 12, with more time available by appointment if necessary. Students are strongly encouraged to meet the instructor for help with any of the assignments. The Piazza page is a good place to post questions that may interest others.

Meetings. Room E17-129, Tuesdays and Thursdays at 2:30 to 4.

Textbook. Most student lectures will be given from Proofs from THE BOOK, available electronically or in print from the library. Students may give other lectures, pending instructor approval.

Requirements. Room E17-129, Tuesdays and Thursdays at 2:30 to 4.

Give three 35 minute lectures.
- The first will be given using a slide show, and the second will be a blackboard talk. Students are free to choose either for the third talk.
- The first and second will be given on a chapter of "Proofs from THE BOOK". Students may choose other topics, after coordinating with the instructor.
- The last lecture will be given on an independently chosen topic.
- Students are required to give a practice talk, either to a peer or to the instructor (at the instructor's discretion).
- Students must furthermore prepare a short quiz for the end of their talk, which should take no more than 5 minutes to solve and be easy for anyone who paid attention.
Write a short paper on an assigned topic. This will be a 2 to 4 page paper which will be assigned in the beginning of the term. Papers must be written in L^aT_eX.
Write a final paper on the topic of the last talk. This will include handing in a paper outline, a first draft, a second draft (if necessary) and a final draft. Papers must be written in L^aT_eX.
Attend all the meetings and give feedback on other students' talks. Students who miss more than one meeting will be required to write a short paper describing the lectures given there.
There is no final exam.

Guidelines for giving lectures.

Talking about something that you find beautiful and understand well makes it easier to give a good lecture. Make sure you choose topics that you like, and study them well.
Find your own style of talking; there is no universal way to give talks.
The goal of the lecture is to teach math to your peers. Whatever you do that achieves that goal is good! Not to be confused with (1) demonstrating to the instructor that you understand the subject, or (2) reading out loud the paper / book chapter that you are presenting.
Encourage the audience to ask questions. After explaining a subtle point give them time to think about it before you move on. Maintain eye contact with them to make sure they are still with you.
You do not have to prove everything formally, but you should prove something formally and make sure the audience has an idea of how the rest was proved.
Talk slowly; the bottleneck of a talk is not how fast you can speak, but how fast the audience can understand. Plan to have some spare time to answer questions, make mistakes etc. This will also help you be more relaxed.
Slide shows: (1) Don't put more than 4 lines on each slide, (2) consider using L^aT_eX beamer rather than WYSIWYG software like PowerPoint; a template is available here, (3) give the audience time to read each slide, and (4) use figures! Also, come 10 minutes before your lecture to make sure your computer connects properly to the projector.

Students are strongly encouraged to meet the instructor while preparing their talks to discuss mathematical content, delivery strategy, or any other issues.

Short paper.

Prove the following theorem regarding asynchronous majority dynamics: Theorem. Let G=(V,E) be a finite, undirected simple graph with odd degrees. Then, for any initial opinions and any update sequence, the size of the set {(u,t) | X^u_t ≠ X^u_t-1} is at most |E|.
The synchronous analogue of this theorem appears in "Periodic behaviour of generalized threshold functions", by E. Goles and J. Olivos, Discrete Mathematics, 1980.
Paper outline:
- No need to define graphs.
- Define majority dynamics (asynchronous).
- Define L_t.
- Prove the following: Lemma. L_t is non-increasing.
- Prove the theorem.
Those who want more of a challenge can prove the following: Theorem. Let G be a graph of bounded maximal degree, and such that the number of edges at distance r from some vertex w is bounded from above by a polynomial in r. Then there exists a C > 0 such that for any initial opinions and any update sequence, the total number of times that X^w_t ≠ X^w_t-1 is at most C.

Very short paper.

Write a proof of the six color theorem using this template.
You can make changes to the template if you wish, but the only requirement is to fill in the proof of the theorem. There's no need to prove the lemma.
Hint: prove by induction on the size on the graph. Another possiblity is to assume by contradiction that the theorem is false, and proceed by analyzing a smallest graph that violates it.
Due April 2^nd.

Final paper.

The paper should be 10 or more pages long, including about 5 or 6 pages of proofs.
Papers must be written in L^aT_eX; a template is available here.
Don't plagiarize.

Semester schedule.

February 3^rd and 5^th: introduction, lectures by instructor.
February 10^th: student lectures start.
February 24^th: short paper due.
March 20^th: final paper proposal due.
April 2^nd: very short paper due.
April 2^nd: final paper outline due.
April 16^rd: final paper first draft due.
April 30^th: final paper second draft due (if requested by instructor).
May 7^th: final paper due.

Resources. In additional to the assistance you will receive from your peers and instructor, help with presenting and writing is available from the department’s mathematical communication specialist, Susan Ruff (ruff@math.mit.edu). You can come to her office hours (Wednesdays 4 to 5 at E17-404), or e-mail her to arrange a time to meet. Linda Sutliff (lsutliff@mit.edu), a lecturer in Writing, Rhetoric, and Professional Communication is also available to help you. Please e-mail her to arrange a meeting.

General help with writing and presenting (not specific to mathematics) is available from MIT's Writing Center.

Grading.

Each talk will be worth 15%; 7% for the depth and correctness of the mathematics, 7% for communication, and 1% for the audience's performance in the quiz. Any points lost on communication may be regained in subsequent lectures by improving the relevant issues.
The short paper will be worth 7%.
The very short paper will be worth 3%.
The final paper will be worth 25%.
Participation will count for 20%. Half of these points will be given for correctly solving the quizzes at the ends of the lectures, and half for giving helpful feedback to the speaker.

Collaboration. Collaboration on preparing lectures is encouraged, as is the reading and deciphering of material. However, papers have to be written individually. Students are strongly discouraged to commit plagiarism. It is forbidden to copy any complete sentence from another source, including work submitted in past years or other courses. It is furthermore not acceptable to copy a proof, rewriting each line. A good strategy for writing a proof that appears elsewhere is to read and understand the source, then write it from scratch the next day. Here are some guidelines of what is and isn't allowed, and here are some examples.

Students in need of assistance or in distress. If you are dealing with a personal or medical issue that is impacting your ability to attend class or complete work you have the possibility of discussing this with Student Support Services (S³). The deans in S³ will verify your situation, and then discuss with you how to address the missed work. You may consult with S³ in 5-104 or at 617-253-4861. Also, S³ has walk-in hours: Monday through Friday, 9-10am.

MIT is committed to the principle of equal access. Students who need disability accommodations are encouraged to speak with Kathleen Monagle, Associate Dean, prior to or early in the semester so that accommodation requests can be evaluated and addressed in a timely fashion. Even if you are not planning to use accommodations, it is recommended that you meet with Student Disability Services staff to familiarize yourself with the services and resources of the office. You may also consult with Student Disability Services in 5-104 or at 617-253-1674.