Ma 006b:  Introduction to Discrete Mathematics (Winter 2016-17)

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

  • I'm not completely sure what this is, but it is related to the material!

  • Is Ramsey theory useful when studying the history of pre-christian England? See here.

  • A nice Youtube video about stable matchings. Part 2 of the video contains a proof different than the one that we saw in class.

  • Play the planarity game.

  • Twenty proofs of Euler's formula.

  • PREREQUISITES

    None. It is recommended to take Ma6a first.


    SCHEDULE

    MWF 13:00 - 13:55, 151 Sloan.


    INSTRUCTORS

    Adam Sheffer
    HARRY BATEMAN INSTRUCTOR IN MATHEMATICS
    Sloan 276
    626-395-4347
    Office hours: 4pm Sundays at Sloan 276.


    TA's

    Cosmin Pohoata, apohoata@caltech.edu, Kellog 307.
    Office hours: 5:30pm Mondays at Sloan 153.


    HOMEWORK POLICIES


    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 DescriptionBook 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