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

First batch of exercise set #20 posted (5-31, 8:20pm). Second batch posted (6-1, 7pm). Due Monday, June 2.

**Tuesday, June 3, 4:30pm: Alex Dunlap holds office hour (before the June 4 test) in Ry 162 ("Theory lounge")**

**John Loeber's class notes** posted. Click "Text" on the banner.

Quiz and HW statistics updated.

Quiz-6 posted. (Click "Grading, tests" on the banner.) Solve it on your own time.

Quiz-5 posted.

Statistics posted: Q4, cumulative quiz (Q1-Q4), cumulative HW (HW#3-HW#13) (May 6)

Exercise set #14 posted (5-5, 8:30pm). Due Wed, 5-7.

Exercise set #13 posted (5-3, 7pm). Due Mon, 5-5. Clarifications to Exx. 13.9 and 13.12 added 5-4 2pm.

First batch of Exercise set #12 posted (4-28, 7pm). Due Wed, 4-30.

Exercise set #11 posted (4-27, 7am; updated 4-28, 4:40pm).

Exercise set #10 posted. Posting was completed on 4-24, 8:50pm
and further updates made at 10:30pm.
If you checked this exercise set earlier,
please go back and **refresh** to see the update.

**Please answer the Questionnaire** if you have not done so yet.
(Click "Questionnaire" on the banner.)

**Schedule of tests posted.** Click "Grading, tests" on the banner.

Alex Dunlap holds **office hours** Thursday 4:30-5:30 in Ry-162 ("Theory lounge")

HW##7,8 statistics and cumulative HW statistics posted (4-22)

There will be a quiz on Wednesday, 4-23.

Exercise set #8 posted (4-20, 8am) (due 4-21)

HW#6 statistics and cumulative HW statistics posted (4-14)

Quiz-2 posted. Quiz-2 and cumulative quiz statistics posted (click "Statistics" on the banner).

There will be a quiz on Monday, 4-14.

Exercise set #6 has been posted (4-13, 6am). Due Monday 4-14.

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:

Alex Dunlap holds office hours Thursday 4:30-5:30 in Ry-162 ("Theory lounge")

make appointment with instructor in person after class or by e-mail

Methods of enumeration, proof of existence, explicit construction of discrete structures, the fundamental parameters of such structures (matching number, covering number, chromatic number, independence number of hypergraphs, the Shannon capacity of graphs), combinatorial extrema, regular structures (including finite projective planes), combinatorial duality are discussed. The tools developed include estimation of binomial coefficients, 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), linear programming duality and linear relaxation, methods of linear algebra (orthogonality, spectral inequalities), combinatorial applications of A. Weil's character sum estimates.

Mathematical puzzles will pepper the course. The instructor hopes that the course will be fun in many ways.

To get an idea of the breadth and depth of the discussion, check the test problem sets in the "Grading, tests" section.

**Prerequisites:**
Basic linear algebra and the basics of discrete mathematics, along
with a degree of mathematical maturity and an interest in creative
problem solving.

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.

The following may also be helpful:
John Loeber's class notes. REFRESH to see the latest version.

Caveat: these notes have not been checked by the instructor.

There will also be frequent postings on this (instructor's) course website. Please check this website frequently.

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

- mini version (miniDM)
- advanced version (advancedDM)

**Recommended reading:**

**Advanced introduction:**

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

**Advanced texts:**

L. Lovász: "Combinatorial Problems and Exercises." 2nd ed. AMS Chelsea Publ., ISBN# 978-0-8218-4262-1

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

**Basic introduction:**

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.

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 name
- 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.)
- If you did, what type of grade do you seek (letter grade [A-F], P/F, audit)? (You can change your mind about this later.)
- 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).

Grading is based on homework, tests, and class participation. The tests are closed-book. Proofs discussed in class required; exercises stated in class are helpful.

Class participation contributes 5% to the grade. (This includes answering the Questionnaire.) The tests contribute 50%. Homework contributes 45% as follows: suppose the total point value of the homeworks assigned is $N$ and your score is $K$. Then the quantity $f(K)=\max(0, 45(K-0.6N)/(0.4N))$ will be added to your grade percentage. (This quantity is the linear interpolation between the extremes of $f(N)=45$ (if you get perfect homework score) and $f(0.6N)=0$ if your score is $K\le 0.6N$.)

**1st quiz (3%):**Friday, April 4**2nd quiz (6%):**Monday, April 14**3rd quiz (15 min) (6%):**Wednesday, April 23**4th quiz (15 min) (6%):**Monday, May 5**5th quiz (15 min) (6%):**Wednesday, May 14**6th quiz (12 min) (5%):**Wednesday, May 21**"midterm" (45 min) (18%):**Wednesday, June 4