Math 28410 / CMSC 27410 -- Honors Combinatorics

CMSC 37200 -- Combinatorics -- Spring 2016


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

What's new?

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.

Old news

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.


Course information

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


Course description

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.


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.

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

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.

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.

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.

Go to top


Grading, tests

Due to the large number of graduating students, there will be no final exam in finals week in this course. Instead, there will be a "final midterm" on Tuesday, May 31.

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

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 may or may not have a specific deadline but they expire 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 class discussion of the problem before you handed in the solution.

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.

View the instructor's course material from previous years

Return to the Department of Computer Science home page

Go to top