共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
Ignacio Ojeda 《代数通讯》2013,41(10):3722-3735
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. 相似文献
5.
Kazufumi Eto 《manuscripta mathematica》2002,109(4):455-463
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 相似文献
6.
7.
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. 相似文献
8.
9.
Thomas Kahle 《Annals of the Institute of Statistical Mathematics》2010,62(4):727-745
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. 相似文献
10.
任一多项式理想的特征对是指由该理想的约化字典序Grobner基G和含于其中的极小三角列C构成的有序对(G,C).当C为正则列或正规列时,分别称特征对(G,C)为正则的或正规的.当G生成的理想与C的饱和理想相同时,称特征对(G,C)为强的.一组多项式的(强)正则或(强)正规特征分解是指将该多项式组分解为有限多个(强)正则或(强)正规特征对,使其满足特定的零点与理想关系.本文简要回顾各种三角分解及相应零点与理想分解的理论和方法,然后重点介绍(强)正则与(强)正规特征对和特征分解的性质,说明三角列、Ritt特征列和字典序Grobner基之间的内在关联,建立特征对的正则化定理以及正则、正规特征对的强化方法,进而给出两种基于字典序Grobner基计算、按伪整除关系分裂和构建、商除可除理想等策略的(强)正规与(强)正则特征分解算法.这两种算法计算所得的强正规与强正则特征对和特征分解都具有良好的性质,且能为输入多元多项式组的零点提供两种不同的表示.本文还给出示例和部分实验结果,用以说明特征分解方法及其实用性和有效性. 相似文献
11.
Laura Felicia Matusevich Christopher ONeill 《Journal of Pure and Applied Algebra》2019,223(1):380-394
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 is not binomial, answering a question of Dickenstein, Miller and the first author. 相似文献
12.
Manoj Kummini 《Journal of Algebraic Combinatorics》2009,30(4):429-445
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. 相似文献
13.
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. 相似文献
14.
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. 相似文献
15.
一个图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}—分解. 相似文献
16.
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. 相似文献
17.
Tsiu-Kwen Lee 《代数通讯》2013,41(1):238-259
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. 相似文献
18.
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. 相似文献
19.
《Discrete Mathematics》2022,345(12):113107
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. 相似文献
20.
David P. Sumner 《Discrete Mathematics》1973,5(2):179-187
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. 相似文献