Introduction to Discrete Mathematics

Course Meeting Time and Location
Monday, Wednesday, Friday
1:00 - 1:55 pm
B122 Gates Chemical Laboratory (GCL, Building 26)


Course Instructor Contact Information and Office Hours
201 Math Building (Building 15)
E-mail: durcik at caltech dot edu
Office hours: By appointment


TA Contact Information and Office Hours
2-R Math Building (Building 15)
E-mail: afrimu at caltech dot edu
Office hours: Monday 8-9pm


Course Schedule and Textbook
Math/CS 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).

Textbooks:
Introduction to Graph Theory, 2nd edition, by Douglas West
Graph Theory, 4nd edition, by Reinhard Diestel

We will follow the slides by Adam Sheffer. They will be posted on this website as the course proceeds.

 DateTopic  Book sections*
 01/03/2018Graph recap D1.1, D1.2, D1.3, D1.5
 01/05/2018Matchings W3.1 (also D2.1)
 01/08/2018Stable matchings D2.1 (also W3.1, W3.2)
 01/10/2018Matchings in general graphs D2.1 and W3.3 (also D2.2)
 01/12/2018Graph connectivity D1.4 (also W4.1)
 01/17/2018More connectivity W4.2 (also D3.1 and D3.3)
 01/19/2018Minors D1.7
 01/22/2018Planar and plane graphs W6.1
 01/24/2018Euler's formula W6.1
 01/26/2018Kuratowski's theorem W6.2 (also D4.4)
 01/29/2018Kuratowski and coloring  W6.2, W6.3 (also D4.4, D5.1)
 01/31/2018Ramsey theory W8.3 (also D9.1)
 02/02/2018Ramsey theory 2 W8.3 (also D9.2)
 02/05/2018The probabilistic method Chapter 1 of this book (also W8.5)
 02/07/2018The probabilistic method 2 Excerpts from chapters 1-3 of this book (also W8.5)
 02/09/2018Crossing numbers W6.3
 02/12/2018Extremal graph theory Chapters 18 and 36 of this book (also D7.1)
 02/14/2018Extremal graph theory 2
 Parts of Lectures 2 and 3 here. Notes until page 10.
 02/16/2018Graphs and matrices
 W1.1 (also D1.9) but only partially
 02/21/2018Counting spanning trees W2.2
 02/23/2018Spectral graph theory W8.6
 02/26/2018Spectral graph theory 2 W8.6
 02/28/2018Eigenvalues in regular graphs W8.6 and this
 03/02/2018Expanders
This (and W8.6)
 03/05/2018Error correcting codes Biggs (the 6a book) 24.1,24.2,24.3,24.4
 03/07/2018Error correcting codes 2 Biggs 24.4 and this
 03/09/2018Art and politicians Chapters 35 and 39 of this book
*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.


Course Policies
There will be six homework assignments, due 11AM Thursday in the dropbox in Downs. Homework assignments comprise 70% of your final grade. You are not allowed to look up solutions to the problems from any source until after the due date has passed for the homework in question. You are encouraged to discuss homework problems in small groups, however each student must hand in the solutions written up in their own words. You are not allowed to look at written solutions of other students.

There will be a final exam which makes up 30% of your final grade. The exact policy will be announced. There will be no midterm exam.


Assignments
Homework 1, due Jan 18.
Homework 2, due Jan 25.
Homework 3, due Feb 1.
Homework 4, due Feb 15.
Homework 5, due Feb 22. 
Homework 6, due Mar 8.


Exam
The final exam is available here and due Wednesday, March 14 at 3pm. The password has been emailed to you. If you have issues accessing the exam, please let Meagan know.

Ċ
Polona Durcik,
Jan 3, 2018, 5:34 PM
Ċ
Polona Durcik,
Jan 5, 2018, 9:39 AM
Ċ
Polona Durcik,
Jan 5, 2018, 9:55 AM
Ċ
Polona Durcik,
Jan 5, 2018, 9:55 AM
Ċ
Polona Durcik,
Jan 10, 2018, 10:16 AM
Ċ
Polona Durcik,
Jan 10, 2018, 10:16 AM
Ċ
Polona Durcik,
Jan 17, 2018, 3:50 PM
Ċ
Polona Durcik,
Jan 17, 2018, 3:52 PM
Ċ
Polona Durcik,
Jan 17, 2018, 3:52 PM
Ċ
Polona Durcik,
Jan 17, 2018, 3:52 PM
Ċ
Polona Durcik,
Jan 17, 2018, 3:52 PM
Ċ
Polona Durcik,
Jan 29, 2018, 3:32 PM
Ċ
Polona Durcik,
Jan 29, 2018, 3:32 PM
Ċ
Polona Durcik,
Jan 29, 2018, 3:32 PM
Ċ
Polona Durcik,
Jan 29, 2018, 3:32 PM
Ċ
Polona Durcik,
Feb 2, 2018, 10:23 AM
Ċ
Polona Durcik,
Feb 2, 2018, 10:23 AM
Ċ
Polona Durcik,
Feb 2, 2018, 10:23 AM
Ċ
Polona Durcik,
Feb 2, 2018, 10:23 AM
Ċ
Polona Durcik,
Feb 2, 2018, 4:15 PM
Ċ
Polona Durcik,
Feb 2, 2018, 10:24 AM
Ċ
Polona Durcik,
Feb 2, 2018, 10:24 AM
Ċ
Polona Durcik,
Feb 2, 2018, 10:24 AM
Ċ
Polona Durcik,
Feb 2, 2018, 10:24 AM
Ċ
24 Codes.pdf
(1907k)
Polona Durcik,
Feb 2, 2018, 10:24 AM
Ċ
Polona Durcik,
Feb 2, 2018, 10:24 AM
Ċ
Polona Durcik,
Feb 2, 2018, 4:15 PM