# CMSC 37200 -- Combinatorics -- Spring 2010

What's new | Course info | Text | Questionnaire | Grading, tests | Policy on collaboration | Puzzles | Exercises, homework | Statistics | prior years

Last updated June 4, 2010, 9pm

## What's new?

To find out what's new, make sure you press your browser's REFRESH button.

Final exam statistics posted (June 4). Click the "Statistics" tab on the banner.

Reminder. The last class of the term is Friday, June 4. Attendance is expected and will count toward the "class participation" portion of your grade (5%).

## TAKE-HOME EXAM posted (first batch May 26, the rest May 28)

### Due Wed, June 2, before class.

Please report any errors to the instructor.

All-quiz (1-5) statistics posted (May 26). Click the "Statistics" tab on the banner.

All-homework (1-8) statistics posted (May 25).

## Old news

Full exercise set #8 posted (a set of DO exercises was added on May 22, 7:30am). Due Monday, May 24.
Exercise set #9 also posted (due Wednesday, May 26).
Click the "Exercises, homework" tab on the banner.

First batch of exercise set #8 posted (May 20). Due Monday, May 24. Click the "Exercises, homework" tab on the banner.

Quiz-4 and Quiz-4 statistics posted. Click the "Statistics" tab on the banner. DO: Solve the problems.

Homework 1-7 statistics posted (May 10). Click the "Statistics" tab on the banner.

Exercise set #7 posted. Due Monday, May 10. Click the "Exercises, homework" tab on the banner.

Quiz-3 and combined test statistics posted. Click the "Statistics" tab on the banner.

Test dates posted. Click "Grading, tests" on the banner.

Solutions to exercise set #4 posted. Click "Exercises, homework" on the banner, and then "Solutions #4" on the banner. Study the solutions carefully.

Exercise sets ##5 and 6 posted. Click the "Exercises, homework" tab on the banner. Set #5 is due Friday, April 30. Set #6 is due Monday, May 3. Do not mix the solutions; hand in the solutions on their due dates. Start early on the problems.

Quiz-2 statistics posted. Click the "Statistics" tab on the banner.

Exercise set #4 posted. Due Wednesday, Apr 21. Start early on the problems; it is best if you read and understand them before Monday's class. Click the "Exercises, homework" tab on the banner.

Second quiz posted. Click "Grading, tests" on the banner. Solve by Wednesday.

Exercise set #3 posted. DO exercises due Friday, Apr 16 (before the quiz). Click the "Exercises, homework" tab on the banner.

Quiz statistics posted. Click the "Statistics" tab on the banner.

First quiz posted. Solve all problems, including the bonus problems, by Monday, Apr 12.

Exercise set #2 posted. HW due Monday, Apr 12. Click the "Exercises, homework" tab on the banner.

Go to top

## Course information

Instructor: László Babai     Ryerson 164     e-mail: laci(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.

Prerequisites: The principal prerequisite for this class is a degree of mathematical maturity. Basic linear algebra will be helpful. It helps if you have taken Discrete Mathematics but it is not required.

Go to top

## Texts

Your primary text will be your course notes, so 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):

Note that the chapter numberings in the two versions are not consistent. Some of the introductory chapters are missing from "advancedDM" while the 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

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

Recommended background text:

Kenneth H. Rosen: Discrete Mathematics and its Applications (n-th edition, n=2,3,4,5,...)

Recommended reference:

The Discrete Mathematics 2009 course (CMSC37110) is a good source of relevant exercises; check out the homeworks and the tests.

Go to top

### Questionnaire

Please send email to the instructor with answers to these questions, even if you are only sitting in on the class, did not register, answered the same questionnaire in an earlier class by the instructor, or have an unusual status. Your answers to these questions will help me better to plan the course. Please write "combinatorics data" in the subject.

• Your field, area of specialization, and status at the university (e.g., "3rd year math major with minor in economics," or "2nd year TTI-C grad student specializing in pattern recognition," or "student at large specializing in oceanography")
• Do you expect to graduate this quarter?
• Did you register for this class? (It is ok if you did not, I still want to hear from you.)
• Are you fulfilling a requirement with this class? If yes, please elaborate.
• Please tell me about your math background. Have you had proof-based courses before? Have you been exposed to creative problem solving? If so, tell me in what course(s) or program(s). Tell me about the four most advanced math courses you have taken (name of instructor, title of course, course number if at Chicago, name/location of institution).

Go to top

## Course information

Class MWF 11:30 - 12:20 Ry 276

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

Office hours: by appointment (please send e-mail)

Based on five 15-minute quizzes (6% each, total 30%), homework (40%), a take-home exam (25%), and class participation (5%). For the quizzes: no book or notes. Proofs discussed in class required; exercises stated in class helpful.

Go to top

## Rules on HOMEWORK

Homework will be assigned in class and/or on this website. If you find an error or something that looks suspicious in an assignment, please notify the instructor (by email). If you are the first to point out an error, you may receive bonus points. "DO" problems are meant to check your understanding of the concepts. Do them but do not hand them in. You may encounter them in tests. Challenge problems don't have a specific deadline except they cease to be assigned once they have been discussed in class. If you are working on a challenge problem, please send email to the instructor so as to avoid the problem being discussed before you handed in the solution. Solutions to Challenge problems don't earn you credit toward your grade but they do earn you the instructor's respect, in addition to giving you valuable experience.

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.