Undergraduate Seminar in Discrete Mathematics 18.304, Spring 2015, MIT
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
Meetings. Room E17-129, Tuesdays and Thursdays at 2:30 to 4.
Textbook. Most student lectures will be given from
from THE BOOK, available electronically or in print
from the library. Students may give other lectures, pending
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
- Students are required to give a practice talk, either
to a peer or to the instructor (at the instructor's
- 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
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
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 is no final exam.
Guidelines for giving lectures.
Students are strongly encouraged to meet the instructor while
preparing their talks to discuss mathematical content,
delivery strategy, or any other issues.
- 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
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.
Very short paper.
Prove the following theorem regarding asynchronous
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
Xut ≠ Xut-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.
- No need to define graphs.
- Define majority dynamics (asynchronous).
- Define Lt.
- Prove the
following: Lemma. Lt is
- Prove the theorem.
Those who want more of a challenge can prove the
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 Xwt
≠ Xwt-1 is at most C.
- 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 2nd.
- The paper should be 10 or more pages long, including
about 5 or 6 pages of proofs.
- Papers must be written
in LaTeX; a
template is available here.
- Don't plagiarize.
- February 3rd and 5th: introduction,
lectures by instructor.
- February 10th: student lectures start.
- February 24th: short paper due.
- March 20th: final paper proposal due.
- April 2nd: very short paper due.
- April 2nd: final paper outline due.
- April 16rd: final paper first draft due.
- April 30th: final paper second draft due (if
requested by instructor).
- May 7th: 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
(email@example.com). You can come to her office hours (Wednesdays
4 to 5 at E17-404), or e-mail her to arrange a time to
Sutliff (firstname.lastname@example.org), a lecturer
Rhetoric, and Professional Communication is also available
to help you. Please e-mail her to arrange a meeting.
help with writing and presenting (not specific to mathematics) is
- 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
- 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
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
are some guidelines of what is and isn't allowed, and
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 (S3). The deans in S3 will
verify your situation, and then discuss with you how to address
the missed work. You may consult with S3 in 5-104 or at
617-253-4861. Also, S3 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.