Introduction to Discrete Mathematics

Course Meeting Time and Location
Monday, Wednesday and Friday
1:00 - 1:55 pm
387 Linde


Course Instructor Contact Information and Office Hours
304 Linde
E-mail: durcik at caltech dot edu
Office hours: Monday 4.30-5.30pm


TA Contact Information and Office Hours
306 Linde
E-mail: jyu3 at caltech dot edu
Office hours: Tuesday 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).

We will follow the slides by Adam Sheffer.

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

 DateTopic  Book sections*
 01/07/2019Graph recap D1.1, D1.2, D1.3, D1.5
 01/09/2019Matchings W3.1 (also D2.1)
 01/11/2019Stable matchings D2.1 (also W3.1, W3.2)
 01/14/2019Matchings in general graphs D2.1 and W3.3 (also D2.2)
 01/16/2019Graph connectivity D1.4 (also W4.1)
 01/18/2019More connectivity W4.2 (also D3.1 and D3.3)
 01/23/2019Minors D1.7
 01/25/2019Planar and plane graphs W6.1
 01/28/2019Euler's formula W6.1
 01/30/2019Kuratowski's theorem W6.2 (also D4.4)
 02/01/2019Kuratowski and coloring  W6.2, W6.3 (also D4.4, D5.1)
 02/04/2019Ramsey theory W8.3 (also D9.1)
 02/06/2019Ramsey theory 2 W8.3 (also D9.2)
 02/08/2019The probabilistic method Chapter 1 of this book (also W8.5)
 02/11/2019The probabilistic method 2 Excerpts from chapters 1-3 of this book (also W8.5)
 02/13/2019Crossing numbers W6.3
 02/15/2019Extremal graph theory Chapters 18 and 36 of this book (also D7.1)
 02/20/2019Extremal graph theory 2
 Parts of Lectures 2 and 3 here. Notes until page 10.
 02/22/2019Graphs and matrices
 W1.1 (also D1.9) but only partially
 02/25/2019Counting spanning trees W2.2
 02/27/2019Spectral graph theory W8.6
 03/01/2019Spectral graph theory 2 W8.6
 03/04/2019Eigenvalues in regular graphs W8.6 and this
 03/06/2019Expanders
This (and W8.6)
 03/08/2019Error correcting codes Biggs (the 6a book) 24.1,24.2,24.3,24.4
 03/11/2019Error correcting codes 2 Biggs 24.4 and this
 03/13/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 by noon on Thursday. Homework assignments comprise 70% of your final grade. Late work is only accepted with written permission from the Dean. 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 questionYou 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 17. 
Homework 2, due Jan 24. 
Homework 3, due Jan 31. 
Homework 4, due Feb 14.
Homework 5, due Feb 21. 
Homework 6, due Mar 7.



Exams
The final exam will be due Monday, March 18.
Ċ
Polona Durcik,
Jan 7, 2019, 3:16 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:16 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:16 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:17 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:18 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:18 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:18 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:18 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:18 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:18 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:18 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:18 PM
Ċ
24 Codes.pdf
(1907k)
Polona Durcik,
Jan 7, 2019, 3:18 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:18 PM
Ċ
Polona Durcik,
Jan 7, 2019, 3:18 PM