Syllabus The course will focus on expanders, extremely useful graphs which are highly connected yet have relatively few edges. These graphs are constructed using an amazing variety of mathematical tools.We will cover the necessary background starting from basic definitions.
Elementary theory
Types of graphs: trees, planarity, coloring
Flows and connectivity: Theorems of Ford-Fulkerson, Menger, Hall
Expanders: definitions, network applications
Probabalistic theory
Basics of probability
Erdos: girth vs coloring number
Existence of expanders
Spectral theory
Heat equation & eigenvalues
Spectral vs connectivity properties
Spectrum of the k-regular tree: generating functions
Required Text B. Bollobás, Modern Graph Theory (Springer 1998). The bookstore seems not to have registered my book order, so you might want to order it directly from Amazon.com.
Fri class at 2:30: From now on, Friday lectures will be 2:30--3:20 in the usual roomWells C-212.
Old Homework: I will collect and grade only homework marked with ♠, but it is essential for your understanding to do all problems. I will sometimes give quizzes based on the HW, usually on Fridays, to be announced the previous Monday. Chapter numbers refer to the Bollobás text.
HW 1/13 Reference: Ch I.1, I.2 We will use graph to mean a simple graph G = (V,E): at most one edge between each pair of distinct vertices, e = v1v2 . A multi-graph may have multiple edges and loops from a vertex to itself.
♠ For arbitrary k < n , does there always exist some connected k-regular graph G with n vertices? If not, classify the (k,n) for which there do exist such graphs. Hint: Experiment with small examples of (k,n).Use a simple result we proved in class. If you can't give a complete answer, give as many partial results as possible. Divide the problem in two parts:
Prove that a certain condition on (k,n) is necessary: such a graph is impossible without the condition.
Prove that this condition is sufficient by constructinga graph for each allowed value of (k,n).
Recall that the heat equation on a graph G = (V,E), k-regular with n vertices, is given as follows. A heat function H : V-->R gives the temperature H(v) at each vertex. We represent the function H by its list of values at the n vertices, namely as a vector in Rn. The adjacency matrix A is an n × n matrix with entry aij = 1 if e = vivj ∈ E, and aij = 0 otherwise. We normalize this by taking D = A/k. Now the heat equation governs the evolution of a sequence of heat functions H(t) for t = 0,1,2,..., according to: H(t+1) = D*H(t), where * means matrix multiplication. Experiment with the heat equation on the complete graph K3 (a triangle).Compute the eigenvalues and eigenvectors of D, and relate these to the heat evolution. Now compute the eigenvalues for the n-vertex complete graph Kn with n(n-1)/2 edges.
A tree T is a graph which is connected and acyclic. Show that this is equivalent to:
Any two of the three properties: T is connected; T is acyclic; T has n vertices and n-1 edges.
T is minimally connected: removing any edge disconnects T.
T is maximally acyclic: adding any edge creates a cycle.
T has a unique path between any two vertices.
Kruskal's algorithm efficiently generates a spanning tree of a graph G . Start with a graph T0 having the same vertices as G but no edges. If Ti has already been chosen, define Ti+1 := Ti + e , where e is an edge of G chosen so that Ti+1 is acyclic. If there is no such e, then output the graph T := Ti. Prove that the output T is a spanning tree of G.(By the way, find an efficient algorithm to determine if a graph is acyclic.)
Prove: If a tree T has a vertex v with degree Δ, then T has at least Δ leaves. Hint: Take maximal paths which start at v.
Count the following types of structures using Cayley's Theorem.
A rooted tree is a tree together with an extra piece of data: one of the vertices is designated as the root. Thus, there are three ways to make the tree 3--1--2 into a rooted tree: 3--1--2 or 3--1--2 or 3--1--2, where I use boldface for the designated root. Question: How many rooted trees are there on n labelled vertices?
A forest is an acyclic graph. The connected components of a forest are trees. A rooted forest is a forest together with a designated root on each component. For example,
1--324
is a forest whose components are the three rooted trees 1--3 and 2 and 4. Question: How many rooted forests are there for n = 1, 2, 3 labelled vertices? How many for a general n?
Joyal's proof of Cayley's Theorem is via a bijection between vertebrates (doubly-rooted trees) (T,v,v') and functions f from the set {1,...,n} to itself.
Given (T,v,v'), draw the "spine", the unique path from v to v'.
Consider the sequence of numbered vertices on the spine as a permutation π of these vertices from their numerical order.
Write the permutation π in cycle form, and draw the corresponding directed graph G with an arrow from each i to its permuted image π(i).
Each vertex v of the spine in T has a tree Tv of non-spine edges connected to it. Define the directed graph G' by reconnecting each Tv to its corresponding vertex v in G, with all its edges directed toward v.
Interpret the graph G' as the function graph of some f: namely f(i) = j whenever G' has an edge from i to j.
Problem: Define the reverse algorithm taking f to (T,v,v'), in a way precise enough to program into a computer. The main difficulty is how to determine the vertices of the function graph G' which will become the spine of T. Problem: Compute the vertebrates corresponding to some functions f. How are various properties of f reflected in (T,v,v')? For example, what if f is one-to-one? Onto? A permutation?
HW 1/20 Reference: Ch I.4, V.3.
Recall the two facts we learned about a connected planar graph G with n vertices, m edges, and r regions (including the infinite region).
Euler's Theorem: n - m + r = 2 .
Region inequality: g r ≤ ∑R d(R) ≤ 2 m , where the girth g is the length of the shortest cycle of G; the sum is over all regions R of G; and the degree d(R) is the number of distinct edges on the boundary of R.
Use these formulas to show that the following graphs are non-planar (i.e., have no possible planar drawing):
K5, the complete graph on 5 vertices.
K3,3, the complete bipartite graph in which each of 3 non-adjacent vertices is connected to 3 other non-adjacent vertices. That is, V = {x1,x2,x3,y1,y2,y3} andE = { xiyj for all i,j } .
Subdividing a graph means we repeatedly replace an edge e = xy by a path (xz,zy), where z is a new vertex of degree 2. Kuratowski's Theorem gives a guaranteed way to prove a graph is non-planar: if G is non-planar, it is possible to find a subgraph which is a subdivision of K3,3 or K5. Note that G need not contain K3,3 or K5 directly as a subgraph: G only contains a subdivision of one of these. That is, you must find 3 vertices in G which connect to 3 other vertices by non-intersecting paths; or 5 vertices which all connect to each other by non-intersecting paths. Non-intersecting means no common vertices within the abstract graph G. (In a drawing, the paths must cross each other, precisely because K3,3 and K5 are not planar.)
The Petersen graph P has 10 vertices V = { xi , yj for i = 0,1,2,3,4 } and 15 edges:
E = { xiyi ,xixi+1 , yiyi+2 for i = 0,1,2,3,4 }
(You get a pretty picture if you arrange the xi's as the vertices of a pentagon, and the yi's as a the vertices of a smaller pentagon inside the first.) Show that P is non-planar. That is, explicitly find a subdivision of K3,3 or K5 inside P.
Use Kuratowski's Theorem to classify all the planar bipartite graphs Kn,m . That is, give a condition on (n,m) which prohibits the graph from being planar, and give a planar drawing for the graph in all other cases.
A planar graph is maximal if all its regions (including the unbounded region) are triangles (bounded by exactly 3 edges) If G has n vertices, m edges and r regions, determine m and r in terms of n.
♠ Analogously to last week's problem, classify the possible (k,n) such that there exists a connected k-regular n-vertex graph which is planar. This again involves proving some necessary conditions on (k,n), then giving constructions of explicit graphs for each allowed value of (k,n). Hint: Use our inequalities to show k ≤ 5. Then treat the cases k = 2,3,4,5 separately. The Platonic solids are crucial small examples. Whenever possible, use inductive constructions on n which produce new graphs from old ones . Solution:Paper by Laszlo Szabo. He works with circle packings, but the planar graphs we want are exactly the adjacency graphs of the circles. The graphs exist (and are constructed) for:
k = 2 , n ≥ 3
k = 3 , even n ≥ 4
k = 4 , n ≥ 6 , n ≠ 7
k = 5 , even n ≥ 12 , n ≠ 14
The edge-graphs of Platonic solids are the bi-regular planar graphs, meaning that every vertex has degree d(v) = k and every region has degree d(R) = d , where k, d ≥ 3. Letting n, m, and r be the number of vertices, edges, and regions, we have:
n - m + r = 2 , kn = 2m = dr .
Review the arguments establishing these equations. Solve them for (n,m,r) to obtain:
n = 4d / D , m = 2kd / D , r = 4k / D , where D = 2k + 2d -kd .
Use the inequalities D > 0 and k,d ≥ 3 to establish that k,d < 6. Now classify the Platonic solids, as I did in class.Draw the planar graphs forced by these values of (k,d). Give better drawings, for example drawing the edges as straight line segments.
We defined a bipartite graph as a 2-colorable graph. Prove that G is bipartite if and only if G contains no cycles of odd length.
Determine the chromatic number χ(G) for the following graphs, and prove your answer. To get upper bounds on χ(G), exhibit a proper coloring. To show that your coloring is minimal, use the fact that χ(G) ≥ χ(H) for any subgraph H ⊂ G, or other arguments.
G = T, any tree or forest
G = Cn, a cycle with n vertices.
G = Wn+1, the wheel graph which consists of an n-cycle together with an extra vertex connected to all the vertices of the n-cycle.
Graph coloring was originally motivated by map coloring. Print out this map of the US (print in Landscape orientation), draw a vertex inside each state, and an edge between each pair of adjacent states. (States are not adjacent if they only share a corner, such as Utah and New Mexico.) Now a proper coloring of the graph gives a coloring of the map with adjacent states having different colors. Give a minimal proper coloring of the states. That is, mark the states with colors 1,2,3, etc., as few as possible so that adjacent states have different colors. Prove that your coloring is optimal. Hint: Look at the states around Nevada.
Suppose we try to adapt our proof of the 5-Color Theorem to prove the 4-Color Theorem. That is, remove a vertex v of degree 5, and assume we have a 4-coloring of G' = G - v. Now rearrange the colors on G' just as before, producing a 4-coloring of G. Question: Explain exactly where this proof breaks down.
♠ For a graph G, the clique number ω(G) = k is the size of the largest complete subgraph Kk ⊂ G. Clearly the chromatic number satisfies:
χ(G) ≥ ω(G) ,
since χ(Kk) = k .Show that this is not in general an equality: even if the graph requires k colors, it might not contain any Kk . Here are 4 versions of the problem, in increasing order of difficulty:
Find some graph such that χ(G) > ω(G) .
For each k, find a graph G with χ(G) > ω(G) ≥ k .
For each k, find a graph G with χ(G) - ω(G) ≥ k .
For each k, find a graph G with χ(G) ≥ k and girth(G) ≥ k . Note that if girth(G) ≥ 4 then ω(G) = 2 .
Solution: Let G1 # G2 denote the disjoint union of the graphs, with an edge added between every vertex of G1 and every vertex of G2:
G1 # G2= G1 ∪ G2 ∪ Kn1n2
where Gi has ni vertices.Then it is easily seen that:
Thus if G = C5 # ... # C5 (k times) we have χ(G) = 3k and ω(G) = 2k.
Recall the chromatic polynomial
PG(k) := # proper colorings of G with k colors .
We showed that this is indeed a polynomial in k:
PG(k) = kn + an-1kn-1 + ... + a1k
by repeatedly applying the deletion-retraction recurrence:
PG(k) := PG-e(k) - PG/e(k)
where G-e means G with the edge e deleted, and G/e means the graph with e contracted (replace the two end vertices e = xy by a single new vertex z having the same neighbors as x and y).
Use common sense to compute PG(k) for the complete graph Kn and its complement, the empty graph Kn having no edges.
Use the recurrence to compute PG(k) for some basic graphs such as the path P4 ,the cycle C4 , and then recursively Pn and Cn for all n.
Carefully examine the deletion-contraction recurrence for PG(k) to show that the leading term is always kn (with coefficient 1), and the constant term is always 0.
Extra Credit: Prove the result of Richard Stanley:
PG(-1) = (-1)n × #(acyclic orientations of G) ,
meaning ways to give a direction to each edge of G so that there are no oriented cycles x0 → x1 → ... → xr = x0 . For example, the triangle G = K3 has 3 edges, each of which can be oriented in 2 ways, so there are 23 = 8 orientations altogether. But 2 of these make G into an oriented cycle, so there are 6 acyclic orientations. Now, PG(k) = k(k-1)(k-2), and PG(-1) = -6 = (-1)3 6 . Hint: prove that the quantity on the right side of the equation satisfies the same recurrence as the coloring polynomial on the left.
HW 2/3 Reference: Ch III.1--III.3.
♠Definitions: Recall that in a bipartite graph G = (V,E), we split V = A ∪ B, such that all edges go between A and B. A matching of A to B is a set of edges M ⊂ E such that every a ∈ A is on exactly one edge of M, and every b ∈ B is on at most one edge of M. That is, if A is a set of women, B a set of men, and G is the graph of acceptable mates for each woman, then a matching is a scheme for pairing off each woman with a man, though some men can remain single. Hall's Matching Theorem: There exists a matching of A to B if and only if |A'| ≤ |N(A')| for every set A' ⊂ A. Here N(A') ⊂ B denotes the set of neighbors of A' . Problem: Write a complete proof of Hall's Matching Theorem, assuming the Max-Flow/Min-Cut Theorem. As in class, associate to G the network (G',c,s,t), where G' is G along with an two extra vertices s, t, and with extra edges from s to each a ∈ A and from each b ∈ B to t. Also the capacity function c = 1 for all edges. Show that a flow of volume k is equivalent to a partial matching of a k-element set A' ⊂ A with a k-element subset of B. Show that the hypothesis |A'| ≤ |N(A')| guarantees a flow with volume n = |A| . Hint: Suppose the max flow is < n . Then examine the corresponding min cut, with can be split as S = SA ∪ SB and the complement T = TA ∪ TB .Now consider the capacity of this cut in the network, and find a subset A' ⊂ A with |A'| < |N(A')| .Or can you do this without proof by contradiction? Also, don't forget to prove that Hall's Condition is necessary for a matching. Note: I am not looking for just any proof of Hall's Theorem (you can find three in Bollobas), but a proof that relates this theorem to the Max-Flow/Min-Cut machine. Solution without contradiction, which contains ideas from several of your classmates.
Prove the vertex version of Menger's Theorem for G by applying MF/MC to the network G± defined as follows: for each vertex v of G , there are two vertices v+, v- of G± , and a directed edge e = (v+, v-). For each edge e = ab of G, there are two directed edges (a-, b+) and (b-, a+). Capacity of every edge is c = 1.
Let κV(G) denote the vertex-connectivity of G ; κE(G) the edge-connectivity; and δ(G) the minimum degree of a vertex. Show that we always have:
κV(G) ≤ κE(G) ≤ δ(G) .
Find examples of G for which each of these inequalties is a strict < .
For any k ≤ m , find examples with κV(G) = k and κE(G) = m .
Determine κV(G) and κE(G) for all our favorite graphs: trees, the platonic solid graphs, the Petersen graph, complete graphs Kn, and complete bipartite graphs Km,n,. (By definition, the complete graph has κV(Kn) := n-1 ). Hint: Use Menger's Theorem and the inequalities above.
Show that any maximal planar graph has 3 ≤ κV(G) ≤ κE(G) ≤ 5. Hint: Any planar graph has a vertex of degree ≤ 5.(My previous hint was incorrect.) Also: are there maximal planar G for which each of the possibilities (κV(G), κE(G)) = (3,3), (3,4), (3,5), (4,4), (4,5), (5,5) occurs?
HW 2/10Solutions We have defined several measures of graph connectivity which are not as sensitive to small-scale phenomena as the classical connectivity κV(G) or κE(G), and which better capture the features we seek in a robustly connected network. Let G = (V,E) be a simple graph with n vertices. Let S ⊂ V be any non-empty set of vertices with S ≠ V, and let S~ = V-S denote the complement.
Vertex Cheeger constant (restricted):
g'(G) := min0 < |S| ≤ n/2 |δ(S)| / |S|
Here we define the boundary of S as: δ(S) := N(S)-S , the set of neighbors of S not including S itself. This is the most important measure.
Here E(S,S~) is the set of edges between S and S~. In this case there is no difference between the restricted and unrestricted version, since E(S~,S) = E(S,S~).
Expander constant:
c(G) := minS |δ(S)|·n / |S|·|S~| = minS |δ(S)| / |S|·( 1 - |S|/n )
♠ Evaluate (or at least estimate) g', g, h, and c for our favorite graphs: the cycle Cn , the complete graph Kn , and the Platonic solid graphs . In each case, try to minimize first over all sets S ⊂ V of a given size |S| = s ; then minimize over 0 < s < n = |V|. Even for the Platonic solids, you should be able to give a pretty well-justified answer without pages of cases: I'm not expecting a formal proof.
♠ Evaluate or estimate g'(G), where G is the m×m grid I discussed in class. G has n = m² vertices (i , j) mod m, each with four edges (i , j)--(i±1 , j), (i , j)--(i , j±1), wrapping around at the boundaries.
Try this for m = 10 and m = 20 on a piece of graph paper. Is the minimum boundary δ(S) really achieved for a given s = |S| by the set S = vertices inside a circle of radius r = √(s/π) ? I'm not so sure myself.
Assuming this for large m, try some computer experiments: define S to be the vertices inside a circle of area n/2 , and test each element of the large grid to see if it is in the boundary δ(S). Test my assertion that
g'(G) ≈ a/m = a /√n as n → ∞ ,
where a is a constant. Estimate this constant by assuming δ(S) ≈ 2πr , and see if your experiments confirm this.
The above measures are asymptotically equivalent in following sense. Fix a k, and suppose G is any k-regular graph, or at least d(v) ≤ k for all vertices v. Then for each pair of measures a(G), b(G) above, there exist constants λ > μ > 0 (possibly depending on k but independent of n) such that
λ a(G) ≥ b(G) ≥ μ a(G) .
This is relevant because we will be interested in infinite families of k-regular graphs, assuring that their connectivity does not tend to zero for larger and larger G in our family (i.e., it stays larger than some fixed ε > 0). But then a(G) > ε assures that b(G) > μ ε > 0 ,and b(G) > ε assures that a(G) > 1/λ ε > 0 . Problem: Show that g' , g , h , and c are all asymptotically equivalent for k-regular graphs G by proving an appropriate inequality λ a(G) ≥ b(G) ≥ μ a(G) for each pair. For example, it is easy to see that c(G) ≥ g(G) ≥ 1/2 c(G) . To compare g(G) ≥ μ g(G)' , use that |δ(S)| ≥ 1/k |δ(S~)| . You do not have to consider each pair separately, since if a(G) ≥ α b(G) and b(G) ≥ β c(G) , then a(G) ≥ αβ c(G) . Check that the values you computed for cycles, complete graphs, and Platonic solids satisfy the bounds you computed above.
Now we consider a connectivity measure specifically for bipartite graphs G' = (V',E') with V' = V+ ∪ V- and |V+| = |V-| = n . Let S ⊂ V+ a set of "positive" vertices.
Bipartite expander constant:
c'(G) + 1 := min|S| < n/2 |N(S)| / |S|
The +1 term on the left is because we expect G' to obey Hall's Condition |N(S)| ≥ |S| for any positive S, so that S can be matched to a corresponding negative set S'.Then c' measures the neighbors of S not including S' .
Ordinary graphs G = (V,E) and bipartite graphs G' can be related as follows.
Given G, we can construct G' = (V',E'): for each vertex v ∈ V define two vertices v+ ∈ V+ and v- ∈ V-, and for each edge xy ∈ E, define edges
x+x- , y+y- ,x+y- , y+x- ∈ E' .
Given some bipartite G' with a matching of V+ to V- , denote the match of v+ by v- . Then define G as having a vertex v ∈ V for each pair v± ∈ V' , and an edge xy ∈ E for every edge x+y- ∈ E' with y- ≠ x- .
Problem: (a) Show that if we are given k-regular G and the corresponding (k+1)-regular bipartite G', then g'(G) = c'(G') . (b) Show that if we are given bipartite G' and the corresponding G, then g'(G) and c'(G') are asymptotically equivalent (though not necessarily equal).
HW 2/17Recall the following definitions and constructions from class:
A super-concentrator S(n) is powerful switching network, consisting of a (directed or undirected) graph having subsets of vertices I, O ⊂ V (called the inputs and outputs) with |I| = |O| = n , such that for any subsets A ⊂ I and B ⊂ O with |A| = |B| , there are disjoint paths in S(n) connecting A to B. That is, if |A| = |B| = k , there exist k vertex-disjoint paths starting in A and ending in B. Obviously Kn,n is a super-concentrator, but a general S(n) need not be bipartite, and it may have vertices between the inputs and outputs: |V| may be much greater than 2n.
A concentrator C(n,m) is a (directed or undirected) graph having I , O ⊂ V with |I| = n and |O| = m , where n/2 ≤ m , such that for any subset A ⊂ I with |A| ≤ n/2 , there are vertex-disjoint paths in C(n,m) connecting A to O. That is, if |A| = k ≤ n/2 , there exist k disjoint paths starting in A and ending somewhere in O. Again Kn,m is a concentrator, but C(n,m) need not be bipartite. We see that a concentrator is weaker than a super-concentrator because we require at most n/2 paths, and we specify only their start points in I, while their end points can be anywhere in O.
We gave a recursive construction of super-concentrators S(n) built up from smaller components according to the scheme below:expander ⇒ bipartite expander ⇒ concentrator ⇒ super-concentrator.
Expander G , k-regular on n vertices ⇒ Bipartite expander G' = G± , (k+1)-regular with n+n vertices, c'(G') = g'(G). For each vertex x ∈ G , we define twin vertices x+ , x- ∈ G' and a directed edge x+→x- ; and for each edge x--y ∈ G , we define edges x+→y- , y+→x- ∈ G' .
Bipartite expander G' with vertices V+ ∪ V- having |V+| = |V-| = m , (k+1)-regular with c'(G') ≥ 1/(r-1) ⇒ bipartite concentrator C(n,m) with n = m(r+1)/r and (k+2)m edges. We define C(n,m) with vertices I = V+ ∪ V0 , where V0 := { v01 , ... , v0m/r } ; and O = V+ , which we split into m/r equal subsets:
O = V+ = V+1 ∪ ... ∪ V+m/r with |V+j| = r .
The edges of C(n,m) include the edges of G' from V+ to V- , as well as new edges from V0 to V+ , namely an edge from v0j to every vertex of V+j .
Super-concentrator S(m) with p edges and concentrator C(n,m) with q edges ⇒ super-concentrator S(n) with n+p+2q edges. Take left and right copies of the concentrator: CL and CR with respective inputs and outputs IL ∪ OL and IR ∪ OR .Let S(m) have inputs and outputs IM ∪ OM . We get S(n) by placing CL on the left, S(m) in the middle, and a reflected copy of CR on the right, and then identifying OL with IM and OM with OR ; and we also add one edge from each vertex vL ∈ IL to its twin vR ∈ IR . The resulting S(n) has inputs I = IL and outputs O = IR : that is, inputs of CL become inputs of S(n), and inputs of CR(n,m) become outputs of S(n). We connect our three graphs
♠ Problem: Construct your own examples of super-concentrators and concentrators with fewer edges than the complete bipartite graphs. The undirected versions are easier. For example, we could define an undirected S(2) by:
V = I ∪ O = {a1,a2} ∪ {b1,b2} , E = {a1b1 , a2b2, b1b1} .
Similarly, we could define an undirected C(3,2) by:
V = I ∪ O = {a1,a2,a3} ∪ {b1,b2} , E = {a1b1 ,a2b2 , a3a2} .
Suppose a superconcentrator S(n) is bipartite and directed with all edges from I to O. Show that S(n) = Kn,n. Is the corresponding statement true for a bipartite directed concentrator C(n,m) ?
Can you use any of these constructions with some examples of G, G', C(n,m), S(m) to get concentrators and/or super-concentrators with fewer edges than the complete graphs?
HW 3/3 Probablistic graph theory. Reference: Bollobás Ch VII.1. Given p ∈ (0,1), recall the probability distribution G(n,p), which is the set of all graphs G on a set of vertices V = {v1,...,vn} endowed with the probability function
P(G) := pm q(n | 2) - m ,
where q = 1-p , m is the number of edges of G, and (n | 2) := (n choose 2) = ½ n(n-1) . That is, the probability of randomly choosing G is defined to be P(G) . If p = q = ½ then this is the uniform distribution, in which each graph has the same probability of being chosen. If p < ½, then our selection is biased in favor of graphs with fewer edges.
Prove the key properties of this probability distribution.
For a given potential edge e = vivj , the probablility that e is present in G is: P(e ∈ G) = p .
The presence of any two distinct edges e,e' are independent events:
P(e,e' ∈ G) = P(e ∈ G) P(e' ∈ G) = p2 .
What is the probability that G ∈ G(n,p) has exactly m edges, for each fixed m?
Recall that if F(G) is a function on graphs, then the expected value F(G) for G ∈ G(n,p) is defined to be:
E(F) := ∑G F(G) P(G) .
The most useful property of expectation is that it is linear: E(F1 + F2) = E(F1) + E(F2).
Show that if F(G) is the number of edges of G, then the expected number of edges is E(F) = p (n | 2) .
What is the expected degree of a fixed vertex vi ∈ G? That is, find the expectation of F(G) := d(vi).
What is the expected number of Kr subgraphs inside G? (These subgraphs may overlap.)
We showed that for k fixed, p fixed, and n → ∞, almost every graph in G(n,p) is k-connected. This is still true if we allow p to dwindle to zero: p = p(n) → 0 as n → ∞ , so that the expected number of edges, p(n) (n | 2) grows less than quadratically. Determine the minimal p(n) for which our argument works. For example, can we take p(n) = c/n ?
Asymptotic estimates
Show that for any constants α, β, γ > 0, we have:
limn → ∞ nα / exp(β nγ) = 0 .
Prove the following strengthened version of a result from class. If we fix k and let p(n) = 6 k ln(n) / n , then for G ∈ G(n,p(n)) we have P(χ(G) ≥ 2k) → 1 as n → ∞ , where χ(G) is the coloring number.
Recall our proof of the Erdos Theorem that there exists a graph H with girth(H) > k and with χ(H) > k. We showed that we could construct such a graph H with n/2 vertices provided that for a random G ∈ G(n,p(n)), where p(n) is chosen appropriately, the two probabilities:
P( cyc≤k(G) ≥ n/2 )
and
P( ∃v1,...,vr independent, where r = n / 2k )
are both less than ½.Here cyc≤k(G) is the number of cycles of length ≤ k in G. Let k = 3. Using our estimates, find an n large enough to make the two probabilities < ½. Thus, how large would the corresponding H be? Extra Credit: Can you explicitly find such an H, with no 3-cycles and no proper 3-coloring?
We define the Ramsey number R(k)as the smallest size of V(G) whichforces G to contain k mutually adjacentvertices or k independent vertices:
n = |V(G)| ≥ R(k) ⇒ Kk ⊂ G or Kk~ ⊂ G ,
where Kk~ means the complement of Kk .
♠ Prove that R(3) = 6 . That is, any graph on n = 6 vertices contains a triangle K3 , or a set of 3 independent vertices K3~ . However, there exist graphs on n = 5 vertices with neither K3 nor K3~ . In everyday language: if you invite any 6 people to a party, then there are at least 3 who know each other, or 3 who are strangers to each other.
♠ Prove Erdös' lower bound:
R(k) > 2k/2 .
That is, for n ≤ 2k/2 there is an n-vertex graph containing neither Kk nor Kk~ . Hint: For G ∈ G(n,p) , an appropriate space of random graphs, estimate the probability:
P(Kk ⊂ G or Kk~ ⊂ G) .
Use basic estimates of the binomial coefficient(n | m) and of k! to show that this probability is < 1 .It is remarkable that this is essentially the best lower bound known for R(k).
Give an elementary argument to show R(k) ≤ 22k . That is, any graph with n ≥ 22k contains a Kk or a Kk~ . Hint: Since n is so large, any vertex v has either a large set of neighbors or of non-neighbors. Repeat the argument on this subset, and iterate k times. Bollobas Ch VI.1. gives an elementary proof that:
R(k) ≤ (2k-2 | k-1) ≤ 22k-2 / √k .
The best upper bound known is R(k) ≤ 22k / k .
HW 3/17: Probability and expanders. No HW to hand in. Solution Recall that we defined a probability space G"(k,n) with elements G" = G"(π1,...,πk) which are k-regular bipartite multi-graphs. The vertices are:
V+" ∪ V-" = {1+, ... , n+} ∪ {1-, ... , n-} ,
and the edges are defined by k permutations of n objects, π1,...,πk ∈ Perm(n) . Namely, for each i ≤ k and j ≤ n there is an edge ( j+ , πi( j )- ) .
To each G", we associated G', a k-regular bipartite simple graph. If D is the maximum multiplicity of a multi-edge in G", then G' has Dn+Dn vertices denoted
To get the edges of G', we replace each multi-edge (x+,y-) of multiplicity d in G" by a copy of a fixed graph B(d,D), a bipartite d-regular graph on D+D vertices. Indeed, we let B(d,D) := G"(π1',...,πd'), where πi : {1,...,D} → {1,...,D} is defined by: πi(j) = j + i mod D.
Prove that G' is indeed a k-regular bipartite simple graph satisfying Hall's Condition, |N(S')| ≥ |S'| for all S' ⊂ V+'.
Suppose that G" is a c'-expander, meaning that for any S" ⊂ V+" with |S"| ≤ n/2, we have |N(S")| ≥ (1+c') |S"|. Then prove that the corresponding G' is also a c'-expander.
Recall that if G' is k-regular bipartite on n+n vertices and satisfies Hall's Condition, then we can define an ordinary simple graph G on n' vertices, with vertex degrees deg(v) ≤ 2k-2 . Prove that the restricted Cheeger constant of G is bounded below by the bipartite Cheeger constant of G': that is, g'(G) ≥ c'(G'). That is, if c'(G') = ε, we have |δ(S)| ≥ ε |S| for any S ⊂ V(G) with |S| ≤ ½|V(G)|. Thus, the multi-graph expander G" ends up producing an ordinary expander G.
We write G" = G"(π1,...,πk), and we take the uniform probability distribution on all choices of π1,...,πk . We bounded the probability that G'' fails to be a c' = ½ expander:
P( c'(G'') < ½ ) = P( ∃S,T s.t. πi(S) ⊂ T ) ≤ ∑s=1n/2 R(s) ,
and (n || s) denotes a binomial coefficient. Here S,T run over sets of vertices with |S| = s ≤ ½ n and |T| = 3/2 s . We aim to show that this bound tends to zero as n → ∞ , provided k ≥ 4 .
For 1 ≤ s ≤ n/3 , show combinatorially that R(s)/R(s+1) ≥ 1 , so that R(1) ≥ R(s) for s in this range. Now prove:
∑s=1n/3 R(s) → 0 .
Remember that k ≥ 4 .
Use Stirling's approximation
n! ~ √(2πn) (n/e)n
to show that for a constant 0 < α < 1 andβ := 1 - α , we have:
(n || αn) ~ α-αn-½ β-βn-½ / √(2πn)
Here f(n) ~ g(n) means limn→∞ f(n) / g(n) = 1 : the percentage difference between f(n) and g(n) approaches zero.
Use the above to approximate R(s) for s = αn . Show that R(s) is monotone (increasing or decreasing) for n/3 ≤ s ≤ n/2 . Perhaps show that the derivative d/dα R(αn) ≠ 0 for 1/2 ≤ α ≤ 1/3 ?
Finally, show that
∑s = n/3n/2 R(s) ≤ n/6 max( R(n/3) , R(n/2) ) → 0
via your approximation for R(αn) .
HW 3/24 Spectrum of a graph. Reference: Bollobás Ch VIII.2. Quiz in class: Computing eigenvalues and eigenvectors (see Prob. 4 below).
We can parametrize the points of a circle by x ∈ R / Z , the real numbers with the identification x ≡ x + 1 for each x .A function on the circle is thus a real function with period one: f(x+1) = f(x) for all x . A heat function on the circle is:
ft(x) := temperature at the point x at time t .
Newton's law of heating and cooling implies that a heat function must obey the continuous heat equation:
(*) d/dt ft(x) = Δ ft(x) ,
where d/dt is the derivative with respect to t and the Laplace operator Δ := d² / (dx)² is the second derivative with respect to x .
Suppose f(x) , a function of x only, is an eigenfunction of the Laplace operator:
Δ f(x) = λ f(x)
for some constant λ ≤ 0 . Then show that
ft(x) = eλt f(x)
is a solution of the heat equation. This special heat function dies away exponentially over time, but does not change its shape as a function of x .
Show that for any m, the functions f(x) = cos(2πmx) and sin(2πmx) are both eigenfunctions of Δ , and determine the corresponding solutions of (*).
♠ Now let G be a k-regular graph with n vertices, and consider a function on G to be a function on the vertices, f : V → R .Define the adjacency operator A which takes a function f and gives another function Af :
Af(v) := ∑w∈N(v) f(w) ,
where N(v) means the neighbors in G. A discrete heat function is:
ft(v) = temperature at vertex v at time t ,
where t ∈ Z is an integer time value.We showed that the appropriate discrete version of theheat equation is:
(**) ft+1(v) = 1/k Aft(v) .
That is, the temperature at time t+1 is the average of the neighboring temperatures at time t.
Suppose f(v) , a function of v only, is an eigenfunction of the adjacency operator:
Af(v) = μ f(v) for all v ,
for some constant μ . Then show that:
ft(v) = ct f(v)
is a solution of the heat equation for an appropriate constant c . Again, this heat function dies away exponentially(provided |μ/k| < 1) but does not change its shape.
Let G = Cn , the n-cycle. Show that for any m = 0,1,...,n-1, the functions f(vj) = cos( 2πm j/n ) and sin( 2πm j/n ) are both eigenfunctions of A , and determine the corresponding solutions of (**).
Are the above 2n functions all linearly independent, or are some linear combinations of others? Find a basis of these functions, a maximal linearly independent subset.Hint: There should be n functions in your basis. Consider n odd and even separately.
Let G = Kn , the complete graph. Find a basis of n linearly independent eigenfunctions of A , and the corresponding solutions of (**).
Eigenvalues and convergence to uniform temperature.
Let G = C3= K3 , and consider the initial temperature value f0(v1) = 1 and other f0(vi) = 0 . Write the function f0 as a linear combination of eigenfunction basis f(1), f(2), f(3) of A . Explain how this controls the exponential convergence of ft to the uniform temperature distribution f∞(v) = 1/3 .
Do the same for G = C4 = K2,2 . How does the bipartiteness of the graph affect the temperature evolution? Recall that for a bipartite k-regular G , we have extreme eigenvalues μ0 = k and μn-1 = -k , whose eigenvectors do not die off for large t .
Now we translate the above into the language of vectors and matrices. Let us identify a function f with the vector of its values (f(v1),...,f(vn)) ∈ Rn , which we will think of as an n × 1 column vector. Now the adjacency operator corresponds to an n × n matrix, the adjacency matrix A ∈ Mn×n(R) with A = (aij) with aij = 1 if vivj ∈ E and aij = 0 otherwise. Multiplying the n × n matrix A with the n × 1 column vector f gives the column vector corresponding to Af . An eigenfunction of the adjacency operator corresponds to an eigenvector of the adjacency matrix, a vector f such that Af = μ f , a scalar multiple of f . It is known that A , being a symmetric real matrix, has a basis of n real eigenvectors, each with a real eigenvalue. Let us review how to find eigenvalues. First, the equation Af = μf is equivalent to:(A-μI)f = 0 , where μI is the scalar μ times the identity matrix. That is, μ is an eigenvalue iff A-μI is a singular (non-invertible) matrix; and recall that a matrix is singular iff its determinant is zero. Thus, to find the eigenvalues, we consider μ as an unknown, and find the roots of the characteristic polynomial:
P(μ) := det(A-μI) = 0 .
We can compute the determinant of a matrix Z = (zij) via the recurrence:
det(Z) = ∑i=1n (-1)izi1 det(Zi1) ,
where the matrix Zi1 means Z with the ith row and the 1st column deleted. Now, once we know an eigenvalue μ, we can find the corresponding eigenvectors by solving the system of linear equations (A-μI)x = 0 , where x = (x1,...,xn) is an unknown vector.We simplify the system by using the three operations of Gaussian elimination: multiplying an equation by a non-zero constant; adding a multiple of one equation to another; and switching two equations. Eventually, we can write some of the variables xj as combinations of other, independent, xj's . Setting one of the independent xj = 1 and the others to zero gives a basis vector. Problem: Use the above method to find the adjacency matrix of the following graphs:
G = K2 , a single edge
G = K1 ∪ K2 , an edge and an isolated vertex
G = C3 = K3 , a triangle
G = P3 , a path with 3 vertices
Verify in the above cases that the more connected k-regular graphs have smaller values of |μ / k|.
HW 3/31: Spectral gap and connectivity. Reference: Bollobás Ch VIII.2 Recall the discrete derivative operator D , which takes a function f on the n vertices to a function Df on the m edges: D : Rn → Rm , Df(xy) := f(y) - f(x). (We arbitrarily fix an orientation x→y for each edge xy.) We also have its transpose matrix DT : Rm → Rn , DTg(x) := ∑y←x g(xy) - ∑y→x g(yx) , the net outflow at a vertex under the flow g. Prove the following facts for a general connected k-regular graph G . Explicitly verify the facts for G = C3 and C4 .
For a k-regular graph G , we define the Laplacian L := DT D. Then we have L = kI - A , meaning k times the identity matrix minus the adjacency matrix.
The eigenvalues of L are 0 = λ0 < λ1 ≤ ... ≤λn-1 ≤ 2k.Indeed, λi = k - μi, where μi is the ith largest eigenvalue of the adjacency matrix A.
The Laplacian is a real symmetric matrix (equal to its transpose): L = LT . Its eigenvalues may be characterized as:
λ0 = min { (Lf • f) / (f • f) for f ∈ Rn } , λ1 = min { (Lf • f) / (f • f) for f ∈ Rn , f ⊥ f(0) } ,
where f(0) is an eigenvector of λ0 .By the above, this is equivalent to minimizing | Df |² / | f |² .
Suppose the edge Cheeger constant of G is achieved by h(G) = |E(S,S~)| / |S| for some vertex set S ⊂ V with |S| ≤ n/2 . (Here E(S,S~) is the set of edges between S and S~ := V-S.) Let fS ∈ Rn be the function:
fS(x) := |S~| for x ∈ S , fS(x) := -|S| for x ∈ S~ .
Hence: k - μ1 = λ1 ≤ 2 h(G) . Since h(G) ≤ g(G) ≤ g'(G), we obtain lower bounds for the vertex Cheeger constants in terms of λ1 .
Suppose G is a non-complete graph, and the vertex connectivity of G is achieved by a minimal set S of κ := κV(G) vertices which disconnects V-S into subsets A ∪ B with a := |A| and b := |B| . Thus V = A ∪ S ∪ B with E(A,B) = Ø . Let fS ∈ Rn be the function:
fS(x) := |B| for x ∈ A , fS(x) := 0 for x ∈ S , fS(x) := -|A| for x ∈ B .
Hence: k - μ1 = λ1 ≤ κV(G) . Note: This inequality does not hold for a complete graph G = Kn .
HW 4/7: Spectrum and chromatic number. Reference: Bollobás Ch VIII.2 Let G be a connected k-regular graph with n vertices. The adjacency matrix A has n eigenvalues:
μ0 > μ1 ≥ ...≥ μn-1 ,
with k = μ0 and μn-1 ≥ -k (equality ⇔ G is bipartite).
Define the trace of an n×n matrix X as the sum of the diagonal entries:tr(X) := ∑i xii . Show the following.
For any n×n matrices X,Y we have: tr(XY) = tr(XY) and tr(X-1YX) = tr(Y) .
If X is the matrix whose column vectors are the eigenvectors of A , then the matrix X-1AX is a diagonal matrix with entries μ0 ,..., μn-1 . Hint: Let ei = (0,...,1,...,0) be a standard basis vector of Rn . Then X ei = f(i-1) , an eigenvector of A . Show that ei are the eigenvectors of X-1AX .
Show that 0 = tr(A) = ∑i μi , meaning the n eigenvalues of any adjacency matrix add up to zero.
Theorem: We have the following relation between the spectrum of A and the chromatic number of G:
1 + k / |μn-1| ≤ χ(G) .
Verify the steps of the following proof for the graph G = C5 with the coloring c(v1) = c(v3) = 1 , c(v2) = c(v4) = 2 , c(v5) = 3 . Let χ := χ(G) be attained by a proper coloring c : V → {1,2,...,χ} . Let
ni := #{ x ∈ V s.t. c(x) = i } ,
the size of the color class i .
Define the color graphG as the multigraph with vertices {1,...,χ} and mij edges between i and j , where:
mij := #{ x,y ∈ V s.t. c(x) = i , c(y) = j , xy ∈ E(G) } .
Show that the degree of the vertex i is: deg(i) = ∑j mij = k ni .
Consider functions f(x) taking a real value on each vertex x ∈ V ; and also functions f(i) taking a real value on each color i . The space of vertex functions is Rn ; the space of color functions is Rχ . Define the weighted adjacency operator of G to be:
A : Rχ → Rχ Af(i) := ∑j mij /√(ninj) f(j) .
Note: This is corrected from the formula I gave in class. Then the function f(i) := √ni is an eigenfunction for A with eigenvalue k .
Define the following linear mapping from color functions to vertex functions:
S : Rχ → Rn , f → f = Sf f(x) := f(i) / √ni where i = c(x) .
The transpose of this operator is:
ST : Rn → Rχ , f → f = STf f(i) := ∑c(x)=i f(x) / √ni .
Then we have: |Sf| = |f| . Furthermore:
A = ST A S .
Lemma: The matrix A has χ real eigenvalues. We denote the extreme eigenvalues of A as μmax and μmin , and the extreme eigenvalues of A as μmax = μ0 and μmin = μn-1 . Then we have:
Since c is a proper coloring, all the diagonal entries of A vanish: mii = 0 . Therefore tr(A) = 0 .
Now we can prove the Theorem.We have:
0 = tr(A) = μmax + ... + μmin ≥ k + (χ-1)μmin ≥ k + (χ-1)μmin .
Moving χ to the left-hand side yieldsχ ≥ 1 - k / μmin . Sinceμmin = μn-1 < 0 , this is what we wanted.
♠We have found the following relations between the extreme non-trivial eigenvalues of A and graph invariants such as the edge expansion, the vertex connectivity, and the chromatic number:
k - μ1 ≤ 2 h(G) k - μ1 ≤ κV(G) 1 + k / |μn-1| ≤ χ(G) .
By examining the proofs of these inequalities, say as much as you can about those graphs G for which equality holds. For example, if k - μ1 = 2 h(G) , then h(G) must be achieved by a set of size |S| = n/2, so G must have an even number of vertices (though this is not sufficient for equality). Hint: The first inequality is easiest. Do the others if you can.
