Math 180, Combinatorics, Winter 2013

Office Hours: MW 2:00-3:30

Tentative Schedule

Syllabus :[Syllabus_math180_Winter2013]

Note: Weekly homework is due at the beginning of Disccusion section. Homeworks will be posted here:

Homework 1 is due on Thursday, Jan 17:

Section 5.1: 2, 6, 9, 13(a), 24, 34, 39, 46.
Section 5.2: 7, 12, 22, 29, 46(a), 70, 82.
Section 5.3: 4, 10, 19, 25, 30, 35.

Homework 2 is due on Thursday, Jan 24:

The problems from section 6.2 have been moved to Homework3.
Section 5.4: 8, 14, 26, 40, 55.
Section 5.5: 3(c), 12(b), 14(d), 20(b), 32.
Section 6.1: 7, 10, 15, 20, 22.

Homework 3 is due on Thursday, Jan 31:

Section 6.2: 8, 16, 26, 28, 35(b), 41.
Section 6.3: 2, 5, 12, 16, 19(b).
Section 6.4: 6, 12, 14, 16, 17, 20.

Homework 4 is due on Thursday, Feb 7:

Section 7.1: 18, 25, 34(c), 36, 46.
Section 7.3: 2, 4, 6, 8, 10.
Section 7.4: 6, 9(b), 10, 17, 18.

Homework 5 is due on Thursday, Feb 14:

Section 7.5: 1(d), 4, 8, 13, 14.
Section 8.1: 10, 14, 18, 26, 34, 36.

Homework 6 is due on Thursday, Feb 21:

Section 8.2: 8, 12, 18, 22, 25, 28, 38(a,b), 40, 44(a).
Section 1.1: 6, 7.
Section 1.2: 2, 6(b,h), 10, 14(b).

Homework 7 is due on Thursday, Feb 28:

Section 1.3: 1(b), 4, 6, 8, 11, 16.
Section 1.4: 4, 6, 8, 12(b,c), 16, 20, 23.

Homework 8 is due on Thursday, Mar 7:

Section 2.1: 2, 8, 12(a), 15, 16.
Section 2.2: 2(b), 4(b), 6, 16, 24.

Homework 9 is due on Thursday, Mar 14:

Section 2.3: 1(c,p), 2(b,d).
Section 2.4: 2, 4, 8, 9(b), 11, 14(c,d).

The following two are good exercises for matchings in bipartite graphs; No need to submit.

Problem 1: Let M be a matching in a bipartite graph G and assume that M contains fewer edges than some other matching M' in G. SHow that G contains an M-augmenting path.
Hint: Consider the symmetric difference between M and M' to construct such path.
Problem 2: Let A be a finite set with subsets A_1,A_2...,A_k, and let d_1,d_2,...,d_k be positve integers. Show that there are disjoint subsets B_i of A_i with sizes of d_i for all i=1,2,...,k, if and only if for any subset S of {1,2,...,k}, the size of the union of A_i over all i in S is at least the sum of d_i over all i in S.
Hint: Define a bipartite graph in which A is one side and the other side consists of a suitable number of copies of A_i. Then reduce this to the Hall's Theorem.

Course outline will be updated here during term:

Lec 1: Two basic counting principles (Section 5.1)

Lec 2: Simple arreangements and Selections (Section 5.2)

Lec 3: Arreangements and Selections with repetitions (Section 5.3)

Lec 4: Distributions (Section 5.4)

Lec 5: Binomial Identities (Section 5.5)

Lec 6: Models of generating functions (Section 6.1)

Lec 7: Coefficients of generating functions (Section 6.2)

Lec 8: Partitions (Section 6.3)

Lec 9: Exponential generating functions (Section 6.4)

Lec 10: Recurrence relations (Section 7.1)

Lec 11: Solution of linear recurrence relations (Section 7.3)

Lec 12: Solution of inhomogeneous recurrence ralations (Section 7.4)

Lec 13: Recurrence relations VS generating functions (Section 7.5)

Lec 14: Midterm

Lec 15: Venn diagram (Section 8.1)

Lec 16: Inclusion-Exclusion formula (Section 8.2)

Lec 17: Basic of graph theory (Section 1.1-1.2)

Lec 18: Edge Counting (Section 1.3)

Lec 19: Planar graphs (Section 1.4)

Lec 20: Euler Cycles (Section 2.1)

Lec 21: Hamilton circuits (Section 2.2)

Lec 22: Hamilton circuits continued

Lec 23: Graph Coloring (Section 2.3-2.4)

Lec 24: Graph Coloring continued

Lec 25: Chromatic polynomial (Section 2.4)

Lec 26: Matching in bipartite graphs--Konig's Theorem

Lec 27: Matching in bipartite graphs--Hall's Theorem

Lec 28: Review