Time: Week 116: Monday, 08:00  09:40, Week 18: Thursday, 10:00  11:40. Location:下院413 
Teacher: Dominik Scheder. Teaching Assistant: 林茵 (ireane at "School domain"), 毛威超 (maoweichao at "School domain"), where "School domain" is "sjtu.edu.cn" 
Textbook: An Invitation to Discrete Mathematics by Jiři Matoušek and Jaroslav Nešetřil 
Material:
Video lectures and corresponding slides can be found at
Coursera or 好大学在线.

Grading: 50% final exam, 50% homework. The students will form groups of size 45. Homework will be handed in by every group. 
Date 
Week 
# 
Class 
SelfStudy 
Wednesday, June 20, 2018 
Week 17 

Exam. 

Monday, June 11, 2018 
Week 16 
23 
Discussing the exam of 2017. 

Monday, June 4, 2018 
Week 15 
22 
Preparing for the exam: reviewing course material and solving examlike problems in class. 

Monday, May 28, 2018 
Week 14 
21 
Discussing the solution of Homework 11. 

Monday, May 21, 2018 
Week 13 
20 
Discussing the solution to Homework 10. Addressing questions and problems concerning Homework 11. 
Here is last year's final exam. Work on it, you'll get an idea what type of prolems will be in the exam. 
Monday, May 14, 2018 
Week 12 
19 
Discussing Homework 9: Minimum number of edges you have
to remove from K_{n} in order to destroy
all Hamilton cycles. Theorem that every tournament has a
directed Hamilton path. 
Watch the remaining three videos.

Monday, May 7, 2018 
Week 11 
18 
Discussing solutions to Homework 8. 
Watch videos: Start with Homework 10. Here are the corresponding tex sources.Please take this onequestion survey and vote which material we should cover in the rest of this course. 
Saturday, April 28, 2018 
Week 10 
17 
Kirchhoff's Matrix Tree Theorem: how to compute the number of spanning trees of a given graph by computing the determinant of a matrix. 

Monday, April 23, 2018 
Week 9 
16 
Discussing solutions to Homework 7 (graph score theorems).
Presenting an inductive proof of the Multigraph Score Theorem
that incrementally builds a multigraph, by first drawing
an edge between the two highestdegree vertices and then
recursing. 
Watch videos:

Thursday, April 19, 2018 
Week 8 
15 
Preparing for Homework 8: Counting trees on n vertices. Presenting two different proofs, one using vertebrates and one using Prüfer codes. Selecting random students to come to the blackboard and do several examples. 

Monday, April 16, 2018 
Week 8 
14 
Discussing the first submission of Homework 7: graph score
theorems for alternative graphs (multigraphs, weighted
graphs, weighted graphs with negative weights allowed). 
Watch videos:

Thursday, April 12, 2018 
Week 7 
13 
Determining the winner of the
"smallest unique bet wins" game on graphs,
asymmetric graphs, and asymmetric trees. Handing out prizes.
Discussing several small problems on asymmetric trees. 

Monday, April 9, 2018 
Week 7 
12 
Discussing Homework 4, in particular Exercise 4.14,
giving a combinatorial proof
that (p^{d} choose k) is
divisible by p for 1 ≤ k ≤
p^{d}. 
Watch videos:

Thursday, April 5, 2018 


No class because of Qingming Festival. 

Monday, April 2, 2018 
Week 6 
11 
Applicationg of our estimates for the binomial coefficient: upper and lower bounds for errorcorrecting codes. 
Watch videos

Thursday, March 29, 2018 
Week 5 
10 
Estimating the size of the binomial coefficient. 
Watch videos 
Monday, March 26, 2018 
Week 5 
9 
A bit about Homework 4: How to make those combinatorial
identity proofs more formal. 
No new homework assignment this week. 
Thursday, March 22, 2018 
Week 4 
8 
Discussing the Exercise 2.15 (uncountable chain). Obtaining upper and lower bounds on the Bell numbers B_{n} and the Partition numbers P_{n}. 
Please take the little survey I have created on Survey Monkey. 
Monday, March 19, 2018 
Week 4 
7 
Discussing solutions to Homework 2. In particular

Watch video
Application to a problem in discrete probability theory.

Thursday, March 15, 2018 
Week 3 
6 
A bit more on orderings:
Hasse diagrams; some (infinite) examples where we cannot
reconstruct the ordering from the Hasse diagram.


Monday, March 12, 2018 
Week 3 
5 
Showing sample solutions for some problems in Homework 1. Discussing questions and first submission of Homework 2. 
Watch videos
Start with Homework 3 and submit questions by Sunday, March 17, 12:00. Here are the tex files of Homework 3. 
Thursday, March 8, 2018 
Week 2 
4 
Explaining and giving hints for some problems in Homework 2. 

Monday, March 5, 2018 
Week 2 
3 
Discussion of Homework 1 questions and submissions. Some more things on infinite sets. 
Watch the following videos:

Thursday, March 1, 2018 
Week 1 
2 
Given hints for Homework 1, Exercise 3.3 (feasible intersection sequences). Some basics of infinite sets, countable, uncountable setes. 
I wrote some lecture notes on set theory. Please read them, we will need this for Homework 2. 
Monday, February 26, 2018 
Week 1 
1 
Introduction. Two riddles: tiling the 8x8 chessboard and the coin riddle. 
Watch videos on 好大学在线 or Coursera or (in smaller resolution) by clicking on the links below:
Start with Homework 1. Here are the tex files of Homework 1. 