Establish a bijection between regions

Reference no: EM131085711

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

(a) Let G be a graph vertices {1, 2, . . . , n}. The Graphical arrangement A_G is the arrangement in Rⁿ consisting of the hyperplanes

x_i - x_j = 0, ij ∈ E(G).

Let P_G(t) be the chromatic polynomial of G, i.e. for any positive integer k, P_G(k) is the number of proper vertex colorings of G with k colors (feel free to ask me why P_G(t) is a polynomial if you don't already know why). Prove that

χA_G(t) = P_G(t).

(b) Establish a bijection between regions of A_G and acylic orientations of G, and conclude that the number of acyclic orientations of G is |P_G(-1)|.

Reference no: EM131085711

Questions Cloud

Compute asset current book value and tax payment : Equipment purchased for $100,000 five years ago was depreciated using SL over 10 years. (Assume no salvage value.) Assume the purchaser is profitable with an ordinary income tax rate of 33% and a longterm capital gains tax rate of 15%. Compute the as..

Problem on eulerian polynomial : The descent statistic is des(π) = |Des(π)|. The descent statistic is encoded in the Eulerian polynomial ∑π∈Sn tdes(π), and the most basic identity for Eulerian polynomials is ∑k≥0(k + 1)ntk = ∑π∈S_n tdes(π)/(1 - t)n+1

What do negative free cash flows to the firm imply : Consider the following in relation to the (DCF) model: What do positive free cash flows to the firm imply? What do negative free cash flows to the firm imply?

Four primary serviceoutputs of spatial convenience : Why are the four primary serviceoutputs of spatial convenience, lot size, waiting time, and product variety importantto logistics management? Provide examples of competing firms that differ in thelevel of each service output provided to customers.

Establish a bijection between regions : Establish a bijection between regions of AG and acylic orientations of G, and conclude that the number of acyclic orientations of G is |PG(-1)|

Define the matrix : 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)

Explain major provisions that state constitutions contain : Explain the major provisions that most state constitutions contain. In your own words, summarize the methods used for state constitutional change.

Problem regarding the impact compensation planning : There are many laws which impact compensation planning. Write a brief narrative in about 250 - 350 words which describes which federal law having the greatest effect on your organization's compensation plan?

Prove that there exists a dimensional polytope : Prove that {(f0, f3): there exists a 4 dimensional polytope P with f0 = f0(P), f3 = f3(P)} is precisely the set {(f0, f3) ∈ Z2: 5 ≤ f0 ≤ f3(f3 - 3)/2, 5 ≤ f3 ≤ f0(f0 - 3)/2}

User Account

All Pages