Schedule of topics: MA 4143/6143, Spring 2017

Date       Chapter       Description 
Jan 9 4.1 Introduction
Jan 11 3.1 Counting: strings and functions
Jan 13 3.1 Injective functions

Jan 16 Martin Luther King Day! (no class)
Jan 18 3.2 Permutations
Jan 20 3.3 Binomial coefficient basics, Pascal's triangle

Jan 23 3.3 the Binomial Theorem
Jan 25 3.3 Multinomial counting problems
Jan 27 3.7 the Inclusion-Exclusion formula

Jan 30 3.7, 3.8 Inclusion-Exclusion examples
Feb 1 3.8, 4.1 more on Derangements, Graph basics
Feb 3 4.1 bipartite graphs, graph isomorphisms

Feb 6 4.2 subgraphs, induced subgraphs, paths
Feb 8 4.2 cycles in graphs
Feb 10 4.2 connected graphs, connected components of graphs

Feb 13 Exam 1
Feb 15 4.2 distance, adjacency matrix
Feb 17 4.2 counting walks with powers of the adjacency matrix

Feb 20 4.3 (exams back), vertex degrees
Feb 22 4.3 degree sequences, the Handshake Lemma
Feb 24 7.1 Sperner's Lemma

Feb 27 4.4 Eulerian tours, Euler's Theorem
Mar 1 4.4 multigraphs and multigraphs with loops
Mar 3 4.6 2-connectivity, cycles

Mar 6 4.6 2-connectivity, ear decompositions
Mar 8 5.1 tree definition, characterizations of trees
Mar 10 5.1 proof of Tree Characterization Theorem

Mar 13 Spring Break! (no class)
Mar 15 Spring Break! (no class)
Mar 17 Spring Break! (no class)

Mar 20 5.1, 5.3 finish proof of Tree Char. Thm, spanning trees
Mar 22 5.3 Cycle-Avoiding Algorithm for spanning trees
Mar 24 5.3 Growing A Spanning Tree Algorithm

Mar 27 Exam 2
Mar 29 5.4 minimal weight spanning tree problem; Matroid Lemma
Mar 31 5.4 the Greedy Algorithm for minimal weight spanning trees

Apr 3 6.1 planar graphs, R2 drawings
Apr 5 6.1 metric space approach to planar graph drawing
Apr 7 6.1 faces; drawing graphs on other surfaces

Apr 10 6.1 stereographic projection
Apr 12 6.2 Jordan curves, and the JCT
Apr 14 Religious holiday! (no class)

Apr 17 6.2 K5 is not planar; Kuratowski's Theorem; relation with 2-connected
Apr 19 6.3 1-skeleta of polyhedra; Euler's formula
Apr 21 6.3 applications of Euler's formula; maximal planar graphs

Apr 24 6.4 map coloring and graph coloring
Apr 26 6.4 the 5-color Theorem

May 4 Final exam   (12:00 - 3:00pm)