What is new?

PRESS "REFRESH" to find out!

Statistics of HW sets #1--#18 posted. Click "statistics" on the banner.

Homework set #18 posted in full. Due Tuesday, June 4; some of the problems are due Thursday, June 6. Several HW problems have been added/updated after class.

Statistics of HW sets #1--#16 posted. Click "statistics" on the banner.

Homework set #17 posted in full. Due Thursday, May 30. Some HW problems have been added/updated after class.

Homework set #16 posted in full. Due Tuesday, May 28. Please read the notes carefully. Clarifications have been added, and errors corrected. (Possibly new errors introduced -- please report.) Some HW problems have been added/updated after class.

Homework set #15 posted in full. Due Thursday, May 23.
Please read the notes carefully. Clarifications have been added, and errors corrected. Some HW problems have been added/updated after class.

Homework set #14 posted. Due Tuesday, May 21. Please read the notes carefully; narrative has been added to clarify concepts, make connections to prior material, and fill gaps in the lecture. Some HW problems have been added/updated after class.

Statistics of HW sets #1--#13 posted. Click "statistics" on the banner.

Homework set #13 posted. Due Thursday, May 16. Some HW problems have been added/updated after class. Recall that some exercises from last week are also due Thursday.

Homework set #12 posted in full. Due Tuesday, May 14 and Thursday, May 16. Some HW problems have been added/updated after class.

Statistics of HW sets #1--#10 posted. Click "statistics" on the banner.

Grading scheme posted

Homework set #11 posted. Due Thursday, May 9. Some HW problems have been added/updated after class.

Homework set #10 posted. Due Tuesday, May 7. Some HW problems have been added/updated after class.

The HW section of this page now also includes a summary of what has been covered in each class. Click "Class notes, homework assignment, material covered" on the banner.

If you have not completed the Questionnaire below yet, please do.

Questionnaire

Please send email to the instructor with answers to these questions, even if you are only sitting in on the class, did not register, or have an unusual status. Your answers to these questions will help me better to plan the course. Please write "CMSC 27530 data" in the subject (or CMSC 37530, as appropriate).

• 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 TTI-C grad student specializing in semantic image segmentation," or "PSD Masters student interested in visualizing biological pathway information" etc.)
• Do you expect to graduate this quarter?
• Did you register for this class? (I want to hear from you in either case.)
• If you did, what type of grade do you seek (letter grade [A-F], P/F, audit)? (You can change your mind about this later.)
• Why are you taking this course?
• Are you fulfilling a requirement with this course? If yes, please elaborate. What is the minimum grade you need to fulfill the requirement?
• 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).
• Math background, continued: 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 otherwise).
• Have you taken a formal course in linear algebra? If so, you probably answered this in the previous question but still, please anwser the rest of this question. If not, please describe the extent of your encounter with linear algebra (in what course). Are you familiar with these concepts and results: rank of a matrix, determinant, eigenvalue, characteristic polynomial, Spectral Theorem.

Go to top

Course description

Description will be entered here.

Prerequisites: 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 homework and test problems will ask you to prove something.

Formal prerequisites: analysis (Math 20400) or Discrete Mathematics (CMSC 27100) or instructor's consent. In particular, facility with limits and the basics of counting, discrete probability, and number theory expected. Linear algebra will be used occasionally and is only required if you aspire for an A or A-.

Go to top

Course information

e-mail:     laci(at)cs(dot)uknowwhere(dot)edu    and    lbabai(at)(google-mail)

If you send me email, please send it to both addresses.
Each address has its pros and cons; safest is if you send it to both.

Office hours: by appointment (please send e-mail)

TA: Alex Hoover                               alex [at] CS [dot] etc

TA's office hour: Monday 5pm. Location: JCL-356

Classes: TuTh 11:00 - 12:20, Ry-276

LAST CLASS: Thursday, June 6. Attendance required if you want a letter grade. Also if you want P/F. (This sentence was added 05-31.)

Go to top

Text

Your primary text will be your course notes, so please make sure you don't miss classes. If you do, you should copy somebody's class notes and discuss the class with them.

Texts (for reference only):

Gary Chartrand and Ping Zhang: A First Course in Graph Theory
(This is a basic intro text with many exercises)

J. Adrian Bondy and U. S. Rama Murty: Graph Theory with Applications.
(Highly recommended: a classic text, still a first course but with more substatial proofs)   Print copy recommended but you may also be able to find it online.

WARNING: in these and all other references, watch out for possible discrepancies in terminology. Please use the terminology we use in class.

Additional printed references:

Douglas B. West: Introduction to Graph Theory. Prentice - Hall 1996, 2001.

Jiří Matoušek, Jarik Nešetříl: Invitation to Discrete Mathematics, published by Oxford University Press, ISBN# 098502079.
(This is a beautiful introduction on the advanced undergraduate level.)

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)

Online references:

Tero Harju "Lecture Notes on Graph Theory" (2007) (too easy)

Lex Schrijver: "Advanced Graph Theory" (too hard)

Instructor's Discrete Mathematics Lecture Notes (PDF) includes Graph Theory terminology and exercises; it also includes the basics of Finite Probability Spaces and Asymptotic Notation, relevant for this course

Instructor's Discrete Math Lecture Notes by Morgan Sonderegger and Lars Bergstrom (PDF) (detailed notes based on the 2007 DM class, but not proofread by instructor)

Lecture notes on linear algebra and spectral graph theory by Madhur Tulsiani and the instructor, REU 2013 for rising 2nd-years

Problem sheets from instructor's 2012 REU course for rising 2nd-years (including linear algebra problems and "puzzle problems")

Basic prerequisites such as a discussion of equivalence relations can be found in this book:

Kenneth H. Rosen: Discrete Mathematics and its Applications (n-th edition, n=2,3,4,5,...).
This is a basic-level introductory text. The foundations of logic, proofs, basic number theory and counting covered in this text are assumed in this course. This course is considerably more advanced than the level of Rosen's book, but some students may find some chapters of Rosen helpful; if so, solving many problems from Rosen's relevant chapters is a good way to fill those gaps in your background.

Go to top

Grading

Grades are based on homework (90%) and class participation (10%). Experimentally, there will be no tests in this course. What contributes to class participation? Showing interest in the class. Here are some of the ways in which you can show your interest: raising your hand to ask or answer questions, warning the instructor about mistakes on the blackboard or by email about errors on the website, other help or feedback.     Negative: failing to answer the questionnaire.

The tests are closed-book; no notes permitted. The use of electronic devices is strictly forbidden during tests.

Test dates

TBA. (There will be no final exam.)

LAST CLASS: Thursday, June 6. Attendance required if you want a letter grade.

Go to top

CLASS NOTES, homework assignments, material covered

Please submit solutions to challenge problems separately, either by email or on a separate sheet (email is best). In the Subject of your email message, write "Challenge 12.33" (or whatever the problem number).

Remember that you are expected to attend the last class, Thursday, June 6.

• Class 18, Thu, May 30     Geoff #18 (rev)     (due Tuesday, June 4)
  Directed graphs, orientations of undirected graphs. Out-degree, chromatic number. Accessibility vs. cuts: a good characterization. Strong connectivity. Tournaments. Acyclic digraphs, topological sort. Rational roots of polynomials with integer coefficients. (Fibonacci numbers, golden ratio, powers of a $2\times 2$ matrix, gcd of Fibonacci numbers: for entertainment only.) (Exponential function of a matrix: for entertainment only.) Algebraic vs. geometric multiplicity of eigenvalues. Spectrum vs. maximum degree. Largest eigenvalue of a tree is $\le 2\sqrt{\Delta -1}$. Smart-greedy coloring, Wilf's spectral bound: $\chi(G)\le 1+\lambda_1$. Triangle-free graphs with large chromatic number: Mycielski, Grötzsch. Erdös's probabilistic proof of existence of small ($n\le k^{3+\epsilon}$) graph of chromatic number $\ge k$. Erdös--Rényi random graphs. Large girth and large chromatic number. Kneser's graph, Kneser's conjecture. (Infinite graphs: for entertainment only: Erdös-DeBruijn ($k$-colorability is a finitary property), graphs of large infinite chromatic number without short odd cycles, Erdös-Hajnal: graphs of uncountable chromatic number contain 4-cycle, large complete bipartite subgraph.)
• Class 17, Tue, May 28     Geoff #17 (rev)     (due Thursday, May 30)
  Independence of random variables, variance, covariance, variance of sum, pairwise independence, Chebyshev's and Markov's inequalities. Probability generating functions, sum of independent variables, if real-rooted then sum of independent Bernoulli trials, application to matching generating function, Central Limit Theorem, Berry-Esséen theorem (stated), asymptotic normality of random matchings. Ramsey theory revisited, Erdös's probabilistic lower bound for diagonal Ramsey numbers, explicit Ramsey graphs. Ramsey numbers for $(0,1)$ matrices.
• Class 16, Thu, May 23     Geoff #16 (rev)     (due Tuesday, May 28)     Please read the notes carefully. Clarifications have been added, and errors corrected. (Possibly new errors introduced -- please report.) Some HW problems have been added/updated after class.
  Spectral graph theory and the Chebyshev polynomials. Inner products, function spaces. Orthogonal polynomials. Some families of classical orthogonal polynomials: Chebyshev (first and second kind), Hermite. Orthogonal polynomials: real-rooted, interlacing. Proof using 3-term recurrence. Matchings polynomials: real-rooted, interlacing. 3-term recurrence. Matchings polynomial of trees, paths, cycles, complete graphs. Independence of events vs. size of the sample space.
• Class 15, Tue, May 21     Geoff #15 (rev)     (due Thursday, May 23)    
  Girth. Laplacian, the Matrix-Tree Theorem (stated). Independence of events and random variables. Bernoulli trials, binomial distribution. Unimodal and log-concave sequences. Real-rooted polynomials and log-concavity: Newton's inequalities. Chebyshev polynomials, recurrence. The matching generating function and the matchings polynomial of a graph.
• Class 14, Thu, May 16     Geoff #14 (rev)     (due Tuesday, May 21)     Please read the notes carefully; narrative has been added to clarify concepts, make connections to prior material, and fill gaps in the lecture. Some HW problems have been added/updated after class.
  Fractional independence number. Basic Ramsey Theory for graphs. The Erdös-Szekeres bound. Discussion of the diagonal case. Erdös's non-constructive bound stated; constructive bounds. Polynomials of matrices. Spectral graph theory. Powers of the adjacency matrix. Maximum number of triangles bounded in terms of the number of edges. Rayleigh's Principle revisited. Bounds on the largest eigenvalue of a graph. Uniqueness of the largest eigenvalue if the graph is connected. Wilf's spectral upper bound on the chromatic number. Spectral conditions of bipartiteness.
• Class 13, Tue, May 14     Geoff #13 (rev)     (due Thursday, May 16) Recall that some exercises from last week are also due Thursday.
  The spectrum of a matrix: a multiset. Computing $\det(bJ+(a-b)I)$ in two ways: by elementary determinant operations, and without computation, by finding an eigenbasis and eigenvalues. Eigenbasis of the $J$ (all-ones) matrix. Rank-nullity. Similarity of matrices. The characteristic polynomial is a similarity invariant. Diagonalizable matrices: existence of eigenbasis is equivalent to similarity to a diagonal matrix. Criteria of left and right invertibility of a matrix. Orthogonal matrices. List of $2\times 2$ orthogonal matrices. Orthogonal similarity. Spectral Theorem restated.
• Class 12, Thu, May 9     Geoff #12 (rev)     (due Tuesday, May 14 and Thursday, May 16)
  Extremal graph theory. Kövári-Sós-Turán theorem. Erdös-Stone-Simonovits theorem stated.   Linear algebra over the real and complex numbers. Determinants, eigenvectors, eigenvalues, characteristic polynomial, trace, eigenbasis, diagonalizable matrices. Fundamental Theorem of Algebra. Eigenvalues vs. trace and determinant. Symmetric real matrices and quadratic forms. The Spectral Theorem. Rayleigh quotient, Rayleigh's Principle. Courant-Fischer theorem, interlacing eigenvalues.
• Class 11, Tue, May 7     Geoff #11 (rev)     (due Thursday, May 9)
  The pentagon and the golden ratio. Orthonormal systems. Kronecker product, Lovász dimension, Shannon capacity. Lovász capacity: the Lovász $\vartheta$ function. The Shannon capacity of the pentagon: the Lovász umbrella. Good characterization of the $\vartheta$ function.
• Class 10, Thu, May 2     Geoff #10 (rev)     (due Tuesday, May 7)
  Perfect graphs. Posets, comparability graphs. The Perfect Graph Theorem stated. Tiling invariants, AHA proofs of impossibility of tiling. Kronecker product (tensor product), Lovász dimension, and Shannon capacity.
• Class 9, Tue, Apr 30     Geoff #9 (rev)     (due Thursday, May 2)
  Asymptotics, chromatic polynomial, deletion/contraction recurrence, independent sets in strong products, Linear Programming, Duality Theorem of LP (stated), upper bounds on the Shannon capacity, $\Theta \le \alpha^*$, Lovász's orthonormal representations of graphs, Lovász-dimension of graphs
• Class 8, Thu, Apr 25     Geoff #8 (rev)     (due Tuesday, April 30)
  Excluded subgraphs vs. chromatic number (challenge problems), independence number via the pigeonhole principle - independence number of the grid (3 AHA proofs), the Shannon capacity of graphs, Fekete's Lemma, supermultiplicativity of the independence number, submultiplicativity of the chromatic number, Linear Programming (LP) and Integer Linear Programming (ILP), dual LP, fractional independence number, fractional chromatic number: linear relaxations of combinatorial optimization problems.
• Class 7, Tue, Apr 23     Geoff #7 (rev)     (due Thursday, April 25)
  Independent sets in strong products of cycles ("King's graphs" on the toroidal chessboards), Lovász bound mentioned, matchings, König's Theorem proved: method of augmenting paths, chromatic polynomial: the fact that it is a polynomial proved (G. D. Birkhoff, 1912), orientations of graphs.
• Class 6, Thu, Apr 18     Geoff #6 (rev)     (due Tuesday, April 23)
  longest paths, finite probability spaces, indicator variables, linearity of expectation, expected number of heads in $n$ coin flips, probabilistic proof of the Wei--Caro bound on the independence number, strong product of graphs, independent sets in toroidal "King's graphs"
• Class 5, Tue, Apr 16     Geoff #5 (rev)     (due Thursday, April 18)
  intersection of subtrees, walks vs. paths, closed walks vs. cycles, (closed) Eulerian trails, adjacency matrix and its powers, bipartite graphs vs. odd cycles, matchings and covers, Dénes König's Theorem: for bipartite graphs, $\nu = \tau$, Philip Hall's "Marriage Theorem," good characterization of predicates
• Class 4, Thu, Apr 11     Geoff #4 (rev)     (due Tuesday, April 16)
  distance, diameter. Turán's Theorem, proof by induction. Three lower bounds of increasing strength on the independence number in terms of the degrees: (1) naive bound via the greedy algorithm (2) Turán's bound (3) the Wei--Caro bound. Comparing the arithmetic, geometric, and harmonic means. Comparing Turán's bound and the Wei--Caro bound. Finite probability spaces. Events. Uniform distribution. Random variables. Expected value, linearity of expectation. Indicator variables. The hat-ckeck problem, first variant: an application of the linearity of expectation. Use linearity of expectation to prove the Wei--Caro bound.
• Class 3, Tue, Apr 9     Geoff #3 (rev)     (due Thursday, April 11 and Tuesday, April 16)
  bipartite graphs, chromatic number, clique number, triangle-free graphs of high chromatic number (stated), independence number, cartesian product of graphs, maximal vs. maximum independent sets, minimum spanning tree
• Class 2, Thu, Apr 4     Geoff #2 (rev)     Amin #2 (orig)     (due Tuesday, April 9)
  Fibonacci numbers, explicit formula, asymptotic equality, big-Oh notation, implied constant, quadratic vs. arithmetic mean, Mantel--Turán Theorem (2 proofs), $C_4$-free graphs, Multinomial Theorem, number of edges of a tree, Cayley's formula, number of trees with prescribed degrees, use this to prove Cayley's formula, Prüfer's code (reading), longest paths in a tree, chromatic number, greedy coloring, $\chi \le 1+\Delta$, asymptotic notation
• Class 1, Tue, Apr 2     Geoff #1 (rev)     Amin #1 (orig)     (due Thursday, April 4)
  graphs, path $P_n$, cycle $C_n$, $k\times\ell$ grid, clique $K_n$, complete bipatite graph $K_{r,s}$, $d$-cube $Q_d$, complement, Petersen's graph, Handshake Theorem, isomorphism, self-complementary graphs, Mantel--Turán Theorem stated, trees

Rules on HOMEWORK

Errors may occur, so please recheck the website. If you suspect an error, please notify the instructor (by email) right away. If you are the first to point out an error, you may receive bonus points.

Problems come in several categories.

"DO" exercises are meant to check your understanding of the concepts. Do them but do not hand them in. If you encounter any difficulties, please let the instructor know by email.

"HW" indicates ordinary homework problems that you need to hand in.

"Bonus problems" also carry point value and have the same deadline as ordinary homework but they are not mandatory for the undergraduate credit. However, they are mandatory for graduate credit. Their point value is underrated so do the ordinary homework first. To get an "A" in this course, you need to collect at least 1/3 of the bonus homework points, and at least 1/5 for an A-.

"Challenge problems" don't have a specific deadline except they cease to be assigned once they have been discussed in class. If you are working on a challenge problem, please send email to the instructor so as to avoid discussion of the problem before you handed in the solution.

Solutions to Challenge problems earn you some bonus points, but they are significantly underrated. However, they do earn you the instructor's respect, in addition to giving you valuable experience. If at some point in the future you need a letter of recommendation, challenge problems you solve will be the primary reference.

Partial credits. On ordinary homework, a reasonable effort will typically result in partial credit. The grading of bonus problems and challenge problems is stricter, effort does not guarantee partial credit unless your work represents a significant part of a correct solution. Moreover, for bonus problems and challenge problems, only mathematically accurate work will earn partial credit. For Challenge problems, you may ask the instructor for a hint; the cost of a hint is reduced point value. Use of web-sources that explicitly solve the problem assigned or an essentially equivalent problem also results in reduced credit, see below.

Go to top

Policy on collaboration, academic integrity

Collaboration on current homework is discouraged but not prohibited. If you do collaborate, state it at the beginning of your solution (give name of collaborators, nature/content of collaboration) and mark inside the solution if an idea is not yours. Please also send email to the instructor with the same collaboration information (to make it easier for the instructor to keep track of collaborations). Please write "HW#6 collaboration" in the Subject line for HW set #6 (where, in the tradition of the ancient Greeks, "6" is a symbol for a variable; substitute the correct value). There is no penalty for acknowledged collaboration on homework as long as it does not amount to copying. DO NOT COPY someone else's solution: after the discussion, throw away any written records. Understand the ideas discussed and give your own rendering. Sharing hand-written or printed drafts or electronic files containing solutions or significant parts of solutions before submission is strictly prohibited, and will be regarded academic dishonesty.

The requirement to report sources also applies to other sources (books, the web, etc). Acknowledge all sources both in the paper and in email to the instructor. (Write "HW#6 collaboration/sources" in the Subject if you report both collaboration and sources.) See the policy on the web sources below.

Go to top

Policy on web sources

The web is a useful resource but you need to read it critically: it often has errors, it often makes things look more complicated than they actually are, the web article may be targeted to a very different audience and with very different goals, and the terminology may differ from the one used in class.

The use of the web to track down solutions to homework problems is strongly discouraged. This is counterproductive; it denies you the experience of learning by discovery that this course tries to impart.

The web by now is so rich that it is virtually impossible to avoid assigning problems to which solutions are found on the web. The instructor retains the right to reduce the point value of problems during grading if it turns out that solutions exist on the web in cases when the instructor was not aware of the availability of such a solution.

While studying relevant material on the web is ok, looking up explicit solutions on the web to problems essentially identical with those assigned is considered an abuse of the web. Unfortunately to many of the most elegant and instructive problems, you can find solutions on the web. Tracking them down is not prohibited but here are the rules:

• acknowledge the source: give the source (URL). Failing to do so is considered academic dishonesty.
• DO NOT COPY. Understand the idea, then write your own version without looking at the source or your notes. Acknowledge specific ideas you learned from the web source.
• If the solution is based on an explicut solution found on the web, the solution will only get partial credit, typically 2/3 of the full credit. This policy is subject to change depending on how much students abuse the availability of solutions on the web.

View the instructor's course materials from previous years

View instructor's home page

Go to the Department of Computer Science home page

Go to top