06-01 05:05 Class notes posted for classes 05-26 discussion session and 05-27 lecture (last class). Click "Class notes" on the banner. REFRESH. Notes of 05-25 lecture updated (Fekete's Lemma corrected). EXERCISES and MATERIAL COVERED section of 05-25 updated (Shannon capacity material added)
05-26 05:15 Class notes posted for recent classes: 5-19, 5-20, 5-25.
05-23 04:10 Statistics of HW1-6 posted. Click "Statistics" on tha banner.
05-18 20:40 First batch of HW due May 24 posted.
05-18 18:45 Paley graphs and tournaments handout posted. Click "HANDOUTS" on the banner.
05-13 13:00 Today's class notes posted. Click "Class notes" on the banner.
05-13 08:30 Final week's schedule posted just below this section. Final homework due: Thu June 3, 23:00.
05-11 12:30 Today's class notes posted. Click "Class notes" on the banner. "Exercises, material covered" also posted; includes third batch of exercises due May 17. Make sure to REFRESH your browser.
05-10 22:10 Second batch of Class #12 material and exercises posted. Due May 17. Make sure to REFRESH your browser.
05-06 11:40 Today's class notes posted.
05-05 22:20 Assignments due Monday posted on Gradescope.
05-05 18:55 Notes of today's discussion session posted (click "Class notes" on the banner). Attendance was very low; you missed important feedback on assigments.
03-31 04:15 First set of assignments, called ORD1 and Bonus1, posted on Gradescope. Due Monday, April 5 at 11pm. Make an early start, practice using the Latex template. Read the template also for its math and its LaTeX usage. Carefully read the policy on collaboration and web sources (on this page). Make sure to link pages to problems when uploading your solutions on Gradescope. Please report errors and omissions.
03-30 13:10 Today's class notes posted. Click "Class notes" on the banner.
Instructor: László Babai
Final week's schedule
Class schedule
Websites: Go to
Canvas, login, and then
Click Zoom to access the class
Click Gradescope to access the assignments and the video recordings
of the classes
For everything else, check out the links on the banner on this website. Not all tabs on the banner are operational yet. If you think a link should already work but it does not, please send email to the instructor.
Please send email to the instructor with answers to these questions, even if you are only auditing the class, did not register, have an unusual status, or you answered a similar questionnaire in another course given by the same instructor. Your answers to these questions will help me better to plan the course. Please write "Graph Theory data" in the subject.
This is a heavily proof-based course, so the key prerequisite is that you be comfortable with mathematical formalism, proofs, and the discovery of proofs on your own. Most problems to be assigned will ask you to prove something. The focus of the course is on theory, although application areas will occasionally be mentioned.
Formal prerequisites: analysis (Math 20400 or higher) or Discrete Mathematics (CMSC 27100 or higher) or instructor's consent. In particular, facility with limits, the basics of counting, and basic linear algebra (including the Spectral Theorem) are expected. Some familiarity with probabilities helps but is not assumed; the course will briefly review the concepts of discrete probability. Material for the review of linear algebra will also be provided.
e-mail:
laci(at)cs(dot)(university postfix) (do not miss the "cs")
and
lbabai(at)[Google's mail service]
Contact: e-mail.
Please send any messages to both email addresses; each address
has its advantages and disadvantages.
Please do NOT send me messages via Canvas, I do not read such messages.
TAs: Zihan Tan e-mail: [firstnamelastname](at)u.e
and Fernando Granha e-mail: [lastname](at)u.e
Class notes (slides and iPad notes) will be posted on this webite. Video recordings of lectures and problem sessions will be available on the Canvas/Panopto site.
The instructor places an emphasis on interaction with the students. The primary method of feedback during class is zoom's private "chat" feature. Please make sure you do NOT broadcast your "chat" messages to the class, to permit everybody else to think and send their independent answers.
Outside class, email is the best way to communicate with the instructor.
Your primary text will be the course notes posted on this website, along with the explanations given in class, so please make sure you don't miss classes.
WARNING: in these and all other references, watch out for possible discrepancies in terminology. Please use the terminology we use in class, reflected in DM (below).
Recommended printed references:
J. Adrian Bondy and U. S. Rama Murty:
Graph Theory with Applications.
(Highly recommended: a classic text. It is a "first course"
on the subject but includes some substatial proofs)
Print copy recommended but you may also be able to find it online.
Gary Chartrand and Ping Zhang:
A First Course in Graph Theory
(This is a basic intro text with many exercises)
Additional printed references:
Jiří Matoušek, Jarik Nešetříl:
Invitation to Discrete Mathematics,
published by Oxford University Press,
ISBN# 098502079.
(a wonderful introduction for the mathematically inclined)
László Lovász:
Combinatorial Problems and Exercises.
(This is a treasure trove of advanced problems that lead to central
theorems. Written by the master to whom we owe much of the
modern theory; also a great expositor for the advanced student.)
Reinhard Diestel: Graph Theory. Springer, 1997 (graduate text, research-level)
Douglas B. West: Introduction to Graph Theory. Prentice - Hall 1996, 2001.
Kenneth H. Rosen: Discrete Mathematics and its Applications. (n-th edition, n=2,3,4,5,...) (a very basic introduction)
Online references:
Tero Harju "Lecture Notes on Graph Theory" (2007) (introductory)
Lex Schrijver: "Advanced Graph Theory" (hard)
Online resources by the instructor
"MR20" -- Introduction to Mathematical Reasoning via Discrete Mathematics (basic course, Fall 2020)
"GR19" -- Lecture notes for the 2019 edition of this class. While the material will not be identical, there will be a large overlap. The detailed lecture notes of that class are worth studying.
"DM" -- Discrete Mathematics Lecture Notes. Skip Sections 2.2 and Chap. 7. DM Sec 2.2 is replaced by ASY (below) and DM Chap. 7 is replaced by PROB (below).
Problem sheets from instructor's 2012 REU course for rising 2nd-years (including linear algebra problems and "puzzle problems")
"ASY" -- Asymptotic Equality and Inequality (lecture notes, replaces DM Sec 2.2)
"PROB" -- Finite Probability Spaces (lecture notes, replaces DM Sec 7)
"LinAlg" -- Discover Linear Algebra (online text)
Puzzle problems for challenge and fun
There are additional online handouts for the following subjects.
Grading will be based on weekly homework assignments, class participation via "chat," and possibly tests. Homework assignments appear on Gradescope and consist of Ordinary and Bonus problems posted on this website (click "EXERCISES, material covered" on the banner). For more information, go to the Categories of exercises section below. Class participation will account for 15% of the course grade. Those who registered under the graduate course number (CMSC 37530) will be graded on a higher scale.
Unless otherwise stated, all homework is due next Monday at 11pm.
Homework problems are posted on this website. They are organized into weekly assignments on Gradescope. You will need to upload your solutions on Gradescope by the deadline stated (usually Monday 11:00pm). Problems may be updated. Please make sure to refresh your browser to get any updates of the homework problems. You may also need to clear your browser's cache to avoid reading an older, cached version.
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).
Such reports will enhance your class participation score.
Trivial errors. 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. Merely stating that the problem is in error and giving an easy counterexample will not earn you the credit.
Homework help. Take advantage of the TA's office hours. You may also contact the instructor by email and ask for a hint. See also the Policy on collaboration and Policy on web sources below.
Collaboration on current homework is discouraged but not
prohibited. If you collaborate on a problem, acknowledge this
at the beginning
of your solution: give the name(s) of the collaborator(s),
state the nature and extent of the collaboration. A person
to whom you give a hint counts as a collaborator
even if you do not receive any reciprocal help. The LaTeX homework
template gives examples of such acknowledgments.
Acknowledged collaboration on homework may incur a minor penalty.
Collaboration may involve discussing ideas, giving/receiving a hint.
You need to understand the ideas discussed and give your own rendering.
Sharing a solution or a significant portion of a solution
before the deadline is not permitted and may incur heavy
penalties on both parties.
You may ask the instructor by email for a hint; there is no penalty
for doing so. Also, take advantage of the TA's office hours.
You may use web sources to study material related to the course. Beware of the variations in terminology.
Looking up solutions to homework problems on the web
is strongly discouraged but not prohibited.
It is counterproductive; solving the problems by yourself
is a key part of learning. Without this experience,
your knoweldge will be superficial. You may ask the
instructor for a hint; there is no penalty for doing so.
If you consult a web source that explains the solution
to a homework problem or a closely related problem, you are
required to state the URL at the beginning of your
solution. Acknowledged use of a web source
may incur a small penalty.
Unacknowledged use of a web source counts as
academic dishonesty and may incur a
heavy penalty ranging from zero points for the given
problem to failing the course.
Copying from a web source is strictly prohibited
and is subject to heavy penalties. If you do use a web source,
understand it, close it, wait at least 30 minutes, and
then give your own rendering of the solution.
Soliciting a solution to a homework problem on the web is an extreme violation of the standards of academic integrity and may incur disciplinary action in addition to failing the course.
Note that you can set your name in your Zoom profile, so you do not have to go with whatever has been assigned. You may include your preferred pronouns after your last name. I recommend that you follow this practice for multiple reasons. If you set yourself a name that cannot be easily matched to your name on record with the University, please let your instructor know.
You are strongly encouraged to attend the classes synchronously and be an active partiticipant. Our Zoom class meetings will be recorded and saved to the cloud to allow students enrolled in this class to review it and to allow students enrolled in this class who cannot participate synchronously to benefit from the class. It is illegal for anyone other than the instructor to record the class or to post a recording or to pass it on to anyone. The recording is intended to be available only to the participants of this class and will not be available after the quarter ends. However, I am not in the position to prevent illegal activity. If you have FERPA concerns, please mask yourself accordingly, e.g., by turning off the video and using an alias.