Monomial invariants applied to graph coloring (Q6116562)

The flow of this paper is a threefold process that aims at computing graph invariants using monomial invariants. Although the ultimate goal is to put the theory of monomial ideals to the service of graph coloring, each step of the process has its own goal and contains some results interesting in itself. In the first stage, the author reinterprets two monomial invariants in the language of monomial ideals. Since monomial ideals are members of the larger class of modules over a polynomial ring, definitions, and theorems about such modules automatically become definitions and theorems about monomial ideals. In particular, the concepts of monomial codimension and monomial multiplicity can be (and have often been) defined with the same terminology as the codimension and multiplicity of a module. However, in this article, the author redefines these concepts in terms inherent to monomial ideals. More specifically, they define the codimension of a monomial ideal \(M\) as the cardinality of the smallest set of variables \(X\), such that every generator of \(M\) is divisible by some variable of \(X\). The set \(X\) is called a realization of the codimension of \(M\). In Theorem 3.5, it is then shown that for a large class of monomial ideals, the multiplicity of an ideal equals the number of realizations of the codimension of its polarization. The second part is constructive and pivotal. Given a graph \(G\), a monomial ideal \(M_{G}\) is constructed, called the chromatic ideal of \(G\). The name chromatic ideal responds to the fact that the chromatic number of \(G\) equals the codimension of \(M_{G}\). This can be seen in Theorem 4.8. This chromatic ideal \(M_{G}\) can be regarded as the algebraic counterpart of the graph \(G\), as invariants of one can often be represented in terms of invariants of the other, and each structure can be obtained from the other. See Proposition 4.3 for corresponding details. The idea of associating a monomial ideal to a graph has already been used in the past. The term edge ideal, for instance, clearly speaks of an ideal defined in terms of the edges of a graph. Edge ideals, cover ideals and other ideals constructed with an eye on graphs usually have the following common characteristic: the vertices of the graph determine the variables of the ideal, and the edges of the graph determine (either directly or indirectly) the minimal generators of the ideal. Chromatic ideals, however, reverse this principle. The vertices of \(G\) define the minimal generators of \(M_{G}\), and the edges of \(G\) determine the variables of \(M_{G}\). See Definition 4.1. This distinctive feature makes chromatic ideals a useful bridge between commutative algebra and graph theory. In the third and last part of the process, the author transforms information about monomial ideals into information about graphs. Some graph invariants are expressed in terms of monomial invariants. The main result is given in Theorem 5.1, where it is shown how the chromatic polynomial of \(G\), evaluated at the chromatic number of \(G\), can be computed using the codimension and multiplicity of \(M_{G}\), for a class of graphs. The main idea used to prove this theorem is the fact that the number of configurations of \(k\)-colorings of \(G\) (where \(k\) is the chromatic number of \(G\)) is equal to the number of realizations of the codimension of \(M_{G}\). In particular, this theorem applies to all graphs satisfying the Erdős-Faber-Lovàsz conjecture, something that is discussed at the end of the paper. Section 3 discusses the meanings of codimension and multiplicity in the context of monomial ideals. In Section 4, the author introduces chromatic ideals, computes some of their invariants, and proves their basic properties. Section 5 demonstrates the interaction between chromatic polynomial, chromatic number, codimension, and multiplicity. Section 6 deals with the Erdős-Faber-Lovàsz conjecture. The paper is extremely well-written and organized. It contains many examples and references while stating enough motivation to explain the approach taken by the author. Well worth the read!