The homology of the cyclic coloring complex of simple graphs

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:116

Article

Crown, Sarah

关键词: Coloring complex;    Chromatic polynomial;    Cyclic homology;    Acyclic orientation;   

DOI  :  10.1016/j.jcta.2008.10.001

来源: Elsevier

【 摘 要 】

Let G be a simple graph on n vertices, and let chi(G)(lambda) denote the chromatic polynomial of G. In this paper, we define the cyclic coloring complex, Delta(G), and determine the dimensions of its homology groups for simple graphs. In particular, we show that if G has r connected components, the dimension of (n - 3)rd homology group of Delta(G) is equal to (n - (r + 1)) plus 1/r!vertical bar chi(r)(G) (0)vertical bar, where chi(r)(G) is the rth derivative of chi(G)(lambda). We also define a complex Delta(G)(C), whose r-faces consist of all ordered set partitions [B(1), . . . , B(r+2)] where none of the B(i) contain an edge of G and where 1 is an element of B(1). We compute the dimensions of the homology groups of this complex, and as a result, obtain the dimensions of the multilinear parts of the cyclic homology groups of C[x(1) , . . . , xn]/{x(i)x(j) vertical bar ij is an edge of G}. We show that when G is a connected graph, the homology of Delta(G)(C) has nonzero homology only in dimension n - 2, and the dimension of this homology group is vertical bar chi'(G) (0)vertical bar. In this case, we provide a bijection between a set of homology representatives of Delta(G)(C) and the acyclic orientations of G with a unique source at v, a vertex of G. (C) 2008 Elsevier Inc. All rights reserved.

【 授权许可】

Free