MA 4143/6143 - Schedule

Schedule

Schedule of topics: MA 4143/6143, Spring 2014

Date Chapter       Description 
Jan 13           4.1 Introduction
Jan 15 3.1 Counting functions between finite sets
Jan 17 3.1 - 3.2 Counting injections between finite sets (permutations)

Jan 20 Martin Luther King Day! (no class)
Jan 22 3.3 Counting subsets
Jan 24 3.3 the Binomial Theorem, the Freshman's Dream Identity

Jan 27 3.3 Mississippi reorderings, poker hands
Jan 29 3.7 Inclusion-Exclusion
Jan 31 3.8 Derangements: the Hatcheck Problem

Feb 3 4.1 Graph basics: examples and isomorphisms
Feb 5 4.1 (Complete) bipartite graphs, the number of graphs on n vertices
Feb 7 4.2 Subgraphs and induced subgraphs

Feb 10 4.2 Walks and the adjacency matrix
Feb 12 Snow Day
Feb 14 4.3 Degrees and the degree sequence

Feb 17 4.3 The Handshake Lemma; Bridges of Königsberg
Feb 19 Exam 1
Feb 21 4.4 Eulerian tours

Feb 24 4.4 proof of the Eulerian Tour Theorem
Feb 26 4.6 2-connected graphs, examples and terminology
Feb 28 4.6 Cycle characterization of 2-connected graphs

Mar 3 4.6 Ear decompositions of 2-connected graphs
Mar 5 4.7 Extremal problems example: cycle-free graphs
Mar 7 Automorphisms of the Petersen graph (guest lecturer: Ted Dobson)

Mar 10 Spring Break! (no class)
Mar 12 Spring Break! (no class)
Mar 14 Spring Break! (no class)

Mar 17 4.7 Maximum # edges in a triangle-free graph
Mar 19 5.1 Introduction to trees, TFAE
Mar 21 5.1 The Tree Characterization Theorem

Mar 24 (5.2) A brief introduction to computational complexity
Mar 26 5.3 Spanning trees, Algorithm 1
Mar 28 5.3 Running time of Algorithm 1

Mar 31 5.3 Algorithm 2: growing a spanning tree
Apr 2 5.4 Minimum spanning trees
Apr 4 5.4 - 6.1 Matroid Lemma for cycle-free graphs; begin planar graphs

Apr 7 6.1 Arcs, R2-drawings, and R2-embeddings
Apr 9 Exam 2
Apr 11 6.1 exam solutions, a zoo of surfaces

Apr 14 6.1 - 6.2 Stereographic projections, arc-connected regions, faces
Apr 16 6.2 The Jordan Curve Theorem, K5 is not planar
Apr 18 Religious holiday! (no class)

Apr 21 6.2 Faces of 2-connected graphs, Kuratowski's Theorem
Apr 23 6.3 Euler's formula for planar graphs
Apr 25 6.3 Upper bound for # edges of a planar graph, dual graphs

Apr 28 6.4 k-colorings and the chromatic number
Apr 30 6.4 The 5-color Theorem

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