05-09 3:20 iPad notes for all previous lectures and problem sessions posted. Click SLIDES on the banner.
04-26 1:00 ORD06 and BON06 posted on Gradescope. Due to the late posting, I moved the deadline to Tuesday, April 30, 23:00.
04-20 20:40 iPad notes for all previous lectures and problem sessions posted. Click SLIDES on the banner.
04-16 9:20 iPad notes for all previous lectures and problem sessions posted. Click SLIDES on the banner.
04-05 10:00 Assignments ORD03, BON03 posted on Gradescope
03-28 5:00 Assignments ORD02, BON02 posted on Gradescope
03-21 14:00 Today's iPad slides have been proofread and posted. Click SLIDES on the banner.
03-20 14:15 First batch of HW problems posted. Click "HOMEWORK, material covered" on the banner.
03-19 23:30 Today's iPad slides have been proofread and posted.
REMEMBER: problem session
every Friday 16:30-17:20 Room: Ryerson 276
First session: Friday, March 22.
The problem session is followed by an office hour.
Homework is an integral part of the course material, and
the problem sessions provide the most important feedback
on homework. So while the problem sessions are not
mandatory, they are strongly recommended; please check
with the instructor if you have a scheduling conflict.
There will be frequent postings on this course website. Please check it frequently, and always REFRESH your browser.
Homework problems will be posted on this website. Homework is due every Monday by 23:00, submitted online on Gradescope.
The instructor places an emphasis on interaction with the students. Student responses to the instructor's questions will be given in private on Zoom "chat."
Outside class, email is the best way to communicate with the instructor. (See the email addresses below.)
Class schedule
e-mail: laci(at)u.e. (expand abbreviation) and lbabai(at)[Google's mail service]
When sending me a message, please use BOTH email addresses to help ensure that I see it. I have been experiencing a variety of uncertainties with email.
Office hours: The weekly problem sessions (Fri 4:20-5:20) will be followed by an office hour. Please send me email if you wish to have a one-on-one appointment.
Please send email to the instructor with answers to these
questions,
even if you are only auditing the class,
did not register, or have an unusual status. Your answers
to these questions will help me to better plan the course.
Please write "CMSC 27410 data" in the subject
(even if you registered or plan to register under
one of the other two course numbers).
Please read the questions carefully and do not miss parts of them.
This is a proof-based course. It requires familiarity with mathematical proofs and certain degree of mathematical maturity. The course involves mathematical problem solving.
The subject includes classes of finite 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.
While this course will not be identical with the Winter 2023 course by the same title and course numbers, the overlap will be significant, and a most valuable source of information about the course content is the Homework, material covered section of the 2023 course website.
We shall not follow any particular text, so your attention to the classes and to this website is important. Your primary text will be your course notes. So please make sure you don't miss classes. If you do, try to discuss the class with a peer and copy their notes.
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 a standalone set of notes:
Recommended reading
A delightful general introduction to combinatorics is the book
Advanced reading
These three classics by the masters are beautiful 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,\dots$)
Unfortunately the graph theory terminology in this book significantly differs from ours and from common usage. The most important differences are listed in DMmini, Chapter 6.1 ("Graph Theory terminology").
There are online handouts for the following subjects.
Grading scheme Homework 85% Class participation 15%
Homework problems are posted on this website;
Please make sure to refresh your browser to
get the latest version of the homework problems.
The problems are organized into weekly assigments on Gradescope.
Errors may occur, both in class and in the posted version of the problems. Please recheck the website, especially if you suspect an error.
If you find an error or something looks suspicious in an assignment (e.g., it seems too easy or it has already been discussed), please notify the instructor (by email) as soon as possible. This will help you and everyone else in class. 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.
Homework help. If you encounter difficulties with an assigned problem, you may contact the instructor by email.
While solutions to Challenge problems don't earn you credit toward your grade, 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 the use of web sources and AI tools" below). If you did use AI tools, mention it in "Sources and collaborations" and send me a detailed report by email. (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 strictly prohibited. DO NOT COPY someone else's solution. If you got some help, understand the ideas discussed and give your own rendering. Violation of these rules constitutes academic dishonesty and will be deal with accordingly.
Posting a solution to an assigned problem online without the instructor's permission is a serious academic offense.
Use of the Web. You may look up pertinent general information online but not the posted solution to a problem that significantly overlaps 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 online to the great majority of the most elegant and instructive problems. Use the web with restraint. The way to learn matematical subjects (such as the Theory of Algorithms) is by discovering it through solving problems. If you look up the solutions, you are denying yourself the experience of discovery.
In any case, if you use a web source, acknowledge the source, include the URL at the beginning of your solution. If the URL is long (longer than 15 characters, excluding the "https://" prefix), please also send it by email to the instructor (because it is not possible to cut and paste from the Gradescope site).
Using AI tools. At this point I am not prohibiting this, but this policy may change. For now, if you do use AI tools, acknowledge it at the beginning of the solution, and send me, by email, a detailed report of what exactly you were using, and how. The report should be sufficiently detailed to allow me to reproduce your experiment. Tell me about your experience and your opinion about the pros and cons of using these tools.
Note that you can set your name in your Zoom profile, so you do not have to go with whatever has been assigned. If you set a name that cannot be easily matched to the your name on record with the University, please let your instructor know.