CMSC 27530 / Math 28530 -- Honors Graph Theory
Spring 2023
What's new
| Health
| Questionnaire
| Course info
| Texts, online sources
| Grading
| HW rules
| Categories of exercises
| Gradescope
| Policy on collaboration and web sources
| Zoom and privacy
| Puzzles
| HOMEWORK, material covered
| LaTeX HW template
| Statistics
| prior years
THIS PAGE IS FREQUENTLY UPDATED
For the latest information, make sure to
REFRESH your browser.
Recommended lecture next Tuesday by UChicago alum:
an application of graph theory to the law.
Speaker: Moon Duchin
Title: A spanning tree goes to court
Date/Time/Place: Tuesday, May 23, 3:30pm, Kent 120
See full announcement here.
05-24 6:00 Statistics of HW01-07 posted. Click "Statistics"
on the banner
05-21 23:10 Statistics of HW01-06 posted.
05-15 11:10 Statistics of HW01-05 posted.
05-10 18:45 Assignments ORD08, BON08 posted on Gradescope.
Due May 15.
05-02 20:50 Assignments ORD07, BON07 posted on Gradescope.
Due May 8.
04-26 23:58 Assignments ORD06, BON06 posted on Gradescope.
Due May 1.
04-17 4:00 A new set of exercises, not covered in class,
has been posted under "Class #08" on the "Homework and
Material Covered" page, due April 24, except where otherwise
stated. The exercises cover orthogonal polynomials,
including their real-rootedness, and questions from
spectral graph theory, chromatic graph theory, extremal
graph theory, and the theory of random graphs.
03-22 13:00 First assignments (ORD01, BON01) posted
on Gradescope. Due Monday, March 27, at 23:00 on Gradescope.
03-21 19:50 First batch of homework problems posted.
Due Monday, March 27, at 23:00 on Gradescope.
Click "HOMEWORK, material covered" on the banner.
IMPORTANT INFORMATION FOR THOSE SEEKING CONSENT
FOR ADMISSION TO THIS COURSE. Please go to the
Questionnaire below.
There will be frequent postings on this course website.
Please check it frequently.
REMEMBER: office hours/tutorial/problem session
every Friday 16:30-17:20, room TBA
This is an in-person class in a crowded classroom.
I encourage everybody to wear a mask for your own
sake and everyone else's, including your instructor's
who is at hightened risk.
(I will not wear a mask while speaking, at least for now, because
the mask would impede comprehension of what is being said.)
We use the "chat" feature of Zoom in the classroom so
you can privately communicate
your comments to the instructor, without taking your mask off.
I also encourage everybody who is eligible to get a
bivalent Covid booster. (These are designed to offer
protection not only against the original virus but also against
the omega variants.) Please remember that even with the booster
you can get the virus (but your illness is likely to be much milder)
and you can spread the virus even while you have no symptoms.
-- Flu vaccine is also strongly recommended.
Please send email to the instructor with answers to these questions,
even if you are only auditing, or you have
answered a similar questionnaire in an earlier
course by the instructor, or have an unusual status.
The purpose of these questions is twofold:
(a) If you seek the instructor's consent to be
admitted to this class, please respond to the questionnaire
as soon as possible; your answers will be my basis to determine
whether this course is appropriate for you.
Please write "graph theory consent request" in the SUBJECT.
(b) To all students regardless of admission status,
your answers to these questions will help me better to plan the course.
If you have already been admitted, please write
"graph theory data" in the SUBJECT.
Please respond no later than by Thursday, March 23,
and preferably earlier. The instructor lists two email addresses (below),
please use both email addresses for messages to the instructor.
IMPORTANT. Please observe the above instructions regarding the
SUBJECT of the message and the email ADDRESSES to be used.
If you don't carefully follow these instructions,
I may miss your message (or misclassify your message)
among the deluge of messages I am receiving.
- (a) Have you already been admitted to this class, or
(b) do you seek instructor's consent for admission?
- Your name
- Your field, area of specialization,
and status at the university (e.g.,
"3rd year math major with minor in economics," or
"2nd year CS/TTIC PhD student specializing in pattern recognition,"
or "2nd year UChicago MPCS student in the Pre-doc program
specializing in HCI").
If you are a graduate student, who is your advisor?
- Do you expect to graduate this quarter?
- Under which course number did you register or do you intend
to register (CMSC-27530 or Math-284530)?
- 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. Auditing is not
encouraged for two reasons: possible overcrowding of the classroom,
and because you learn math by doing it, not just
listening to it.)
- 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? (Note: this course is proof-heavy.)
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 have you studied (a) linear algebra
(b) probability theory (c) discrete mathematics?
- If the course work includes timed tests,
will you require special accommodations for the tests? If yes,
please elaborate.
- Do you have a laptop and reliable access to the internet?
- Are you familiar with LaTeX? You will need to typeset your
solutions to the homework exercises in LaTeX. Those not familiar
wih LaTeX get one week grace period.
Go to top
There is an official Canvas site for the course.
Sign up under the CMSC 27530 course number.
Class meets TuTh 12:30 - 13:50 in Ry-251.
Discussion session Friday 16:30 - 17:20, followed by office hour.
Room TBA. The main subject of the discussion session is solution to
homework problems. Attending the discussion session is strongly
recommended but not mandatory.
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 Graphs.
TA: Theodoros (Theo) Papamakarios (pronouns: he/him/his)
email: [lastname](at)(uc)
TA: Derek Zhu
email: [XYYYZ where X=initial YYY=last name Z=8](at)(uc)
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.
Course outline.
Finite probability spaces. Asymptotic notation. Review
of basic linear algebra.
Graphs, isomorphism, automorphisms, counting.
Basic structures in graphs (paths, cycles, matchings, coverings,
independent sets and cliques, vertex coloring, edge coloring),
trees, bipartite graphs, planarity. Network flows.
Basic parameters of graphs (connectivity, diameter, independence number,
chromatic number). Ramsey's theorem for graphs, Ramsey numbers.
Random graphs. The probabilistic method. Universality.
Explicit constructions. Weil's character sum estimates.
Spectral graph theory. Spectral bounds on clique number,
chromatic number. Expansion. Strongly regular graphs.
Orthogonal polynomials. The matchings polynomial. Reality of the roots.
Directed graphs (digraphs), tournaments.
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.
Go to top
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 sources,
watch out for possible discrepancies in terminology.
Please use the terminology we use in class, reflected in DMmini (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 substantial 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 the 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.)
- Noga Alon and Joel H. Spencer: "The Probabilistic Method."
Wiley, ISBN 0-471-53588-5
(beautifully written, a must for advanced study
in combinatorics, including graph theory)
- Jacobus H. van Lint and Richard M. Wilson:
"A Course in Combinatorics."
Cambridge University Press,
ISBN 0-521-00601-5
(a wonderful book that presents multiple proofs of
central results that show different angles and generalizations)
-
Reinhard Diestel: "Graph Theory." Springer, 1997 (graduate text,
research-level)
-
Douglas B. West: "Introduction to Graph Theory."
Prentice - Hall 1996, 2001.
Online references:
Online resources by the instructor:
-
An online IBL-style introduction to linear algebra is offered in
an unfinished manuscript by the instructor:
Discover Linear Algebra (LinAlg)
(IBL = Inquiry-Based Learning: students are presented with definitions
and theorems, and are expected to fill in the proofs themselves.)
Two versions of the instructor's Discrete Mathematics lecture notes
are available:
-
mini version (DMmini)
Check that you see "Last updated January 5, 2023"
under the title. Skip Sections 2.2
and Chap. 7. DMmini Sec 2.2 is superseded by ASY (below) and
DMmini Chap. 7 is superseded by PROB (below).
-
expanded version (DMmaxi)
Note that the chapter numberings in the two versions are not consistent.
Some of the introductory chapters are missing from "DMmaxi" while
the mini version does not include any of the advanced material; regarding
chapters that appear in both versions, the more recent updates
appear in the mini version.
The mini version will be our standard reference for
terminology.
Chapter 7 ("Finite Probability Spaces") of the mini version has been
greatly revised and is available as standalone set of notes:
An update of Section 2.2 of the "Asymptotic notation"
chapter of the mini version is here:
Some basic number theory is described in these notes (correct definition
of gcd's, Euclid's algorithm, congruences, residue classes,
multiplicative inverse)
Additional resources:
- "MR22" --
Introduction to Mathematical Reasoning via Discrete Mathematics
(Autumn 2022)
(basic course, with an emphasis on the logic of proofs, includes a
discussion of equivalence relations, Inclusion-Exclusion,
binomial coefficients,
the basics of Ramsey theory for graphs, finite probability spaces,
random variables, independence, limits and asymptotic notation,
basic number theory: greatest common divisors, congruences,
and more; it also includes LaTeX codes for many of the
symbols used)
- "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.
-
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:
For challenge and fun, you may want to check out these problem sets:
There are additional online handouts on the following subjects.
- Grades will be based on
homework (85%) and class participation (15%).
(Class participation includes answering the Questionnaire on time
and answering the Zoom "chat" questions in class (see "Zoom and privacy"
below). Giving an answer, even if incorrect, is always better than
giving no answer.
Warning the instructor about errors made in class or posted on this
website also counts as class participation.)
There will be no tests in this course.
- Concepts and proofs discussed in class are required in the
next class and in all subsequent classes.
Go to top
Homework exercises will be announced in class and/or on this website.
Homework to be handed is will be assigned on Gradescope, with
reference to this website (see below).
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.
- "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.
- "ORD" "ordinary" HOMEWORK problems. Solve them when
assigned on Gradescope, and submit your solutions
online on Gradescope. Most problems will have short and
elegant solutions; elegance counts.
- "Bonus" BONUS problems: they count as ordinary homework
for those who seek graduate credit (CMSC 37200), and for those
who seek a grade of A or A- for undergraduate credit
(CMSC 27410 and Math 28410).
For everyone else, the Bonus problems count as "extra credit" problems
(not required but it adds to your score). Solve them when
assigned on Gradescope, and submit your solutions
online on Gradescope. Elegance counts.
The Bonus problems are underrated (expected to take more work
per point), so do the ordinary problems first.
- "Reward" problems are similar in difficulty to the
Bonus problems. Solve them for your own satisfaction.
Do not hand them in.
- "Challenge" problems do not earn you credit
for this course;
solve them for fun. These problems have no deadline unless a deadline
is announced, but they expire once discussed in class or assigned
as Bonus problems. If you are
working on a challenge problem, please warn the instructor by email,
so as to avoid class discussion of the problem before you handed in
the solution. You may submit solutions by email. Do not try
to submit them on Gradescope.
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.
Log into the Canvas site for this class. On the navigation bar
to the left, click "Gradescope". You will see two assignments,
"ordinary" problems (ORD01, ORD02, etc.) and "bonus" problems
(BON02, BON03, etc.).
Click "upload images" even if you have no itention to upload
any images. This will allow you to see the details of the
assignments (which problem corresponds to what exercise on
the course website).
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" 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.
Go to top
Studying in groups is 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(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.
Go to top
Please login to the course Zoom session at the beginning of each class
and mute your voice.
We will be using Zoom "chat" in this class, to answer questions
asked by the instructor, and to convey your comments or questions to
the instructor. Make sure to make all your communications in private
mode. The instructor will publicly comment on the chat answers but will
never identify the person on whose answer he is commenting.
The "chat" comments will be recorded for later review by the instructor.
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.