What's new?

To find out what's new, make sure you press your browser's REFRESH button.

June 10, 10pm complete HW statistics posted

June 9: all HW grades released

June 2, 2:30pm Slides of June 2 class debugged and posted, along with synopsis. (Click "Slides" on the banner.)

June 1, 5:45pm HW statistics posted (click "Statistics" on the banner)

Last problem session: Wednesday, June 3.
* LAST CLASS:   Thursday, June 4 *

May 30, 5:20am Last set of homework assignments posted. Due dates: Tuesday, June 2, and Wednesday, June 3, at 11:59pm. There will be no tests/exam.

May 29, 7:45am Slides of May 28 class debugged and posted, along with synopsis. (Click "Slides" on the banner.)

May 26, 11:30pm Slides of May 26 class debugged and posted, along with synopsis.

May 16, 4am Log-asymptotics of products of factorials and The greatest term in Dobiński's formula handouts posted.

May 13, 3:30pm Slides of May 12 class posted.

May 3, 8pm Hypergraph Cover handout posted. It illustrates the Probabilistic Method of proving the existence of certain objects without actually constructing them. The handout includes three proofs of the upper bound on hypergraph cover stated in Exercise 4.112.

Apr 29, 10:30pm Order Statistics handout posted, gives intuitive solution to Ex. 3.45.

Apr 28, 5pm Slides of today's class posted, with synopsis. Click "Slides" on the navigation bar.

Apr 18, 9:30pm Slides and notes of 2nd week's classes posted on this website. Click "Slides" in the navigation bar. Synopsis of slides and notes has been added.

Apr 17 Videos of 2nd week's classes posted on Canvas/Panopto/week2.

Apr 3: section "Zoom and privacy" added, paragraph on College P/F policy added to section "Grading, tests." (Click section titles in the navigation bar above.)

THIS PAGE IS UNDER CONSTRUCTION

Course information

There is an official Canvas site for the course. Sign up under the CMSC 27410 course number.

Class meets TuTh 12:30 - 1:50pm online via zoom.
Discussion session Wed 4:30 - 5:20pm via zoom. The discussion sessions are required part of the course. Selected exercises will be discussed during these sessions, and the quizzes will also be held during this time slot.

There will be three quizzes. Dates TBA.

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)cs(dot)(uc)   (don't miss the "cs")
    email2: lbabai(at)(g)
Please use both email addresses for messages to the instructor.

         TA1:   Theodoros (Theo) Papamakarios (pronouns: he/him/his)     email: [lastname](at)(uc)
         TA2:   Tiago Royer (pronouns: he/him/his)                      email: [lastnamefirstname](at)(g)

Course description

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.

Texts, online sources

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:

• László Babai and Peter Frankl: Linear Algebra Methods in Combinatorics

• László Babai: Discover Linear Algebra

Online lecture notes: instructor's "Discrete Mathematics" lecture notes (preliminary, incomplete drafts):

• mini version (DMmini)
• expanded version (DMmaxi)

Chapter 7 ("Finite Probability Spaces") of the mini version has been revised and is available as standalone notes:

• Finite Probability Spaces

• Order Statistics

• Hypergraph Cover

• Asymptotic inequality

• Log-asymptotics of products of factorials

• Euclid's algorithm and multiplicative inverse

You may want to check out these Puzzle problems for challenge and fun

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

• Jiři Matoušek, Jaroslav Nešetříl: "Invitation to Discrete Mathematics." Oxford University Press, ISBN 098502079.

Advanced reading:

These three classics by the masters are delightful resources for deeper study:

• László Lovász: "Combinatorial Problems and Exercises." 2nd ed. AMS Chelsea Publ., ISBN 978-0-8218-4262-1
• Noga Alon and Joel H. Spencer: "The Probabilistic Method." Wiley, ISBN 0-471-53588-5
• Jacobus H. van Lint and Richard M. Wilson: "A Course in Combinatorics." Cambridge University Press, ISBN 0-521-00601-5

Basic introduction:

This is a popular undergraduate text:

Kenneth H. Rosen: Discrete Mathematics and its Applications (n-th edition, n=2,3,4,5,...)

Slides

The videos of the lectures are posted on the Canvas/Panopto site.
Click here for the annotated slides and notes presented in the lectures and problem sessions.

Questionnaire

Please send email to the instructor with answers to these questions, even if you answered the 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.

• Your name
• Your geographic location during this term (Hyde Park, elsewhere in Chicago, city/state/metropolitan area), time zone
• Your field, area of specialization, and status at the university (e.g., "3rd year math major with minor in economics," or "2nd year TTIC PhD student specializing in pattern recognition," or "PSD Masters student specializing in genetics"). If you are a PhD student, who is your advisor?
• Do you expect to graduate this quarter?
• Under which course number did you register (CMSC-27410, Math-28410, or CMSC-37200)?
• What type of grade do you seek (quality grade [A-F] or P/F) or just auditing? (You can change your mind about this later.)
• Are you fulfilling a requirement with this course? 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).
• In what courses did you study (a) linear algebra and (b) probability theory?
• If the course work includes timed tests, will you require special accommodations for the tests? If yes, please elaborate.
• Do you have access to the technology needed to succeed in your Spring quarter? In particular, do you have reliable internet access, laptop, etc.?

Credits

• This course offers both undergraduate (CMSC 27410 or Math 28410) and graduate (CMSC 37200) credits.
• Any student, including undergraduates and Masters students, can seek graduate credit. Consult with the instructor before making that choice.
• Undergraduates, Masters students, and non-math PhD students can seek undergraduate credit.
• If a CS PhD student wishes to apply for the joint Math-CS PhD, an undergraduate credit for this course will not count toward their degree requirements.
• Those who seek graduate credit will need to do more work and of higher quality than those who seek an undergraduate credit.
• I will offer a quality grade [A-F] to everyone who does not specifically ask for P/F, even if the College mandates P/F grading for this term. In that case, those quality grades will not show on your transcript. However, if you ask me for a letter of reference in the future, then I will include in that letter the quality grade you received.
• Exceptional work may be rewarded by a grade of A+. This again will not show on your transcript, but I will mention it in a letter of reference you may ask me to write.

Grading, tests

• There will be no final exam for graduating seniors. For those who do not graduate, the final exam will be optional (see below).
• Grades will be based on three timed quizzes (7% each), homework (75%) and class participation (4%) except in case the optional final exam is chosen (see below). (Class participation includes answering the Questionnaire.)
• During the last week of classes, every student will be offered a tentative course grade (a quality grade). If you choose the P/F option, then "P" requires a C- or higher.
• If you accept your tentative grade then that will be your course grade.
• If your tentative grade is C- or higher and you do not accept your tentative grade then your options depend on whether you are graduating.
  • If you are graduating then you get a P.
  • If you are not graduating then you can choose between a P, and I (incomplete, must be completed within a year, if not completed, your tentative grade becomes your grade), or taking the final exam.
  • If you choose to take the final exam, the final exam will account for 50% of your grade but in no case will your grade be lower than your tentative grade. You can still choose "P" if you don't like the quality grade you would be getting after the final. In other words, there is no risk for you in taking the final exam. Even those whose tentative grade is "A" may want to take the final just for the challenge (and possibly to advance to A+).
  • While you can choose P/F up to the last minute in this course, a "P" will generally not count toward degree requirements. However, given the abnormal circumstances in this quarter, the College has special P/F policies in place for this quarter. PSD Dean Olinto communicated the following to faculty.

    "For courses taken to fulfill the requirements of a Major or Minor in the Physical Sciences Division, students in the College may request to take up to two courses as pass/fail with the consent of their instructors. Students must then submit a petition to their department to have those courses count toward Major/Minor requirements by Friday of Week 9. For more information about grading options in the Core and electives, view the communication from Dean of the College John Boyer and Dean of Students Jay Ellison."

    In this course, you automatically have the consent of the instructor to choose P/F. However, if you choose that option and wish the course to count toward requirements, note the deadline for your petition: Friday, June 5.

Proofs discussed in class are required; exercises stated in class are helpful.

Rules on HOMEWORK

Homework is due each Tuesday before class.

IMPORTANT. Homework must be typeset in LaTeX and submitted as a PDF file. Hand-drawn figures may be attached.

If you find an error in an assignment or anything else posted on this website, or something that looks suspicious (e.g., the assignment seems too easy for the number of points offered), or you are uncertain of the degree of detail required, please let the instructor know (by email). If you are the first to point out an error, you may receive bonus points.

Categories of problems.

• "DO" exercises: you are expected to solve them but do not hand them in. Most of them are meant to check your understanding of the concepts; they are due (to be solved) by the next class. Some are creative; they are marked by an asterisk:   DO*. Solve them within ten days.
• "HW" HOMEWORK problems. Prepare the solution in LaTeX, submit it as a PDF file (with hand-drawn figures attached if needed). They are due the next Tuesday, before class.
• "B" BONUS problems: they count as HW to those who seek graduate credit (CMSC 37200), and as extra credit problems (not required but it adds to your score) for those who seek undergraduate credit (CMSC 27410 and Math 28410). Same deadline.
• "CH" CHALLENGE problems have no deadline unless a deadline is announced, but they expire once 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.

  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, the first thing I will ask, which challenge problems did you solve.

Policy on collaboration and internet use

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 essentially the same problem as the one assigned.

Do NOT SEARCH for a solution to the specific problem assigned. If you found a closely related website, include the link in your homework submission. DO NOT COPY: understand, then write your own version without looking at the source.

Zoom and privacy

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.

Our Zoom class meetings will be recorded and saved to the cloud to allow students in this class to review the discussion, and especially to allow students who can't participate the opportunity to benefit from class. It is not my intention that these recordings will be available to anyone but class participants, nor that they will be available after the quarter, but I don't have control over what others will do. If you have FERPA concerns, please mask yourself accordingly, e.g., by turning off video and using an alias.

View the instructor's course material from previous years

Return to the Department of Computer Science home page

Go to top