Let l be a finite lattice and let fx s be a c-valued

Question

Math 121c: Topics in Geometric Combinatorics, Spring 2012 Problems-

(a) Let L be a finite lattice and let f(x, s) be a C-valued function defined for all x, s ∈ L. Set F(x, s) = ∑_z≤x f(z, s). Show that

det[F(x ∧ y, x)]_x,y∈L = ∏_x∈L f(x, x),

and use this to show that

det[gcd(i, j)]_i,j=1ⁿ = k=1∏nφ(k).

Hint: Define the matrix M = M(x, y) whose entries are ζ(x, y)f(x, y). Investigate M and M^T.

(b) Let G be a graph. For any positive integer k, let χ(k) be the number of proper k-colorings of G (i.e. the number of functions c: V (G) → [k] such that c(u) ≠ c(v) for any uv ∈ E(G)). Let LG be the poset of all partitions π of V(G) such that the induced subgraph on every block of π is connected (with ordering by refinement).

Show that

χ(n) = ∑_{π∈L_G}µ(0ˆ, π)n^|π|.

where |π| is the number of blocks of π, and µ is the Mobius function of L_G.