To find out what's new, make sure you press your browser's REFRESH button.
Statistics of 2nd Midterm and cumulative test scores (all tests) posted
Second Midterm has been posted.
Michael Cervia's class notes are posted here. CAVEAT. These notes have NOT been proofread by the instructor. They contain many errors. The purpose of posting the notes is NOT to serve as a reference; the sole purpose is to help refresh your memory as to the subjects discussed in class; and even in that regard, the notes are neither complete nor accurate. Use these notes at your own risk, they come with no warranties of any kind. In particular, mistakes in the notes cannot serve as an excuse for making the same mistakes in the test. (Note added on 5-27, 0:20am: instructor proofread and corrected the material of the May 26 class.)
Cumulative test statistics posted. Compare with green numbers returned on May 26.
Quiz-3 statistics posted
ALL HOMEWORK statistics posted (#1-13). Compare with green numbers returned on May 26.
Homework set #14 has been posted. Due Thu, May 26.
Quiz-3 has been posted. Solve it without the time pressure.
Homework statistics posted (#1-11). Compare with green numbers returned on May 19.
Homework set #13 has been posted. Due Tue, May 24.
Homework set #12 has been posted. Due Thu, May 19.
First Midterm has been posted. Solve it without the time pressure.
Homework statistics updated. Compare with green numbers on homework returned Tue May 10.
Homework set #11 has been posted. Due Tue, May 17. Work on these problems only after the May 12 midterm.
Homework set #10 has been posted. Due Thu, May 12. Required for the Midterm, including the DO exercises.
Quiz-2 statistics posted.
Quiz-2 has been posted. Solve it without the time pressure.
Homework and quiz statistics posted. (Click "Statistics" on the banner.)
Quiz-2 rescheduled to Tuesday, April 26.
Quiz-1 has been posted. The point values have been slightly reduced so the values of the non-bonus problems add up to 60 points, corresponding to 6%. (Even the 6% was by mistake; future quizzes will be valued at 5% (50 points) as originally advertised.) The first midterm will be valued at 14% (as opposed to the 15% originally posted.)
The schedule of tests has been posted. (Click "grading, tests" on the banner.)
Please answer the Questionnaire even if you are only auditing. (Click "Questionnaire" on the banner.)
Schedule of tests posted. Click "Grading, tests" on the banner.
Class TuTh 12:00 - 1:20 Ry 276
Instructor: László Babai Ryerson 164 e-mail: laci(at)cs(dot)uchicago(dot)edu.
Office hours:
TA office hours TBA
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 2014 class notes.
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 are 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$.)