Algebraic Combinatorics (course notes Fall 2008) by Geir T. Helleloid

By Geir T. Helleloid

Show description

Read or Download Algebraic Combinatorics (course notes Fall 2008) PDF

Best combinatorics books

Handbook of Algebra Vol III

1998 . .. a good index is incorporated on the way to aid a mathematician operating in a space except his personal to discover enough info at the subject in query.

Extra info for Algebraic Combinatorics (course notes Fall 2008)

Example text

Otherwise, if D is an oriented tree with root vi , then Li (D) is (conjugate to) an upper triangular matrix with 1’s on the diagonal and has determinant 1. If D has m > n − 1 arcs, we may assume that vi has no outgoing arcs (these are not contained in any spanning tree with root v and do not affect det(Li (D)). Then some vertex vj = vi has outdegree at least two; choose one outgoing arc e. Let D1 be D with e removed and let D2 be D with other outgoing arcs from vj removed. By induction, det(Li (D1 )) and det(Li (D2 )) equal the number of oriented spanning trees rooted at vi in the respective graphs.

Vn }. Then t(D, vi ) = det(Li (D)). Before proving this theorem, we show that the Matrix Tree Theorem is a corollary. 7. Given a general graph G, form a digraph D by replacing each edge vi vj in G by arcs (vi , vj ) and (vj , vi ). Then L(G) = L(D). Furthermore there is a bijection between spanning trees of G and oriented spanning trees of D with root vi (given a spanning tree of G, orient all edges toward vi to obtain an oriented spanning tree of D with root vi , and given an oriented spanning tree of G with root vi , unorient the edges to obtain a spanning tree of G).

Vm and v2 , . . , vl form a smaller minimal counterexample. This is a contradiction. There is an addition operation on chip configurations. If σ1 , σ2 : V (G) → Nn are chip configurations, then σ1 + σ2 is the chip configuration for which (σ1 + σ2 )(v) = σ1 (v) + σ2 (v); that is, you just combine the two piles of chips at each vertex. Now, generalize to chip configurations that allow negative numbers of chips at vertices, that is, maps σ : V (G) → Zn and allow any vertex to fire. Generalized chip configurations form a group under + naturally isomorphic to Zn .

Download PDF sample

Rated 4.24 of 5 – based on 19 votes