Math 6b Introduction to Discrete Mathematics Winter 2014-15
 MWF 1:00 PM, 151 Sloan
 Course Description | Policies | Extra | Lecture Notes | Homework

 Instructor: Adam Sheffer,  276 Sloan, 626-395-4347, adamsh@caltech.edu Office Hours:  Tuesdays 4:00pm TA: Nakul Dawra, 379 Sloan, ndawra@caltech.edu Office Hours: Wednsedays 7:00 pm TA:Alex Mun, 153 Sloan, dei@caltech.edu Office Hours: Tuesdays 8:00pm
 Announcements

 We submitted the final grades. Thanks for taking this class with us! We hope that you liked it. To compute your grade, sum up all of your assignment grades and divide by 4.2 (this will normalize the grade to be out of 100). To get an A+ you need an average of at least 96. For an A, an average of at least 92. For an A-, at least 84.2. For a B+, at least 80. Feel free to contact us for any issues. We cannot place solutions to the last assignments due to some issue. If you would like to know the solution to a question, feel free to ask any of the staff members.

 Course Description
 The course is a continuation of Ma/CS 6a, and explores various topics of discrete mathematics. A large part of the course is dedicated to graph theory, and especially to combinatorial aspects of graph theory (unlike 6a, which focuses more on graph algorithms). The course also includes error correcting codes, uses of algebra in combinatorics, and other related topics.

 Policies

 Extra

 Is Ramsey theory useful when studying the history of pre-christian England? See here. A nice Youtube video about stable matchings. The part 2 video also briefly states a proof different than the one that we saw in class. Play the planarity game. Twenty proofs of Euler's formula.

 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/05 Graph recap D1.1, D1.2, D1.3, D1.5 01/07 Matchings 1 D2.1 (also W3.1) 01/09 Matchings 2 D2.1 (also W3.1, W3.2) 01/12 Matchings 3 D2.1 and H3.3 (also D2.2) 01/14 Connectivity 1 D1.4 (also W4.1) 01/16 Connectivity 2 W4.2 (also D3.1 and D3.3) 01/21 Graph minors D1.7 01/23 Plane and Planar graphs W6.1 01/26 Euler's formula W6.1 01/28 Kuratowski's Theorem W6.2 (also D4.4) 01/30 More Kuratowski and coloring W6.2, W6.3 (also D4.4, D5.1) 02/02 Adjacency matrices W1.1 (also D1.9) but only partially :( 02/04 Counting spanning trees W2.2 02/06 Ramsey theory W8.3 (also D9.1) 02/09 Ramsey theory 2 W8.3 (also D9.2) 02/11 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/18 Crossing numbers W6.3 02/20 Extremal graph theory Chapters 18 and 36 of this book (also D7.1) 02/23 Extremal graph theory 2 Parts of Lectures 2 and 3 here 02/25 Spectral graph theory W8.6 02/27 Spectral graph theory 2 W8.6 03/02 Eigenvalues of regular graphs W8.6 and this 03/04 Expanders this (and W8.6) 03/06 Error correcting codes Biggs (the 6a book) 24.1,24.2,24.3,24.4 03/09 Error correcting codes 2 Biggs 24.4 and this 03/11 Art galleries and politicians Chapters 35 and 39 of this book

 Homework

 Due Date Homework Average and standard dev. TA in charge Solutions Jan 15th Assignment #1 45.3/50, 4.9 Alex Jan 22nd Assignment #2 38.6/50, 8 Nakul Jan 29th Assignment #3 33/40, 5.9 Alex Feb 5th Assignment #4 45/50, 6 Nakul Feb 12th Assignment #5 43.7/50, 4.8 Alex Feb 19th Assignment #6 42.4/50, 5.8 Nakul Feb 26th Assignment #7 26.9/30, 2.2 Alex March 5th Assignment #8 35.64/40, 4.2 Nakul March 12th Assignment #9 25.25/30, 2.7 Alex March 19th Assignment #10 26.5/30, 3.6 Nakul

 | © California Institute of Technology | Questions?  kaubry @ caltech.edu