Schedule for AMS 550.472/672

Schedule for AMS 550.472/672: Graph Theory, Spring 2016.

Here is the schedule of lectures :

Lecture 1 (25/1/16): Canceled due to snow storm Jonas.
Lecture 2 (27/1/16): (Section 1.1 of textbook) Motivating examples: Drawing diagrams without lifting the pen, matching students to schools, or jobs to processors, Matrix operations to discover "block diagonal" structure, Modeling social networks, brains using graphs; Definition of a graph, examples, Definitions: u adjacent to v, Neighbor set/ Neighborhood, Loop, Multi-edges, Degree/Edge-degree, Endpoints of an edge, edge incident on a vertex, Simple Graphs.
Lecture 3 (29/1/16): (Sections 1.1 and 1.2 of textbook) Representation of graphs: 1. Vertex set+Edge set+full incidence relation(as a list), 2. Incidence Matrix, 3. Adjacency matrix; Isomorphism of Graphs; Subgraph; Operations of deleting an edge, vertex or subset of vertices, Induced subgraph; Study of Connectivity: Walks, Paths; Definition of u connected to v;
Lecture 4 (2/1/16): (Section 1.2 of textbook) Connectivity imposes an equivalence relation; Connected components defined from equivalence classes of connectivity relation, connected graphs and subgraphs; connected components = maximal connected subgraph; Definition of independent sets; Bipartite graphs; examples, odd cycle characterization (started proof).
Lecture 5 (2/3/16): (Section 1.2 of textbook) Completed proof of odd cycle characterization of bipartite graphs; Definitions: Trail, Circuit (closed trail), Eulerian trail, Eulerin circuit; Characterization of graphs with Eulerian circuits (started proof), Lemma for existence of cycles in graphs with minimum degree at least 2.
Lecture 6 (2/5/16): (Sections 1.2 and 1.3 of textbook) Completing the characterization of Eulerian graphs, Fundamental relation between sum of edge-degrees and number of edges: Handshaking Lemma, consequence: every graph has even number of odd vertices; decomposing a general graph into minimum number of trails; Applications of Handshaking lemma: Bipartite subgraph with at least half the edges.
Lecture 7 (2/8/16): (Sections 1.3 and 1.4 of textbook) Using the degree-sum formula to prove Sperner's Lemma [Slides for Sperner]; Mantel's bound on the number of edges in a triangle-free graph; Definitions for Directed Graphs; Orientations of undirected graphs; Definitions of complete graph, Tournaments, King; Existence of a king in a tournament.
Lecture 8 (2/10/16): (Section 1.4 of textbook) Existence of a king in a tournament; Eulerian circuits in directed graphs; Operations of adding/deleting an edge and its effect on cycles and connected components; Building up a graph recursively.
Lecture 9 (2/12/16): (pages 22-23 from Section 1.2 and Section 2.1 of textbook) G connected implies at least n-1 edges; G has at least n edges implies G has a cycle; Characterization of cut-edges in terms of cycles; Definitions of tree, forest; Characterization Theorem for trees; Characterization of trees as graphs with a unique path between every pair of vertices; Properties of trees: 1. Every edge is a cut-edge, 2. Every tree is bipartite.
Lecture 10 (2/15/16): Canceled due to inclement weather.
Lecture 11 (2/17/16): (Section 2.1 of the textbook) More properties of trees: 3. Adding an edge creates exactly one cycle, 4. Every connected graph contains a spanning tree. Existence of degree one vertex (leaf); "Induction tool" for trees via deletion of leaf. Exchange properties of spanning trees.
Discussion Session (2/18/16): (Section 2.3 of the textbook) Definitions: Weighted graphs, weight of a spanning tree, optimal spanning tree; Kruskal's algorithm for optimal/minimum spanning trees in weighted graphs, Proof of correctness.
Lecture 12 (2/19/16): (Section 2.2 of the textbook) Counting spanning trees in a graph; Matrix-tree Theorem; Determinants of (n-1)x(n-1) submatrices of the incidence matrix and spanning trees, Factorization of Q in terms of incidence matrix of an orientation,
Lecture 13 (2/22/16): (Section 2.2 of the textbook, Section 1 of Lex Schrijver's notes) Completing the proof of Matrix-Tree theorem: Step 1: Factorization of Q in terms of incidence matrix of an orientation, Step 2: Determinants of (n-1)x(n-1) submatrices of the incidence matrix and spanning trees, Step 3: Cauchy-Binet formula for computing determinants of products of matrices in terms of individual determinants, Step 4: Putting steps 1, 2 and 3 together. Definitions: Matchings, Vertex Cover, independent/stable sets, edge covers, matching lower bounds vertex cover, independent set lower bounds edge cover, Gallai's theorem relating min vertex cover and max independent set, and min edge cover and max matching (statement only).
Lecture 14 (2/24/16): (Sections 1 and 2 from Lex Schrijver's notes) Completing the proof of Gallai's theorem; Structure of set difference of two matchings; Definitions of M-alternating and M-augmenting paths; Berge's theorem stating a matching M is maximum if and only if there is no M-augmenting path.
Lecture 15 (2/26/16): (Section 3 from Lex Schrijver's notes, see also Section 3.1 in textbook, and Section 2.1 from Diestel's book for alternate proofs of Konig's theorem and Hall's theorem) Statement and proof of Konig's Theorem; Statement and proof of Hall's matching theorem.
Lecture 16 (2/29/16): (pages 130-131 of the textbook, pages 40-41 from Diestel's book) Definition of b-factors/b-matchings; Petersen's 2-factor theorem; Stable Matching definitions, The Gale-Shapley algorithm for stable matchings.
Lecture 17 (3/2/16): (pages 130-132 of the textbook, Slides from class, Section 5 in Lex Schrijver's notes, Section 3.3 in textbook) Correctness of the Gale-Shapley algorithm for stable matchings; Matchings in general graphs, Tutte-Berge formula (no proof, only intuition and examples), Tutte's perfect matching theorem, Statement of Petersen's perfect matching theorem for 3-regular graphs with no cut-edges.
Lecture 18 (3/4/16): (Section 5 in Lex Schrijver's notes, Sections 3.3, 4.1 from textbook)Proof of Petersen's perfect matchig theorem for cubic graphs with no cut-edges. Application of Petersen's matching theorem in computer graphics/animation - more details here; Quantifying connectivity: vertex cut/separating set/disconnecting set.
Lecture 19 (3/7/16): (Section 4.1 from textbook) Quantifying connectivity: vertex cut/separating set/disconnecting set, k-connected, vertex connectivity parameter; connectivity of complete graph, complete bipartite graph, n-CUBE.
Lecture 20 (3/9/16): (Section 4.1 and 4.2 of the textbook) Definitions: disconnecting edge set, edge cut, k-edge-connected; Whitney's theorem relating minimum degree, minimum vertex cut and minimum edge cut; Definitions: internally disjoint x-y paths, x-y disconnecting set of vertices, x-y edge-disjoint paths, x-y disconnecting set of edges; Menger's theorem [Vertex version] - statement and discussion.
Lecture 21 (3/11/16): (Section 4.2 of the textbook) Proof of Menger's theorem [Vertex version].
Lecture 22 (3/21/16): (Section 4.2 of the textbook) Recap of Menger's Theorem [Vertex version]; Statement of Menger's thm [Edge version], Definition of line graph, Proof of Menger's Thm [edge version] using line graphs, Global version of Menger's theorem. Statement of "Expansion Lemma" (Lemma 4.2.3 in textbook).
Lecture 23 (3/23/16): (Section 4.2 of the textbook) Proof of Expansion lemma. Characterization of 2-connected graphs. Subdivision Lemma for 2-connected graphs. Definition of ear in a graph.
Lecture 24 (3/25/16): (Section 4.2 of the textbook) Ear decomposition characterization of 2-connected graphs; Fan Lemma - statement.
Lecture 25 (3/28/16): (Section 4.1 and 4.2 from textbook) Fan Lemma - proof. Blocks - definitions and examples. Properties of blocks; block-cutpoint graph of a simple graph.
Lecture 26 (3/30/16): (Section 5.1 from textbook) Colorings in graphs; Definitions - color class, k-colorable, chromatic number \chi(G); Upper bounds for chromatic number: Greedy algorithm for vertex coloring to obtain max-degree+1 as upper bound on chromatic number, Statement of Brook's theorem to give max-degree as uppoer bound for graphs that are not complete and not odd cycles (no proof), Statement of Gallai-Roy-Vitaver theorem on relating orientations and chromatic number; lower bounds on chromatic number in terms of max clique size; Interval graphs.
Lecture 27 (4/1/16): (Sections 5.1 and 5.2 from textbook) Intervals graphs have chromatic number=clique number; Perfect graphs; Mycielski's construction.
Lecture 28 (4/4/16): (Section 5.3 from textbook) counting proper k-colorings; examples - complete graph, complement of complete graph; Chromatic polynomial obtained from partitions of the vertex set into independent sets; Recurrence for chromatic polynomial; examples - cycle of length 4, kite (=K_4 minus a single edge).
Lecture 29 (4/6/16): (Section 5.3 from textbook) Coefficients of chromatic polynomial; Whitney's formula for chromatic polynomial in terms of connected components of spanning subgraphs; counting acyclic orientations using chromatic polynomial; examples - K_3; proof of counting acyclic orientations using chromatic polynomial.
Lecture 30 (4/8/16):(Section 7.1 from textbook) Edge-colorings: connection to vertex coloring on line graph, connection to matchings, Vizing's Theorem.
Lecture 31 (4/13/15): (Section 11.1 from Diestel, Section 8.5 from textbook) Vizing's theorem; graphs of class 1 and class 2. Review of basic discrete probability spaces; definition of probability space of graphs on n vertices with probability parameter p, Probabilities of subgraph structures; Union bound, probability of seeing a clique of size k.
Lecture 32 (4/13/16): (Section 11.1 from Diestel, Section 8.5 from textbook)Ramsey numbers and using random graphs to obtain the Erdos lower bound on Ramsey numbers. Random variables; Expected value/Expectation of random variables; Expected number of k-cycles; technique of indicator random variables.
Lecture 33 (4/15/16): (Section 11.1, 11.2 from Diestel, Section 8.5 from textbook) Tournament with n!/2^{n-1} Hamiltonian paths; Markov's inequality. Erdos' theorem on graphs with arbitrarily large girth (= length of shortest cycle) and arbitrarily large chromatic number; Two ingredients for proof: Show that probability of getting more than n/2 short cycles (cycles of length at most k) goes to zero, Show that probability of having chromatic number larger than n/2k also goes to zero; Put these ingerdients together to get Erdos' theorem - deletion method for removing short cycles; Proof of first "short cycle" lemma (uses Markov's inequality)
Lecture 34 (4/18/16): (Sections 11.2 and 11.3 from Diestel, Section 8.5 in textbook) Proof of second "chromatic number" lemma for Erdos' theorem; Put the two lemmas together to get Erdos' theorem; Definition of graph property; Properties of almost all graphs; Almost all graphs have a (induced) subgraph isomorphic to a fixed subgraph H, when the probability parameter in G(n,p) is a constant (does not depend on n).
Lecture 35 (4/20/16): No lecture -- instructor out of town.
Lecture 36 (4/22/16): (Section 11.3 from Diestel, Section 8.5 in textbook) Almost all graphs have a (induced) subgraph isomorphic to a fixed subgraph H, when the probability parameter in G(n,p) is a constant (does not depend on n). Almost all graphs have diameter at most 2.
Lecture 37 (4/25/16): (Section 11.4 from Diestel, Section 8.5 in textbook) Threshold functions for properties of graphs; Tools: Chebyshev's inequality, bounds on binomial coefficients; Associating a random variable with a property, so that graph has property if and only if X >=1; General proof strategy for threshold phenomenon: 1) Prove almost no graph has property P when p(n) is "small" by using Markov's inequality to bound the probability that P(X >= 1), 2) Prove almost all graphs have property P when p(n) is "large" by showing P(X >= 1) approaches 1 using Chebyshev's inequality; Threshold function for having a subgraph isomorphic to a fixed graph H; First part using Markov showing that if p(n)n^(1/\epsilon(H)) -> 0, then almost no graph contains a copy of H.
Lecture 38 (4/27/16): (Section 11.4 from Diestel, Section 8.5 from textbook) Finish proof of threshold phenomenon for containing a fixed graph as a subgraph -- Second part showing that if p(n)n^(1/\epsilon'(H)) -> \infty, then almost every graph has a copy of H.
Lecture 39 (4/29/16): (Section 11.4 from Diestel) Finish proof of threshold phenomenon for containing a fixed graph as a subgraph -- Second part showing that if p(n)n^(1/\epsilon'(H)) -> \infty, then almost every graph has a copy of H. Discussion of threshold phenomena for multiple properties.