kolount@math.uiuc.edu
W, Jan 22: § 3.1, 3.2, 3.5 (subsets of a n-set, number of permutations, number of subsets of a n-set of size k).
F, Jan 24: § 3.2, 3.3, 3.6 (identities involving binomial coefficients and combinatorial proofs of those, the Binomial Theorem, Pascal's Triangle, Stirling's Formula).
Homework Grading Policy: Turn in all assigned homework
on the date it's due. I will grade some significant fraction
of it each time.
--Try to be brief and precise. Do not just write formulas
and numbers but throw in some English as well to make
the thing readable (by the grader and by yourself later on).
Good style will be rewarded. Solutions that manage to avoid
messy calculations are much prefered.
Homework 1: § 3.13. Problems 2, 4, 6 (ignore last paragraph),
9, 10, 11, 12, 15, 17.
Due in class on F, Jan 31.
M, Jan 27: § 3.7, 3.8, 3.11. Ordered and unordered selections with repetitions and without, how many words on n different letters, relations (equivalences, total and partial orders, Bell numbers.
W, Jan 29: § 4.1, 4.2, 4.3. Recurrence relations, generating functions, deriving a functional equation for the gen. function, determining a sequence from its generating function, the Fibonacci numbers, the general k-step linear recurrence with constant coefficients.
F, Jan 31: Homework due today in class.
Your new homework assignment is here (file in
Postcript). It is due on Fri, Feb 7.
We cover today § 4.4 and § 4.5: Derangments, involutions,
Catalan and Bell numbers through their generating functions.
M, Feb 3: § 5.1, 5.2. The Principle of Inclusion and Exclusion (PIE).
W, Feb 5: § 5.2, 5.3. Continuation of PIE. Stirling numbers.
F, Feb 7: § 6.2, 6.3. Systems of Distinct Representatives (SDRs), the "marriage" theorem. Homework due today in class.
Homework No 3:
§ 4.8: 11(a), 13, 19
§ 5.6: 3, 7, 8 (a permutation is called even if it can
be written as product of an even number of transpositions, otherwise
it is called odd--this definition does not depend on how you write a
given permutation as a product of transpositions),
9 ("sign is a homomorphism" means that the
sign of the product of two permutations is the product of their signs).
Due in class on Fri, Feb 14.
M, Feb 10: Rest of Chapter 6 (Latin Squares and upper and lower bounds on their number).
W, Feb 12: A few facts about groups and finite fields (refer back to § 4.7).
F, Feb 14: § 6.6: Construction of sets with mutually orthogonal Latin squares using finite fileds. Chapter 7: introduction to extremal set theory. Intersecting families of sets, Sperner families.
1st Test: M, 24 Feb., in 223 Greg Hall from 7pm-8pm.
Homework No 4:
§ 6.7: 3, 5 (the incidence matrix of a family of n subsets
of [n] is the matrix whose ij-th element is 1 if
the i-th set contains the j-th point and 0 otherwise), 7.
Due F, 21 Feb in class.
In my book there is no 2nd problem. Check yours!
M, Feb 17: Continuing Chapter 7 (extremal set theory).
W, Feb 19: § 7.3: The de Bruijn-Erdos Theorem.
F, Feb 21: Chapter 8: Steiner triple systems.
Homework No 5:
§ 7.5: 2, 4, 7, 8.
1st Test: You're supposed to know up to Chapter 6 (included).
M, Feb 24: Continuation of the construction of Steiner triple systems for all eligible n. Do not forget the TEST tonight.
W, Feb 26: Ramsey theory (Chapter 10).
F, Feb 28: Ramsey's theorem. Some bounds on Ramsey numbers.
M, Mar 3: Applications of Ramsey's theorem. The infinite Ramsey theorem.
Homework No 6:
§ 8.7: 3, 11, 13, 14.
Due M, Mar 10, in class.
W, Mar 5: Several problems and examples with the Pigeonhole Principle and Ramsey's Theorem.
F, Mar 7: NO CLASS.
M, Mar 10: Introduction to Graphs (lots of terminology today).
W, Mar 12: § 12.1, 12.2. Partially ordered sets, lattices (Chapter 12).
F, Mar 14: § 12.5. Dilworth's Theorem.
Homework: § 12.10: 3. Due W, Apr 2, in class.
No Class on W, March 19, F, March 21 and M, March 31.
W April 2, F April 4, M April 7: Completed Chapter 14 (up to the Schreier-Sims Algorithm).
W April 9: Chapter 15. Proved the Orbit Counting Lemma. How many r-colorings of a three-dim cube? (We worked this out in detail.)
F, April 11, M April 14 and W, April 16: Finished Chapter 15 (up to § 15.4).
The second exam will be held, Thursday April 17 in 143 Altgeld
Hall, at 7pm.
Read up to Chapter 14 (not Chapters 8 or 9).
F, April 18: § 16.1 and § 16.2: Designs.
M, April 21, and W, April 23: § 16.3 and § 16.6. Fisher's inequality, Hadamard matrices.
Homework: Solve problem 7 from § 16.7.
Due on W, April 30.
F, April 25, and M, April 28: § 17.2, 17.4, 17.5: Error-correcting codes.
W, April 30, and F, May 2: Graph colorings (§ 18).
M, May 5: Proof of Brook's Theorem. Proof of the 5-coloring theorem for planar graphs.
The Final Exam will be held in the usual classroom, on W, the 14th of May, from 1:30-4:30pm.
The first test, the second test, and the final.