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 4/14 Tree-bound for the spectrum of large k-regular graphs. In class we discussed the k-regular infinite tree T = T(k), and made the following analysis of generating functions.
W(z) = W(k)(z) := ∑i≥0 wizi = 1 + kz² + ... , where wi = wi(k) is the number of closed i-step walks in T = T(k) from the origin vertex.
N(z) = N(k)(z) := ∑i≥0 nizi = z² + (k-1)z4 + ... , where ni = ni(k) is the number of these closed i-step walks which never return to the orgin before the last step, and whose first step is fixed (that is, we fix a particular neighbor of the origin to visit first).
The basic laws of generating functions imply the relations W(z) = 1 / (1 - k N(z)) and N(z) = z2 / (1 - (k-1) N(z)) , which we may solve to get the explicit formula:
N(z) = ( 1 - (1 - 4(k-1)z²)½ ) / 2(k-1)
The smallest singular point of this function (the point where it ceases to be complex differentiable) is when 1 - 4(k-1)z² = 0 , namely z = 1 / 2(k-1)½ .
Thus (by a deep theorem of complex analysis) the radius of convergence of the Taylor series N(z) is the reciprocal 1/|z| = 2(k-1)½ .
The same analysis applies to the function W(z), and thus we can compute the spectral radius of T as:
μ(T) = R(T) := lim supi→∞ wi1/i = 2(k-1)½ .
In these exercises, we sketch a proof of the above result which does not use the deep complex analysis theorem relating the radius of convergence to the smallest singular point. Define the Catalan number Ci to be the number of closed walks in the non-negative integers N, starting from 0 and with 2i-steps of ±1. For example, C3 = 5 counts the walks
Let C(z) = ∑i≥0 Cizi = 1 + z + 2z2 + 5z3 + ... be the generating series.
Show that in the case k = 2, we have:N(2)(z) = z² C(z²) . Hint: Show combinatorially that the coefficients match: n2i(2) = Ci-1.
For general k, we have:
N(k)(z) = N(2)( (k-1)½ z ) / (k-1) = z² C( (k-1)½ z ) / (k-1) .
Hence n2i = n2i(k) = (k-1)i-1 Ci-1 .
Combinatorially prove the following recurrence for i > 0 :
Ci = C0Ci-1 + C1Ci-2 + ... + Ci-1C0 ,
and use this to show C(z) - 1 = zC(z)². Solve this to re-derive the formula for C(z). Hint: Divide a Catalan path at the first point when it returns to the origin.
Expand the formula for C(z) into a Taylor seriesusing the Newton binomial formula:
where X is any quantity and α is a real number (for example α = ½).Simplify to get the exact formulas:
Ci = (2i | i) / (i+1) , n2i = (k-1)i-1(2i-2 | i-1) / i ,
where (n | k) := (n choose k) = n! / k!(n-k)! .
Now show that asymptotically we have: w2i ~ ki Ci .
Use Stirling's asymptotic formula n! ~ √(2πn) (n/e)n to evaluate limi→∞ w2i1/2i and re-derive our formula for R(T).
A probablistic interpretation of the Catalan numbers. Consider the game in which you bet a dollar on each flip of a coin. What is the probability that you will break exactly even after 2i flips? Given that you broke even, what is the probability that you stayed ahead for the first 2i-1 flips?
Recall GL2(q), the general linear group of 2×2 invertible matrices with entries in the clock arithmetic field Zq = Z/qZ , where q is a prime number. We also have the special linear, projective general linear, and projective special linear groups:
SL2(q) = { A ∈ GL2(q) with det(A) = 1 } , PGL2(q) = GL2(q) / Zq× I , and PSL2(q) = SL2(q) / ±I .
Here we take the quotient of GL2(q) by the normal subgroup Zq× I of all invertible scalar matrices, and the quotient of SL2(q) by the normal subgroup ±I of determinant 1 scalar matrices.
Show that the number of elements of GL2(q) , SL2(q) , PGL2(q) , and PSL2(q) is respectively q(q²-1)(q-1) , q(q²-1) , q(q²-1) , ½q(q²-1) .
For Γ a group, define its center Z(Γ) = { g ∈ G | gg' = g'g for all g' ∈ Γ }. Show that Z(SL2(q)} = {±I} and Z(PGL2(q)) = {I, I'}, where I' = diag(1,-1) is a diagonal matrix. Conclude that PGL2(q) = PSL2(q) × C2 , the product of PSL2(q) and the two-element group.
For which q are SL2(q) and PGL2(q) isomorphic groups? That is, when is there a bijection φ between them which respects multiplication, or equivalently a way of relabelling the multiplication table of one group to obtain the other? For q = 2, both are non-commutative groups of order 6, so they must both be isomorphic to S3. I'm not sure of the full answer myself.
Define the matrices E =
1
1
0
1
F = transpose(E) , and D = diag(d,1) where d ∈ Zq× is a generator of the multiplicative group. Then {E,F} are generators for the group SL2(q), and thus for PSL2(q), and {E,F,D} generate GL2(q) and PGL2(q). Show the above for q = 2, and draw the Cayley graphs. Extra Credit: Show the above for q = 3, and for a general prime q .
Recall that for q = 4m+1 a prime, and p another prime with p = a2 mod q , we have the Ramanujan graph Xp,q , whichis the Cayley graph of PSL2(q) with respect to a certain set of "quaternion matrices" of the form:
a+bi
c+di
-c+di
a-bi
where a,b,c,d are integers with a² + b² + c² + d² = p . (We reduce the above matrix mod q to get a matrix in PSL2(q).) Also, in the Cayley graph we identify opposite pairs of directed edges to one non-directed edge.
Suppose p = a² mod q for some a. Show that Sp,q ⊂ PSL2(q).In fact, Sp,q is a set of generators of PSL2(q) , and the Cayley graph is non-bipartite.. Verify these facts for some p,q, or try to prove them in general.
The Ramanujan graph Xp,q is the Cayley graph of PSL2(q) with respect to the generators Sp,q. It is k-regular with k = p + 1 and any non-trivial eigenvalue μ of the adjacency matrix with |μ| ≤ 2√(k-1) = 2√p , which gives the largest possible spectral gap asymptotically for p fixed, q → ∞. Verify these facts for some p,q.
♠For the PSL2(q) case, girth(Xp,q) ≥ 2logpq . Thus the chromatic number of G = Xp,q satisfies:
χ(G) ≥ 1 + k / |max(μ)| > 1 + 2(p+1)/√p.
Thus if we let p → ∞ and q ≥ pN with N → ∞, we get graphs with arbitrarily large chromatic number and large girth. Use this to construct a graph with girth(G) ≥ 4 and χ(G) ≥ 4.
♠ Draw a picture of Xp,q for p = 3 , q = 5.I believe this is a 3-regular graph which might be planar.