# CMSC 37200 -- Combinatorics -- Spring 2014

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.

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.

## Course information

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

## 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.

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.

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

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.

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

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 Wednesday, June 4.

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

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

## 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.