Generalized binomial edge ideals

This paper studies a class of binomial ideals associated to graphs with finite vertex sets. They generalize the binomial edge ideals, and they arise in the study of conditional independence ideals. A Gröbner basis can be computed by studying paths in the graph. Since these Gröbner bases are square-free, generalized binomial edge ideals are radical. To find the primary decomposition a combinatorial problem involving the connected components of subgraphs has to be solved. The irreducible components of the solution variety are all rational.     

Some Cohen–Macaulay and Unmixed Binomial Edge Ideals

We study unmixed and Cohen-Macaulay properties of the binomial edge ideal of some classes of graphs. We compute the depth of the binomial edge ideal of a generalized block graph. We also characterize all generalized block graphs whose binomial edge ideals are Cohen–Macaulay and unmixed. So that we generalize the results of Ene, Herzog, and Hibi on block graphs. Moreover, we study unmixedness and Cohen–Macaulayness of the binomial edge ideal of some graph products such as the join and corona of two graphs with respect to the original graphs.     

Ideals and graphs,Gröbner bases and decision procedures in graphs

The well known correspondence between even cycles of an undirected graph and polynomials in a binomial ideal associated to a graph is extended to odd cycles and polynomials in another binomial ideal. Other binomial ideals associated to an undirected graph are also introduced. The results about them with topics on monomial ideals are used in order to show decision procedures for bipartite graphs, minimal vertex covers, cliques, edge covers and matchings with algebraic tools. All such procedures are implemented in Maple 9.5.     

Binomial Canonical Decompositions of Binomial Ideals

In this article, we prove that every binomial ideal in a polynomial ring over an algebraically closed field of characteristic zero admits a canonical primary decomposition into binomial ideals. Moreover, we prove that this special decomposition is obtained from a cellular decomposition which is also defined in a canonical way and does not depend on the field.     

Binomial arithmetical rank of lattice ideals

 In this paper, we will show that a lattice ideal is a complete intersection if and only if its binomial arithmetical rank equals its height, if the characteristic of the base field k is zero. And we will give the condition that a binomial ideal equals a lattice ideal up to radical in the case of char k=0. Further, we will study the upper bound of the binomial arithmetical rank of lattice ideals and give a sharp bound for the lattice ideals of codimension two. Received: 12 June 2001 / Revised version: 22 July 2002     

Extremal Betti Numbers of Some Cohen-Macaulay Binomial Edge Ideals

We provide the regularity and the Cohen-Macaulay type of binomial edge ideals of Cohen-Macaulay cones,and we show the extremal Betti numbers of some classes of Cohen-Macaulay binomial edge ideals:Cohen-Macaulay bipartite and fan graphs.In addition,we compute the Hilbert-Poincaré series of the binomial edge ideals of some Cohen-Macaulay bipartite graphs.     

Decompositions of binomial ideals

We present Binomials, a package for the computer algebra system Macaulay 2, which specializes well-known algorithms to binomial ideals. These come up frequently in algebraic statistics and commutative algebra, and it is shown that significant speedup of computations like primary decomposition is possible. While central parts of the implemented algorithms go back to a paper of Eisenbud and Sturmfels, we also discuss a new algorithm for computing the minimal primes of a binomial ideal. All decompositions make significant use of combinatorial structure found in binomial ideals, and to demonstrate the power of this approach we show how Binomials was used to compute primary decompositions of commuting birth and death ideals of Evans et al., yielding a counterexample for their conjectures.     

多项式组的特征分解

任一多项式理想的特征对是指由该理想的约化字典序Grobner基G和含于其中的极小三角列C构成的有序对(G,C).当C为正则列或正规列时,分别称特征对(G,C)为正则的或正规的.当G生成的理想与C的饱和理想相同时,称特征对(G,C)为强的.一组多项式的(强)正则或(强)正规特征分解是指将该多项式组分解为有限多个(强)正则或(强)正规特征对,使其满足特定的零点与理想关系.本文简要回顾各种三角分解及相应零点与理想分解的理论和方法,然后重点介绍(强)正则与(强)正规特征对和特征分解的性质,说明三角列、Ritt特征列和字典序Grobner基之间的内在关联,建立特征对的正则化定理以及正则、正规特征对的强化方法,进而给出两种基于字典序Grobner基计算、按伪整除关系分裂和构建、商除可除理想等策略的(强)正规与(强)正则特征分解算法.这两种算法计算所得的强正规与强正则特征对和特征分解都具有良好的性质,且能为输入多元多项式组的零点提供两种不同的表示.本文还给出示例和部分实验结果,用以说明特征分解方法及其实用性和有效性.     

Some algebraic aspects of mesoprimary decomposition

Recent results of Kahle and Miller give a method of constructing primary decompositions of binomial ideals by first constructing “mesoprimary decompositions” determined by their underlying monoid congruences. Monoid congruences (and therefore, binomial ideals) can present many subtle behaviors that must be carefully accounted for in order to produce general results, and this makes the theory complicated. In this paper, we examine their results in the presence of a positive A-grading, where certain pathologies are avoided and the theory becomes more accessible. Our approach is algebraic: while key notions for mesoprimary decomposition are developed first from a combinatorial point of view, here we state definitions and results in algebraic terms, which are moreover significantly simplified due to our (slightly) restricted setting. In the case of toral components (which are well-behaved with respect to the A-grading), we are able to obtain further simplifications under additional assumptions. We also provide counterexamples to two open questions, identifying (i) a binomial ideal whose hull is not binomial, answering a question of Eisenbud and Sturmfels, and (ii) a binomial ideal I for which $I_{\mathrm{toral}}$ is not binomial, answering a question of Dickenstein, Miller and the first author.     

Regularity,depth and arithmetic rank of bipartite edge ideals

We study minimal free resolutions of edge ideals of bipartite graphs. We associate a directed graph to a bipartite graph whose edge ideal is unmixed, and give expressions for the regularity and the depth of the edge ideal in terms of invariants of the directed graph. For some classes of unmixed edge ideals, we show that the arithmetic rank of the ideal equals projective dimension of its quotient.     

The edge intersection graphs of paths in a tree

The class of edge intersection graphs of a collection of paths in a tree (EPT graphs) is investigated, where two paths edge intersect if they share an edge. The cliques of an EPT graph are characterized and shown to have strong Helly number 4. From this it is demonstrated that the problem of finding a maximum clique of an EPT graph can be solved in polynomial time. It is shown that the strong perfect graph conjecture holds for EPT graphs. Further complexity results follow from the observation that every line graph is an EPT graph. The class of EPT graphs is equivalent to the class of fundamental cycle graphs.     

A Structure Theorem for Strong Immersions

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge‐disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree‐like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path‐like linear decomposition isolating the high degree vertices.     

图的{P4}-分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上.记Pl长度为l-1的路,如果G能够分解成若干个Pl,则称G存在{Pl}—分解.关于图的给定长路分解问题主要结果有:(i)连通图G存在{P3}—分解当且仅当G有偶数条边(见[1]);(ii)连通图G存在{P3,P4}—分解当且仅当G不是C3和奇树,这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树(见[3]).本文讨论了3正则图的{P4}—分解情况,并构造证明了边数为3k(k热∈Z且k≥2)的完全图Kn和完全二部图Kr,s存在{P4}—分解.     

Bidegreed graphs are edge reconstructible

An edge-deleted subgraph of a graph G is a subgraph obtained from G by the deletion of an edge. The Edge Reconstruction Conjecture asserts that every simple finite graph with four or more edges is determined uniquely, up to isomorphism, by its collection of edge-deleted subgraphs. A class of graphs is said to be edge reconstructible if there is no graph in the class with four or more edges that is not edge reconstructible. This paper proves that bidegreed graphs (graphs whose vertices all have one of two possible degrees) are edge reconstructible. The results are then generalized to show that all graphs that do not have three consecutive integers in their degree sequence are also edge reconstructible.     

Rings of Clean Index 4 and Applications

We discuss algebraic and homological properties of binomial edge ideals associated with the graphs which are obtained by gluing of subgraphs and the formation of cones.     

Coloring of lattices

The concept of coloring is studied for graphs derived from lattices with 0. It is shown that, if such a graph is derived from an atomic or distributive lattice, then the chromatic number equals the clique number. If this number is finite, then in the case of a distributive lattice, it is determined by the number of minimal prime ideals in the lattice. An estimate for the number of edges in such a graph of a finite lattice is given.     

A note on the critical ideals of a cycle

Critical ideals of a graph G which are the determinantal ideals of its generalized Laplacian matrix were first introduced by Corrales and Valencia as a generalization of the critical group. Then it was shown that critical ideals are also closely related to other properties of the graph, such as the clique number and the zero forcing number. In this note, we give a simple proof of Theorem 4.13 proved in [7], which gives a Gröbner basis of the first nontrivial critical ideal of a cycle. After that as applications we determine explicit expressions for the characteristic ideals of a cycle and the critical groups of a family of thick wheels.     

Point determination in graphs

A point determining graph is defined to be a graph in which distinct nonadjacent points have distinct neighborhoods. Those graphs which are critical with respect to this property are studied. We show that a graph is complete if and only if it is connected, point determining, but fails to remain point determining upon the removal of any edge. We also show that every connected, point determining graph contains at least two points, the removal of either of which will result again in a point determining graph. Graphs which are point determining and contain exactly two such points are shown to have the property that every point is adjacent to exactly one of these two points.