ANNOUNCEMENTS
There are no office hours this week in the usual times. If you have any questions about the material, feel free to email us or ask for a meeting to discuss this.
COURSE DESCRIPTION
CS/Math 6b is a continuation of Ma/CS 6a, and explores various topics of discrete mathematics. Most of the course is dedicated to graph theory, and especially to combinatorial aspects of graph theory (unlike 6a, which focuses more on graph algorithms). Some of the topics that are studied in the class are planar graphs, the probabilistic method, Ramsey theory, spectral graph theory, and error correcting codes.
Extras
INSTRUCTORS
Adam Sheffer
HARRY BATEMAN INSTRUCTOR IN MATHEMATICS
Sloan 276
626-395-4347
Office hours: 4pm Sundays at Sloan 276.
HOMEWORK POLICIES
- Please staple a blank page containing only your name at the front of the assignment.
- You are encouraged to work in groups on the assignments. However, you are required to write your solution on your own and not to look at written solutions of other students.
- There is no need to formally prove anything, unless the question specifically asks for a proof. However, you do need to explain what you did. The grader needs to see that you did not just write an algorithm/answer without understanding how to get to it or why it works.
- Unless stated otherwise, every given graph is simple and undirected.
- There is no need to find the running time of the algorithms that you create in your homework. However, the running times must be polynomial in the size of the input.
- There is no need to reprove anything that was proven in class. On the other hand, you are not allowed to refer to any other sources, including the course's text book (answers of the form "The proof can be found in page X of the book" will receive no points).
- You may not rely on any related tools that were not studied in 6a or 6b (such as DFS). Using such tools to solve a problem may result in zero points.
- Make sure that you submit your assignments in the LOCKED 6a mailbox, and not in the open box for graded assignments.
TEXTBOOKS
No book covers the entire material of the class, and we rely on several sources. Our main textbook is Introduction to Graph Theory, 2nd edition, by Douglas West. Another useful book is Graph Theory, 4nd edition, by Reinhard Diestel. A free online version of this book can be found here.
LECTURE NOTES
Book sections starting with D refer to the book by Diestel. Sections starting with W refer to the book by West. Some of the relevant sections contain various topics that are not part of the course, or do not contain part of the material. Please do not rely only on the book sections stated below. To see what is missing/redundant, compare with the lecture notes.
Date | Description | Book Sections |
01/06 |
Graph recap | D1.1, D1.2, D1.3, D1.5 |
01/09 |
Matchings 1 | W3.1 (also D2.1) |
01/11 |
Matchings 2 | D2.1 (also W3.1, W3.2) |
01/13 |
Matchings 3 (Class will be given by Cosmin) | D2.1 and W3.3 (also D2.2) |
01/20 |
Connectivity 1 | D1.4 (also W4.1) |
01/23 |
Connectivity 2 | W4.2 (also D3.1 and D3.3) |
01/25 |
Graph minors | D1.7 |
01/27 |
Plane and Planar graphs | W6.1 |
01/30 |
Euler's formula | W6.1 |
02/01 |
Kuratowski's Theorem | W6.2 (also D4.4) |
02/03 |
More Kuratowski and coloring | W6.2, W6.3 (also D4.4, D5.1) |
02/06 |
Ramsey theory | W8.3 (also D9.1) |
02/08 |
Ramsey theory 2 | W8.3 (also D9.2) |
02/10 |
The probabilistic method | Chapter 1 of this book (also W8.5) |
02/13 |
The probabilistic method 2 | Excerpts from chapters 1-3 of this book (also W8.5) |
02/15 |
Crossing numbers | W6.3 |
02/17 |
Extremal graph theory | Chapters 18 and 36 of this book (also D7.1) |
None |
Extremal graph theory 2 (this class is not part of the material this year. It is only here in case you'd like to read more about extremal graph theory). | Parts of Lectures 2 and 3 here |
02/22 |
Adjacency matrices | W1.1 (also D1.9) but only partially :( |
02/24 |
Spectral graph theory | W8.6 |
02/27 |
Spectral graph theory 2 | W8.6 |
03/01 |
Eigenvalues of regular graphs | W8.6 and this |
03/03 |
Expanders | this (and W8.6) |
03/06 |
Error correcting codes | Biggs (the 6a book) 24.1,24.2,24.3,24.4 |
03/08 |
Error correcting codes 2 | Biggs 24.4 and this |
03/10 |
Art galleries and politicians | Chapters 35 and 39 of this book |
HOMEWORK
Due Date | Homework | Solution |
---|---|---|
Jan 17th | Assignment #1 | |
Jan 24th | Assignment #2 | |
Jan 31st | Assignment #3 | Solution #3 |
Feb 14th | Assignment #4 | Solution #4 |
Feb 21st | Assignment #5 | Solution #5 |
March 7th | Assignment #6 | Solution #6 |