For the latest information, make sure to REFRESH your browser.
3-12 3:45 final statistics posted. Click "Statistics" on the banner.
3-04 20:18 assignments ORD07 and BON07 graded, statistics updated
3-02 10:15 assignment BON09 posted on Gradescope. Due Tue, March 7 at 23:00. There will be no ORD09 set.
2-23 19:25 assignments ORD08 and BON08 finalized on Gradescope. Due Mon, Feb 27 at 23:00.
2-23 19:00 Course material of 2-23 class and exercises posted.
2-19 6:55 Course material of 2-16 class and first batch of exercises posted. Due Mon, Feb 27, 23:00.
2-16 Thu 5:00 assignments finalized on Gradescope. Due Mon, Feb 20 at 23:00.
2-16 Thu 2:05 first batch of each assignment posted on Gradescope. More to follow. Due Mon, Feb 20 at 23:00.
2-09 Thu 18:10 assignments posted on Gradscope. Due Mon Feb 13 at 23:00.
2-07 Tue 18:40 Course material of 2-07 class and first batch of new exercises posted. Due Mon, Feb 13, 23:00.
2-04 Sat 8:15 assignments posted on Gradscope. Due Mon Feb 6 23:00.
2-03 Fri 9:15 Course material of 1-31 class and last batch of exercises due Feb 6 posted.
1-30 Mon 13:15 Course material of 1-26 class and first batch of exercises posted. Due Mon, Feb 6, 23:00.
1-27 Fri 3:00 assignments posted on Gradscope. Due Mon Jan 30 23:00. Also, 1-26 "material covered" posted.
1-25 Wed 23:50 Course material and first batch of exercises posted. Due Mon, Jan 30, 23:00.
1-20 Fri 15:25 material of yesterday's class and exercises posted
1-19 Thu 3:15 Course material and first batch of exercises posted. Due Mon, Jan 23, 23:00.
1-17 0:40 The LinAlg book has been updated. Look for the date January 16, 2023 on the front page. If you see an earlier date, you are looking at an earlier, cached version. Please refresh your browser. If this does not help, clear your browser's cache or try another browser.
REMEMBER: office hours/tutorial/problem session every Friday 16:30-18:00 in JCL 298
1-10 Wed 4:15 first batch of exercises posted on the course homepage. Click "HOMEWORK, material covered" on the banner.
1-05 Thu 23:13 assignments posted on Gradscope. Due Mon Jan 9 23:00
1-05 21:50 Course material and second batch of exercises posted. Due Mon, Jan 9, 23:00.
1-05 Thu 19:30 inconsistent numbering of previously posted exercises fixed
1-04 Wed 19:00, 1-05 3:00 Course material and first batch of exercises posted. Due Mon, Jan 9, 23:00.
Please send email to the instructor by Thursday, January 5, with answers to these questions, even if you are only auditing, or answered a similar questionnaire in an earlier course 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.
There is an official Canvas site for the course. Sign up under the CMSC 27410 course number.
Class meets TuTh 12:30 - 13:50 in Ry-276.
Office hour and discussion session Friday 16:30 - 18:00 in JCL-298
In the email addresses below, (uc) refers to "uchicago(dot)edu" and (g) refers to "gmail(dot)com".
Instructor:
Laszlo Babai (pronouns: he/him/his)
email1:
laci(at)(uc)
email2:
lbabai(at)(g)
Please use both email addresses for messages to the instructor.
Each has its advantages and disadvantages. Begin the Subject
of your message with the word Combinatorics.
TA: Theodoros (Theo) Papamakarios (pronouns: he/him/his)
email: [lastname](at)(uc)
Classes of combinatorial structures (graphs, hypergraphs), objects with high regularity (Latin squares, block designs, especially Steiner triple systems and finite projective planes), their existence and construction. Fundamental parameters of hypergraphs (matching number, covering number, chromatic number, independence number), linear relaxation, duality. Extremal combinatorics, probabilistic combinatorics, linear algebra methods in combinatorics. Counting and estimation, asymptotic notation. Generating functions. The Permanent Inequality.
Mathematical puzzles will pepper the course.
Prerequisites: Basic linear algebra, calculus, and the basics of discrete mathematics, along with a degree of mathematical maturity and an interest in creative problem solving.
We shall not follow any particular text, so your attention to the classes and to this website is important.
A considerable portion of the material is covered in this
unfinished book:
Online lecture notes: instructor's "Discrete Mathematics" lecture notes (preliminary, incomplete drafts):
Chapter 7 ("Finite Probability Spaces") of the mini version has been greatly revised and is available as standalone set of notes:
The prior courses by the instructor titled "Discrete Mathematics" and "Honors Combinatorics" are good sources of relevant exercises.
The following notes may also be helpful:
John Loeber's
2014 class notes.
Caveat: these notes have not been checked by the instructor
and contain errors.
There will be frequent postings on this course website. Please check this website frequently.
A wonderful general introduction to combinatorics is the book
Advanced reading:
These three classics by the masters are delightful resources for deeper study:
Basic introduction:
This is a popular undergraduate text:
Kenneth H. Rosen: Discrete Mathematics and its Applications (n-th edition, n=2,3,4,5,...)
Homework is due online each Monday by 23:00.
IMPORTANT. Homework must be typeset in LaTeX and submitted online on Gradescope as a PDF file. Hand-drawn figures may be attached. If you are not familiar with LaTeX, you may ask the instructor for one week's grace period.
If you suspect an error in an exercise or anything else posted on this website, or something looks suspicious (e.g., the problem seems too easy for the number of points offered), or you are uncertain of the degree of detail required, please let the instructor know right away (by email). If the error is of a trivial nature (e.g., the statement is false for $n=0$ but true otherwise), you are expected to discover the error, correct the problem, and solve the corrected problem. In any case, please do warn the instructor.
If you have difficulty interpreting some material stated in class or an exercise (e.g., you are uncertain about the meaning of the notation), let the instructor know by email without delay.
Solutions to Challenge problems don't earn you credit toward your grade but they do earn you the instructor's attention, in addition to giving you valuable experience. If you later ask me for a letter of recommendation for graduate study, the first thing I will ask, which challenge problems did you solve.
On Gradescope you will find a brief description of each problem. These descriptions do NOT constitute the problem statements. You find the authentic statement of each question on the course homepage. (Click "HOMEWORK and material covered" on the banner.)
Please use the LaTeX homework template (click on the navigation bar on the top) to typeset your solutions. Make sure to put in your name, and for each solution, complete the entry "Sources and collaborations" (see "Policy on collaboration and internet use" below). (Write "None" if you did not use sources and did not collaborate.)
Please upload one PDF file per "assignment," i.e., two PDF files per week: one for the "ORD" assignment and one for the "BON" assignment.
Please typeset each solution on a separate page (but parts (a), (b), etc. of the same problem can go on the same page).
IMPORTANT: As you upload your PDF file,
Gradescope will ask you to assign page numbers to each solution.
If a solution extends over more than one page, you need to assign
each of those pages to the problem.
Failing to accurately assign the pages
causes significant extra work for the graders.
If you do not submit a solution to a problem, please assign "page 1"
(the cover page) to the problem.
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(s)). You may share ideas, not entire solutions. Sharing .tex source files is prohibited. DO NOT COPY someone else's solution. If you got some help, understand the ideas discussed and give your own rendering.
Posting a solution to an assigned problem on the web without the instructor's permission is a serious academic offense.
Use of the Web. You may look up pertinent general information on the web but not the posted solution to a problem that is essentially identical with the problem assigned.
Do NOT SEARCH for a solution to the specific problem assigned. If you found a closely related website, okay, but include the link in your homework submission. DO NOT COPY: understand, then write your own version without looking at the source.
Unfortunately, by widespread abuse of the web, you can find solutions to the great majority of the most elegant and instructive problems on the web. Use the web with restraint. The way to learn matematics is by discovering it through solving problems. If you look up the solutions, you are denying yourself the experience of discovery.
Note that you can set your name in your Zoom profile, so you don't have to go with whatever was assigned. You may include your preferred pronouns after your last name; you'll see an example of me doing this in class. I recommend that you follow this practice for multiple reasons. If you set a name that can't be easily matched to the name on record with the University, please let your instructor know.