Math 881

Instructor: Prof. Peter Magyar, magyar@math.msu.edu, tel. 353-6330, Wells Hall D-326.
Office hours: Mon, Wed, Fri 9−11am, and after class and by appointment.
Lectures: Mon, Wed, Fri 1:50−2:40pm, Wells A-316.

Syllabus: Course outline, class schedule, adminstrative dates.

Announcements

Homework: Grades will be based solely on weekly homework assignments posted here. Click ⊞ to open sections.

⊞ Guidelines
- New HW will usually be posted each Mon and due the following Mon.
- You should discuss homework with other students, but you must write out solutions in your own words.
- Use whatever reference works you like, but do not deliberately look up answers. If you do get help from a reference or person, give explicit credit.
- Use Wolfram Alpha or the like whenever helpful.
⊞ Style
- Write rigorously. Answers should be clear and logically complete, ideally with the rigor and style of published mathematics.
- Write short. Give all needed information in minimum words.
- Give the setup. At the beginning of each problem or section, state what it is about. Always state the Proposition before a proof. Do not assume the reader knows what you are talking about: you yourself will have forgotten when reviewing later.
- Adapt to your audience. In your homework, consider your audience as other students in our course who have not done this problem. Omit details obvious to them, expand arguments unfamiliar to them.
- Use LaTeX: Encouraged, but not required.
Homework 1 due Wed 1/17 (tex). Solutions.
Homework 2 due Mon 1/22 (tex). See Notes below.
Homework 3 due Mon 1/29 (tex).
Homework 4 due Wed 2/7 (tex). See Notes below. Solutions, topological minors.
Homework 5 due Mon 2/19 (tex). See Notes below. Solutions, Four-color Kempe chains.
Homework 6 due Wed 3/14 (tex). Solutions, Turan graphs, Cayley graphs.
Homework 7 due Mon 4/2 (tex). See reading below, Probablistic Graph Theory. Solutions, Mycielski graphs.
Homework 8 due Mon 5/2 (tex). See reading below, Spectral Graph Theory. Solutions.

Notes

Textbooks (with online sources)
- [B] Bollobás, Modern Graph Theory. Main text (MSU, Springer)
- [D] Diestel, Graph Theory. Supplemental text (author, MSU, Springer)
- Aigner & Ziegler, Proofs from the Book. Canonical proofs (MSU, Springer)
- Fan R.K. Chung, Spectral Graph Theory (MSU, AMS)
- Horn & Johnson Matrix Analysis. Ch 4 on spectrum of Hermitian matrices (text, Cambridge, MSU)
- [L] Alexander Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures (Springer, MSU)
- [DSV] Davidoff, Sarnak, and Valette, Elementary number theory, group theory, and Ramanujan graphs (Cambridge, MSU)
Undergrad courses with HW and notes
- Math 481; from HW 3/14, and Graph Notes
- Math 482, from HW 3/19, and from Notes 3/26
Menger Theorem: [B] Ch III, [D] Ch 3.3. F. Göring proof
Flows and Connectivity: [D] Ch 6.2, [B] Ch III.1
⊞ Max Flow/Min Cut Theorem
- Network (G,s,t,c)
  - Directed graph G = (V,E), with edges e = (x→y) ∈ E ⊂ V×V
  - Source and sink vertices s,t ∈ V
  - Edge capacity function c : E → Z_≥0 ∪ {∞}
- Flow function f : E → Z_≥0, satisfying:
  - Continuity: Flow(f,v) = ∑_v→x f(v,x) − ∑_x→v f(x,v) = 0 for all v ≠ s,t
  - Bounds: 0 ≤ f(x,y) ≤ c(x,y) for all x→y.
- Flow volume: Vol(f) = Flow(f,s) = −Flow(f,t)
- Edge-cut: S ⊔ T = V, s ∈ S, t ∈ T
  - Cut capacity: Cap(c,S,T) = ∑_x∈S;y∈T c(x,y)
  - Lemma: Vol(f) = Flow(f,S,T) = ∑_x∈S;y∈T f(x,y) − ∑_x∈T;y∈S f(x,y)
  - Trivial bound: Flow(f,S,T) ≤ Cap(c,S,T) for any f,S,T
- Ford-Fulkerson Theorem: Max{Vol(f), all flows f} = Min{Cap(c,S,T), all cuts S,T}. That is, there are some f,S,T with Flow(f,S,T) = Cap(c,S,T)
- Proof of Theorem using Augmenting Path Algorithm. Initialize f_o(x,y) = 0.
  - Given f_k, define G_k with vertices V and edges:
    - x→y ∈ E(G) with f(x,y) < c(x,y), subcapacity edges in G
    - y→x where x→y ∈ E(G) and f(x,y) > 0, reverse of edges used in G.
  - Case (i): There is a source-sink path s = x_o→x₁→···→x_ℓ = t ⊂ G_k.
    Then define f_k+1 with Vol(f_k+1) = Vol(f_k) + 1:
    - f_k+1(x_i, x_i+1) = f_k(x_i, x_i+1) + 1 for x_i→x_i+1 ∈ E(G)
    - f_k+1(x_i, x_i) = f_k(x_i, x_i+1) − 1 for x_i+1→x_i ∈ E(G)
    - f_k+1(x,y) = f_k(x,y) otherwise.
  - Case (ii): Sink t is not reachable from s in G_k. Let: S = {v reachable from s in G_k}, T = V−S. Then:
    - f(x,y) = c(x,y) for x ∈ S, y ∈ T (otherwise y reachable)
    - f(x,y) = 0 for x ∈ T, y ∈ S (otherwise x reachable)
    - Vol(f) = Cap(c,S,T), Q.E.D.
⊞ Augmenting Path Algorithm adapted to Vertex Menger Theorem
- Connectivity and independent paths.
  - Let G by any graph (not necessarily a polyhedron graph). A cut-set is a set of vertices {v₁,...,v_k} whose removal disconnects G: that is, G−{v₁,...,v_k} has two or more connected components.
  - The index of connectivity κ(G) is the minimum number of vertices which form a cut-set G. That is, κ(G) = k means that G − {v₁,..., v_k−1} is connected for any set of k−1 vertices; but there is some choice of k vertices such that G − {v₁,..., v_k} is disconnected. (By convention, for the complete graph we define κ(K_n) = n−1.) We say G is k-connected if κ(G) ≥ k; that is, it takes at least k vertices to disconnect G.
  - We say P₁, P₂ are independent ab-paths if their only common vertices are their endpoints a and b.
  - A computationally efficient way to determine the connectivity of a graph is the Ford-Fulkerson Augmenting Path Algorithm. For any non-adjacent vertices x,y in G, a full run of the algorithm produces two things:
    1. A family of k of independent ab-paths, ℘ = {P₁,..., P_k};
    2. a cut-set of k vertices which disconnect a from b in G − {v₁,..., v_k}.
    For now, let us assume these results.
  - Claim: Let k_ab be the number of paths (or of vertices) produced by the algorithm, and let κ_ab(G) be the minimum number of vertices needed to disconnect a from b in G. Then k_ab = κ_ab(G).
    Proof: For a given a,b, the cut-set of k_ab vertices must have at least κ_ab(G) elements, so k ≥ κ_ab(G). On the other hand, each of the independent paths between a and b requires at least one vertex removed to block it, so k_ab ≤ κ_ab(G).
  - To determine the global quantity κ(G), we simply take the minimum over all non-adjacent a,b of κ_ab(G) = k_ab.
  - The algorithm also immediately proves the following classic result:
    Menger Theorem:
    - The minumum number of vertices needed to disconnect G equals the maximum number of independent paths which can be found between every pair of vertices.
    - Equivalently, G is k-connected ⇔ G has at least k independent ab-paths for every pair of vertices a,b.
- Augmenting Path Algorithm
  - Starting with an empty family of no paths, each iteration produces a larger family of modified independent ab-paths, until eventually the algorithm gets stuck, blocked by a set of disconnecting vertices.
  - Specifically, given a (possibly empty) family of independent xy-paths ℘ = {P₁,..., P_j}, we attempt to find an augmenting path Q = Q_j+1 from a to b. Such Q is allowed to traverse all edges of G not used by any path in ℘; and Q may also traverse edges in ℘, but only in the backwards direction, away from b, toward a. (Also, Q is not allowed to cross a vertex in ℘ without at least one backward step along ℘.) To construct such a path Q, we start at a and take successive neighbors along permitted edges, until either:
    1. the path Q reaches b; or
    2. no more neighbors can be added, and no Q can reach b
  - Case (i): If the augmenting path Q reaches b, we define a new set of j+1 paths ℘' as follows. We consider the subgraph P' ⊂ G which is the union of all vertices and edges of ℘ and Q, but removing all the edges (not vertices) where Q backtracked along a path in ℘.
    Then P' contains:
    - j+1 edges at a and at b, since Q adds another edge to those in ℘;
    - 2 edges at every other vertex, since a vertex where Q meets ℘ has an outgoing edge in ℘, and the incoming edge in ℘ is a backward edge of Q and is removed. (Similarly at a vertex where Q leaves ℘.)
    Thus, the graph P' can be uniquely split into family ℘' of (j+1) xy-paths: after an initial step from a, there is only one way to step within P' until we reach b.
    
    In the figure, the initial family ℘ of 3 independent ab-paths admits an augmenting xy-path Q, which has three stretches of backwards motion along the previous paths. By removing these backward edges, we obtain a set of edges which can easily be split up into a new family ℘' of 4 independent ab-paths.
  - Case (ii): If no augmenting path Q can reach b, then there is a subgraph G' ⊂ G−y, consisting of all vertices which can be reached by some path Q obeying the augmenting path rules. Let ℘ = {P₁,..., P_k}, and for each P_i , let v_i be the last vertex of P_i lying in G'. (If a is the only vertex of P_i ∩ G', then take v_i to be the second vertex of P_i.)
    Claim: Any ab-path R in G must contain some v_i , so that G − {v₁,...,v_k} is disconnected. Indeed, consider the edge wz where R steps out of G', meaning w ∈ G', z ∉ G'. If w is not on any path P_i, then we could take an augmenting path aQw and extend it to the augmenting path Q' = aQwz, giving the contradiction that z ∈ G'. If w ∈ P_i but w is not the last vertex of P_i in G', then we can take an augmenting aQv_i and extend it backward to an augmenting path Q' = aQv_iPwz, again giving the contradicition z ∈ G'. The remaining possibilities are w = v_i or wz = av_i , so R must contain v_i .
Planar Graphs: Math 481 Graph Notes at bottom, [B] Ch I.4
Kuratowski Theorem: [D] Ch 4.4, ⊞ Kuratowski Lemmas
1. Two-Connected Structure Lemma: [D] 3.1.1. Every 2-connected graph G is either a cycle, or G = H ⊔ P where H is a 2-connected subgraph and P is an ab-path with H ∩ P = {a,b}.
2. Two-Connected Face Lemma: [D] 4.2.6. In a planar drawing of a 2-connected graph G, every face F is bounded by a cycle.
3. Three-Connected Face Lemma: [D] 4.2.7. In a planar drawing of a 3-connected graph G, the face boundaries are precisely the non-separating induced cycles: that is, those cycles C such that non-adjacent vertices of C are also non-adjacent in G, and G−C is connected.
4. Three-Connected Contraction Lemma: [D] 3.2.4. Every 3-connected graph G is either K₄ or it contains an edge xy such that G' = G/xy is also 3-connected.
  Proof: Suppose G is 3-connected, and take any edge xy of G. If G/xy is not 3-connected, then there is some x' such that {x,y,x'} separates G. Now, x' has neighbors in all components of G−{x,y,x'}, since otherwise {x,y} would separate G. Take an edge x'y' such that y' lies in the smallest component C of G−{x,y,x'}.
  If G/x'y' is not 3-connected, there is some x'' such that {x',y',x''} disconnects G. Now, y' has neighbors in at least two components of G−{x',y',x''}, since otherwise {x',x''} would separate G. Take an edge y'z such that z ∈ D, a component of G−{x',y',x''} not containing xy. Then D ⊂ C, since D = D−{x,y,x'} ⊂ G−{x,y,x'} is connected, and zy' ∈ C. Also y' ∈ C−D, so |D| < |C|.
  We can continue this way, obtaining a separating set {x'',y'',x'''}, with an even smaller component E, etc. This process can only come to an end with a 3-connected G/x⁽ⁱ⁾y⁽ⁱ⁾.
5. Kuratowski Minor Lemma: [D] 4.4.2. A graph G contains a contraction minor IK₅ or IK_3,3 if and only if it contains a topological minor TK₅ or TK_3,3.
6. Three-Connected Kuratowski Theorem: [D] 4.4.3. Any 3-connected G either has a planar drawing or contains a TK₅ or TK_3,3.
  Proof: For G ≠ K₄, consider a 3-connected contraction G' = G/xy (Lemma iv). If G' contains IK₅ or IK_3,3, then by definition so does G; and hence G contains TK₅ or TK_3,3 (Lemma v).
  Otherwise, assume a planar drawing of G' = G/xy, with xy ∈ E(G) contracted to v_xy ∈ V(G'). Then v_xy lies inside a face F of the 2-connected graph G'−v_xy, surrounded by a boundary cycle C (Lemma ii) containing all neighbors of v_xy, i.e. all x', x'',... ∈ Γ_G(x) and y', y'',... ∈ Γ_G(y). We can draw x in place of v_xy and all edges xx' ∈ E(G) in place of the corresponding v_xyx' ∈ E(G').
  It only remains to draw the edges xy, yy' ∈ E(G). This is easy if the neighbors x', x'',..., y', y'',... lie in a convenient configuration around C. Otherwise, the configuration of 4 distinct vertices x',y',x'',y'' in order around C constitutes a TK_3,3 ⊂ G; the configuration of 3 coinciding vertices x' = y', x'' = y'', x''' = y''' constitutes a TK₅ ⊂ G.
7. Max Planar Lemma: [D] 4.4.5. If G contains no minor TK₅ or TK_3,3, but G+xy does contain such a minor for every xy ∉ E(G), then G is 3-connected.
8. Kuratowski Theorem: G is planar if and only if G contains no toplogical minor TK₅ or TK_3,3, or equivalently no contraction minor IK₅ or IK_3,3.
  Proof: If G contains a TK₅ or TK_3,3, it is non-planar by Euler Theorem and the Edge-Region Inequality. Otherwise, we may add a maximal set of edges without creating a TK₅ or TK_3,3 until we obtain a 3-connected G' ⊃ G (Lemma vii). Now a planar drawing of G' (Lemma vi) contains a drawing of G.
Fáry Theorem
Vertex Coloring: Math 481 Graph Notes at bottom, [B] Ch V.1, [D] Ch 5.1−5.2
Graphs on Surfaces: [B] Ch V.3, Heawood Theorem
Edge Coloring: [B] Ch V.2, [D] Ch 5.3, Vizing Theorem
Chvatal Art Gallery Theorem: Proofs from the Book, Ch 39, p 265
Extremal Graph Theory: [B] Ch IV.2, IV.4, [D] Ch 7.1
Hadwiger Conjecture: [D] Ch 7.3
Cayley and Schreier Graphs: [B] Ch VIII.1
Probablistic Graph Theory: [B] Ch VII.1−VII.3, [D] Ch 11.1−11.4.
Spectral Graph Theory: [B] Ch VIII.2; Fan Chung Spectral Graph Theory (AMS)
Expanders and switching networks: Chung Ch. 6.4
Eigenvalues using Rayleigh quotient: Wikipedia, Horn & Johnson Matrix Analysis Ch 4.2 (text, Cambridge, MSU).
Exercise: Consider the k-regular graph G on vertices ℤ/nℤ with edges (i, i+j) for j = ±1, . . . , ±⌊½k⌋ and possibly j = ½n. Then G has cyclic symmetry, and its adjacency matrix is a circulant matrix A = p(C), a polynomial in the n-cycle permutation matrix C. Hence its eigenvectors are the same geometric series vectors as for C, and its eigenvalues are p(ζ) for all n^th roots of unity ζ.
Ramanujan Graphs: explicit expanding Cayley graphs
[L] Alexander Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures (Springer, MSU)
[DSV] Davidoff, Sarnak, and Valette, Elementary number theory, group theory, and Ramanujan graphs (Cambridge, MSU)
- Probablistic existence of expanders: [L] Ch 1.2
- Finite linear group PSL₂(F_q): [DSV] Ch 3.1, 3.2
- Integer quaternions: [DSV] Ch 2, esp. 2.6
- Definition of expander graphs X^p,q: [DSV] Ch 4.2 <\ul>
Previous Math 881: 2005 1, 2; 2006 1, 2.

MSU MATHEMATICS