Instructor: Brendon Rhoades
Instructor's Email: bprhoades (at) math.ucsd.edu
Instructor's Office: 7250 APM
Instructor's Office Hours: 10:00-11:00am MWF
Lecture Time: 1:00-1:50pm MWF
Lecture Room: 109 CENTR
TA: Michelle Bodnar and Daniel Kroes
TA's Email: mbodnar (at) ucsd.edu and dkroes (at) ucsd.edu
TA's Office: 6434 APM (M. Bodnar) and 6414 APM (D. Kroes)
TA's Office Hours: 1:00-3:00 Tu and 10:00-12:00 W (M. Bodnar) and 12:00-1:00 Tu and 12:00-1:00 F (D. Kroes)
Discussion Time: 4:00-4:50pm M, 5:00-5:50pm M, 6:00-6:50pm M
Discussion Room: 2206 WLH
Final Exam Time: Friday, 3/24/2017, 11:30am - 2:29pm
Final Exam Room: TBA

Syllabus: Please read carefully.

Textbook for the graph theory portion of the course.

Lectures:

1/9: Administrivia. Chapter 1. Counting length n words from a size k alphabet. Counting subsets of a size n set. The Bijection Principle. Counting permutations of a size n set. Counting size k ordered subsets of a size n set.
1/11: Chapter 1. Counting subsets. Binomial coefficients. Pascal's Triangle. Counting lattice paths. Catalan numbers.
1/13: Chapter 2. Pigeonhole Principle. A number in the sequence 2017, 20172017, 201720172017, ... is divisible by 13. If there are five points on a sphere, at least four of them lie on some closed hemisphere. There are two people on Facebook with the same number of friends.
1/18: Chapter 2. If the points of the plane are colored red, blue, or green, there exists a rectangle in the plane with monochromatic vertices. Chapter 3. The Binomial Theorem. Some binomial coefficient identities.
1/20: Chapter 4. Domino tilings of a 2xn board. The Fibonacci numbers. Explicit formula via linear algebra.
1/23: Chapter 2 of Wilson. Definition of a simple graph (multiple edges, loops not allowed). Definition of a graph (multiple edges, loops allowed). Graph isomorphism. Union of graphs. Connected graphs and connected components. Degree of a vertex. Degree sequences.
1/25: Chapter 2 of Wilson. Handshake Lemma. Edge deletion. Vertex deletion. Subgraphs. Edge contraction. Adjacency matrix A(G). Incidence matrix M(G). Null graphs N_n, complete graphs K_n, cycles C_n, paths P_n, wheels W_n.
1/27: Chapter 2 of Wilson. Bipartite graphs. Complete bipartite graphs. Chapter 3 of Wilson. Walks, trails, paths, and cycles. Every cycle in a bipartite graph has even length. Bounds on the number of edges in simple graphs with n vertices and k components.
1/30: Chapter 3 of Wilson. Disconnecting sets and cutsets. Edge connectivity lambda(G) of a connected graph G. Eulerian trails and Eulerian graphs.
2/1: Chapter 3 of Wilson. A connected graph G is Eulerian if and only if deg(v) is even for every vertex v. Hamiltonian graphs and Hamiltonian cycles. Ore's Theorem: If G is a simple graph with n > 2 vertices and, for any two non-adjacent vertices u and v, we have deg(u) + deg(v) >= n, then G is Hamiltonian. Dirac's Theorem: If G is a simple graph with n > 2 vertices and deg(v) >= n/2 for all vertices v, then G is Hamiltonian.
2/3: Midterm 1.
2/6: Chapter 4 of Wilson. Forests and trees. Characterizations of trees. Every tree has at least two leaves. Anonymous course feedback.
2/8: Chapter 4 of Wilson. Labelled trees. Cayley's Theorem: The number of trees on the vertex set 1, 2, ... , n is n^{n-2}. Spanning trees of graphs. The Laplacian L(G) of a simple graph G. Statement of the Matrix-Tree Theorem.
2/10: Chapter 4 of Wilson. The Greedy Algorithm. Pessimistic government officials. Chapter 5 of Wilson. Planar graphs. Planar drawings. K_5 and K_{3,3} are not planar.
2/13: Chapter 5 of Wilson. Graph homeomorphism. Kuratowski's Theorem: A graph is planar if and only if no subgraph is homeomorphic to K_5 or K_{3,3}. Faces of planar drawings and Euler's Formula for connected planar graphs. Stereographic projection. Generalization of Euler's Formula to possibly disconnected graphs.
2/15: Chapter 5 of Wilson. Application of Euler's Formula: K_5 and K_{3,3} are not planar. Application of Euler's Formula: in a planar graph G, there is a vertex of degree < 6. Genus g surfaces. The genus g(G) of a graph G. We have g(K_5) = 1.
2/17: Chapter 5 of Wilson. The geometric dual G* of a plane drawing G. G** = G. n* = f, m* = m, f* = n. Chapter 6 of Wilson. k-colorable graphs. The chromatic number chi(G) of a graph G. Examples.
2/22: Chapter 6 of Wilson. Degree bounds on the chromatic number of graphs. Statement of Brooks' Theorem. The 6-color theorem for simple planar graphs. The 5-color theorem for simple planar graphs. Statement of the 4-color theorem for simple planar graphs. The Art Gallery Problem.
2/24: Chapter 6 of Wilson. The chromatic polynomial P_G(k) of a graph G. Chromatic polynomials of null graphs, complete graphs, and paths. Deletion-Contraction. Applications: The chromatic polynomial is indeed a polynomial, with degree equal to the number of vertices.
2/27: Chapter 6 of Wilson. The chromatic polynomial P_G(k) has the form G = k^n - m k^(n-1) + ... , where G has n vertices and m edges. The chromatic polynomial is an incomplete isomorphism invariant of simple graphs. Chapter 7 of Wilson. Directed graphs: vertices and arcs. Simple digraphs. Examples of digraphs.
3/1: Chapter 7 of Wilson. The underlying graph of a digraph. Connectivity and strong connectivity of digraphs. Orientable graphs. A graph G is orientable iff every edge of G is contained in at least one cycle.
3/3: Midterm 2.
3/6: Chapter 7 of Wilson. The in-degree and out-degree of vertices in digrahps. Handshake dilemma. The adjacency matrix M of a digraph D. Eulerian diagraphs. Euler's Theorem for digraphs.
3/8: Prof. Rhoades was in Pasadena. Prof. Buss lectured on Hamiltonian and semi-Hamiltonian digraphs. Tournaments. Every non-Hamiltonian tournament is semi-Hamiltonian. Every strongly connected tournament is Hamiltonian.
3/10: Chapter 8 of Wilson. Hall's Marriage Problem. Marriage Condition. Hall's Marriage Theorem. Matchings and perfect matchings in graphs. Complete matchings in bipartite graphs.
3/13: Chapter 8 of Wilson. Transversals of lists (S_1, ... , S_m) of sets. Hall's Theorem for transversals; alternative proof. Latin rectangles and Latin squares. Every Latin rectangle can be extended to a Latin square.
3/15: Clutters (C_1, ... , C_m) of sets. Sperner's Theorem. Proof of Sperner's Theorem via the LYM inequality.
3/17: Review.

Homework Assignments:

Homework 1, due 1/18/2017. Solutions.
Homework 2, due 1/25/2017. Solutions.
Homework 3, due 2/1/2017. Solutions.
Homework 4, due 2/15/2017. Solutions.
Homework 5, due 2/22/2017. Solutions.
Homework 6, due 3/1/2017. Solutions.
Homework 7, due 3/15/2017.

Midterms:

Practice Midterm 1 and Solutions.
Midterm 1 and Solutions.
Score Distribution: 95, 93, 91, 91, 90, 90, 88, 88, 87, 86, 85, 83, 83, 80, 77, 77, 75, 74, 74, 73, 72, 70, 69, 69, 68, 68, 67, 66, 66, 66, 64, 63, 62, 61, 60, 60, 58, 57, 56, 56, 56, 55, 54, 54, 54, 54, 54, 53, 53, 51, 48, 48, 47, 47, 46, 46, 46, 45, 45, 43, 42, 41, 39, 38, 38, 36, 36, 35, 31, 29, 28, 28, 27, 21, 19, 13.

Midterm 2 and Solutions.
Score Distribution: 100, 97, 97, 94, 92, 90, 90, 87, 86, 85, 85, 85, 85, 85, 82, 82, 82, 81, 80, 80, 80, 80, 79, 78, 78, 78, 77, 77, 75, 75, 75, 75, 73, 72, 72, 70, 70, 70, 66, 66, 65, 65, 62, 62, 62, 60, 60, 60, 58, 57, 57, 56, 56, 56, 54, 54, 53, 50, 48, 42, 42, 41, 40, 39, 36, 34, 32, 30, 27, 26, 26, 22, 17, 6.