Math 28410 CMSC 27410 -- Honors Combinatorics
CMSC 37200 -- Combinatorics -- Winter 2012
What's new
| Course info
| Text
| Questionnaire
| Grading, tests
| Policy on collaboration
| Puzzles
| Exercises, homework
| Statistics
| prior years
To find out what's new, make sure you
press your browser's REFRESH button.
Instructor:
László Babai Ryerson 164 e-mail:
laci(at)cs(dot)uchicago(dot)edu.
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:
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
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
Recommended supplementary reading:
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
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).
Go to top
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)
Grading is based on homework assigned in class (38%), a midterm (20%),
the final exam (38%), and class participation (4%).
The tests are closed-book.
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
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.