Math 28400 CMSC 27400 -- Honors Combinatorics and Probability

CMSC 37200 -- Combinatorics -- Spring 2008

What's new?

Statistics of quizzes 2,3,4 and cumulative test statistics posted (click the "Statistics" tab on the banner)

24th set of Exercises posted (class 6-4; posted 6-5 at 4:40 am). (Click the "Exercises" tab on the banner.)

New handout: corrected proof of the Erdős - Ko - Rado Theorem.

New tab on banner: Tests. Wed 5-28 quiz moved to Fri 5-30.

TA will hold offices hour Tuesday, May 20, at 5pm in the usual place (Ry 162) and every Tuesday afterwards (May 27, June 3) (the day before each quiz).

TEST DATES and grading scheme REVISED: three new 10-minute quizzes added. Click "Grading, test dates" on the banner.

Midterm-2 statistics updated 5-20. (Click "Statistics" tab on the banner.)

Second Midterm posted. Click "Tests" on the banner. Solve the problems you didn't. You may encounter them again.

TA holds office hour every Thursday 5pm - 6pm in Ry-162 ("theory lounge")

Go to top

Old News

NEW QUESTIONNAIRE posted. Click "Questionnaire" on the banner. PLEASE RESPOND by the end of this week (April 27) even if you sent a similar email previously - there are many extra questions.

Go to top

Course information

Instructor: László Babai Ryerson 164 e-mail: laci(at)cs(dot)uchicago(dot)edu.

Teaching Assistant: Sourav Chakraborty; e-mail: {firstname}(at)cs(dot)uchicago(dot)edu.

Course description

Methods of enumeration, construction, and proof of existence of discrete structures are discussed in conjunction with the basic concepts of probability theory over a finite sample space (random variables, independence, expected value, standard deviation, and Chebyshev's and Chernoff's inequalities). Concepts of combinatorial optimization such as duality and good characterization are introduced. Topics include counting, generating functions, Latin squares, finite projective planes, graph theory, matchings, flows in networks, Ramsey theory, coloring graphs and set systems, extremal combinatorics. The highlights include unexpected applications of linear algebra and number theory. Mathematical puzzles will pepper the course. The instructor hopes that the course will be fun in many ways.
Go to top

Texts

Your primary text will be your course notes, so please make sure you don't miss classes. If you do, you should copy somebody's class notes and discuss the class with them.

There will also be frequent web postings. Please always check this website.

Online texts: instructor's "Discrete Mathematics" lecture notes in PDF (preliminary, incomplete drafts):

mini version (miniDM)
advanced version (advancedDM)

Note that the chapter numberings in the two versions are not consistent. Some of the introductory chapters are missing from "advancedDM" while th mini version does not include any of the advanced material; regarding chapters that appear in both versions, the mini version is current.

Printed text:

J. H. van Lint, R. M. Wilson: "A Course in Combinatorics," Cambrdge University Press, ISBN# 0 521 00601 5

Recommended supplementary reading:

J. Matoušek, J. Nešetříl: "Invitation to Discrete Mathematics," by Oxford University Press, ISBN# 098502079.

Go to top

Questionnaire (April 23)

Please send email to the instructor with the following information (even if you sent a similar message previously). Please do respond even if you are not registered and only audit the class. Otherwise I will be forced to try to track you down to find out your answers.

You name, status (grad/undergrad, major/minor/year).
Are you registered for this class? If so, under what course number (Math-284, CMSC-274, CMSC-372)?
What type of credit do you seek (letter grade, P/F, audit)?
If letter grade, your minimal grade expectation? (E. g. "B+")
Are you taking this class to fulfill a requirement? If so, what is the minimum grade that will meet the requirement?
Do you expect to graduate this term? (If so, it is critical to make arrangements now because the final exam which you will miss accounts for 45% of the grade.)
Have you been solving a decent portion of the exercises assigned in class? How much time do you spend on working on them? Do you feel you need help with them? Are you woring with others in the class?
How do you verify that your solutions to the exercises are correct, and whether simpler solutions exist?
How many times did you attend the TA's office hours?
Any comments you wish to make regarding the class.

Go to top

Grading, test dates

Revised 5-19. Based on tests and class participation. Four quizzes (the first quiz is 20 minutes and weighs 8%, each of the subsequent quizzes are 10 minutes for 4% each), two midterms (21% each), final exam (35%), class participation (3%).

First Quiz: Friday, April 11. (No book or notes.)
First Midterm: Wednesday, April 30.
Second Midterm: Wednesday, May 14.
Second Quiz: Wednesday, May 21 (10 minutes)
Third Quiz: Friday, May 30 (10 minutes)
Fourth Quiz: Wednesday, June 4 (10 minutes)
Final Exam: Wednesday, June 11, 1:30 - 3:30 pm.

Go to top

Policy on collaboration

Studying in groups is strongly encouraged. Collaboration on current homework is discouraged but not prohibited. If you do collaborate, state it at the beginning of your solution (give name of collaborator). DO NOT COPY someone else's solution: after the discussion, throw away any written records. Understand the ideas discussed and give your own rendering. The same applies to other sources such as the Web: give the source (URL), but DO NOT COPY. Understand; then write your own version without looking at the source or your notes.