Colorings of hypergraphs, perfect graphs, and associated primes of powers of monomial ideals (Q716459)

The focus of this article lies on the connection between coloring properties of a finite simple hypergraph and the (associated primes of) powers of the cover ideal of the hypergraph. In this context, the authors investigate several questions. First, they provide an algebraic method for the computation of the chromatic number \(\chi(\mathcal{H})\) of a hyergraph \(\mathcal{H}\) and more general of the \(b\)-chromatic number in terms of a membership problem for powers of the cover ideal \(J\). In case of the ordinary chromatic number, this method is equivalent to an algebraic description of \(\chi(\mathcal{H})\) in terms of secant ideals of the edge ideal, given by \textit{B. Sturmfels} and \textit{S. Sullivant} [Pure Appl. Math. Q. 2, No. 3, 867--891 (2006; Zbl 1107.14045)]. It is also indicated how the more general result might be used to gain further insight into the value of the fractional chromatic number of a hypergraph. Generalizing a result from [loc. cit.], the authors give a graph theoretic interpretation for the generators of the generalized Alexander dual \((J^s)^{[s]}\) of the \(s\)-th power of the cover ideal \(J\) of the hypergraph. More precisely, the generators are certain depolarizations of monomials, which correspond to induced subhypergraphs of the \(s\)-th expansion of \(\mathcal{H}\), whose chromatic number is at least \(s+1\). From this, a description of the associated primes of powers of the cover ideal \(J\) is derived, and primes that are associated to \(J^{d}\) but not to \(J^{e}\) for any \(1\leq e<d\) are shown to correspond to critically \((d+1)\)-chromatic induced subhypergraphs of \(\mathcal{H}\). With respect to the question at which place stability of the associated primes of \(J^s\) occurs, i.e., for which minimal integer \(a\) one has \(\bigcup_{s=1}^a\mathrm{Ass}(R/J^s)=\bigcup_{s=1}^\infty\mathrm{Ass}(R/J^s)\), the authors show that \(\chi(\mathcal{H})-1\) is a lower, though in general not optimal, bound for \(a\). Moreover, for perfect graphs, this bound turns out to be sharp. In the last part of the article, it is aimed at an algebraic characterization of perfect graphs not relying on the Strong Perfect Graph Theorem. Indeed, two such characterizations are provided, one in terms of the associated prime ideals of the powers \(J^s\) of the cover ideal for \(1\leq s< \chi(\mathcal{H})\) and one in terms of the saturated chain property for associated primes of \(J^s\). The first condition allows to check if a graph is perfect in just a finite number of steps. Finally, it is proven that, for a perfect graph \(G\), the associated primes persist, i.e., \(\mathrm{Ass}(R/J^s)\subseteq \mathrm{Ass}(R/J^{s+1})\) for \(s\geq 1\), and \(\chi(G)-1\) is shown to be the place at which stability of the associated primes occurs.