Monomial bases for broken circuit complexes (Q1041597)

Given a finite graph \(G\) with a total ordering on its edge set one defines its broken circuit complex \(\Delta(G)\), a simplicial complex strongly related to the chromatic polynomial of the graph. The Stanley-Reisner ring of \(\Delta(G)\), denoted \(F(G)\) is Cohen-Macaulay and has a homogeneous system of parameters of degree one. \(F(G)\) modulo this homogeneous system of parameters is a finite dimensional vector space. In the present paper, the authors conjecture an explicit monomial basis for this finite dimensional vector space in terms of fundamental cocircuits of the graph. Their construction uses an ordering on the edges of \(G\) and a spanning tree of the graph, and provides a lower monomial ideal \(L(G)\) which is the conjectured basis. In case there is an ordering of the edges of \(G\) such that \(L(G)\) is indeed a basis of \(F(G)\) modulo the homogeneous system of parameters, \(G\) is said to have a \textit{no broken circuit} or \textit{NBC basis}. The authors give a general theorem about when a block has an NBC basis (Theorem 3.2) and describe two infinite families of graphs which do have NBC bases, namely (generalized) theta and phi graphs (Theorems 4.2 and 4.4). As an application, the authors give an upper bound for the number of acyclic orientations for graphs having an NBC basis. Finally, the paper presents some open problems an an approach to proving their main conjecture tahat every graph \(G\) has an NBC basis.