Math 343J -- Discrete Math II -- Winter 2012

Handouts:

Reading Assignments:

Week Number Assignment Due Date
1 1 p.1-6:  Graphs and Their Relatives; Basic Vocabulary (read up thru Theorem 1.1) W 1/11
2 p.6-12:  Perambulation and Connectivity; Special Types of Graphs (read up thru Paths) F 1/13
2 3 p.12-16:  Subgraphs and Bipartite Graphs M 1/16
catch-up day (HW 1 due) W 1/18
4 p.17-20:  Distance in Graphs F 1/20
3 5 p.21-25:  Graphs and Matrices M 1/23
6 p.26-30:  Graph Models and Distance (read up thru end of Section 1.2) (HW 2 due) W 1/25
7 p.30-34:  Trees F 1/27
4 8 p.35-37:  Trees M 1/30
9 p.38-42:  Spanning Trees, Kruskal's Algorithm (HW 3 due) W 2/1
Review R 2/2
Exam 1 F 2/3
5   no class (illness) M 2/6
10 p.43-47:  Counting Trees (omit Matrix Tree Theorem) ; HW 4 due W 2/8
11 p.51-55:  Trails, Circuits, Paths, and Cycles (HW 4 due) F 2/10
6 12 p.56-60:  Eulerian Trails and Circuits M 2/13
13 p.61-66:  Hamiltonian Paths and Cycles; HW 5 due W 2/15
  catch-up day F 2/17
7 14 p.67-72:  Three Open Problems M 2/20
15 p.73-77:  Planarity (HW 6 due) W 2/22
Review R 2/23
Exam 2 F 2/24
8 16
p.78-80:  Euler's Formula
M 3/5
  17
p.80-84:  Regular Polyhedra (HW 7 due)
W 3/7
  18

p.85-93:  Colorings and Chromatic Number (omit proof of Theorem 1.43)

 F 3/9
9 19
p.116-119:  Classical Ramsey Numbers
M 3/12
20
p.120-123:  Exact Ramsey Numbers and Bounds (hw 8 due)
W 3/14
21

p.130-137:  Combinatorics -- Essential Problems
F 3/16
10
no assignment -- work more problems
M 3/19
22
p.138-142:  Binomial Coefficients (hw 9 due)
W 3/21
    Review R 3/22
    Exam 3 F 3/23
11
23
p.144-149:  Multinomial Coefficients
M 3/26
24
p.150-154:  Pigeonhole Principle (hw 10 due)
W 3/28
no assignment -- catch up day
 F 3/30
12
no assignment
M 4/2
  25
p.156-161:  Inclusion/Exclusion
W 4/4
  26
p.164-169:  Generating functions, double decks, counting with repetition

F 4/6
13  
no notes; catch up and review
 
14   Exam 4 T 4/17

Homework Assignments:

Assignment #
Exercises
Due Date
1
 p.4 #1, 2, 3;  p.9 #1, 2, 3, 4, 5, 9;  prove Thm 1.2 by the method of smallest counterexample
W 1-18-12
2

p.10 #6, 7, 11, 12a; p.16 #1, 2, 3, 4, 7a, 8
W 1-25-12
3
 p.10 #10; p.16 #9, 10; p.20 #2, 4; p.25 #4, 7; p.30 #1, 2 (Km,n for optional extra credit on #1 & #2)

W 2-1-12
4

p.21 #5, 7

p.25 #3

p.33 #3, 4.  Prove #3 using “proof by algorithm.”  Design an algorithm to identify partite sets X and Y for T, and prove that your algorithm works correctly.

p.38 #5

Plus, one more problem.

W 2-8-12
5
p.42 #3, 4, 5, 6;  p.51 #1, 2, 3, 4, 5
W 2-15-12
6
See handout (problems for Section 1.4.2).
W 2-22-12
7
 p.66 #1, 2, 4, 5, 6;  p.76 #1, 2;  p.79 #1, 2, 3
W 3-7-12
8
p.83 #2;  p.87 #1, 2, 3, 5;  p.93 #1, 5, 7
W 3-14-12
9
  • p.97 #3:  Go online, print a political map of Africa, convert the map to a corresponding graph, and show how to color the graph vertices with the minimum number of colors.  Label each vertex with a country name and color each vertex with a pen, crayon, marker, etc.
  • p.118 #1, 2, 3, 4
  • p.116  The definition given of R(p,q) is hard for students to comprehend upon first reading it.  Your job is to explain the definition to a friend who knows what a graph is but hasn’t encountered Ramsey Numbers before.  Write a paragraph which might help someone understand the meaning of “R(p,q)”.
W 3-21-12
10
 p.134 #1, 4, 5, 8, 11; p.142 #2
W 3-28-12
11
 p.134 #7, 12;  p.142 #3, 5, 10, 11;  p.149 #2, 5, 9a
W 4-4-12
12
 See handout
W 4-11-12