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):
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.
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$.)