The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of f...The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of finding maximal independent sets of G to the problem of finding k-independent sets in G for. It is shown that the existence of k-independent sets in G is equivalent to the existence of solutions of a system of multivariate polynomial equations. It follows that the problem of finding k-independent sets can be realized by using Gröbner bases of polynomial ideals. Since the number of k-independent sets is finite, the triangular equations composed by Gröbner bases are easier to be solved. Consequently, the maximal independent sets and the independent number of G are obtained after solving at most n such equations. Finally, the numerical example is presented to illustrate the effectiveness of this algebraic computational method.展开更多
The process of substituting variables in a polynomial with other polynomials is dubbed polynomial composition.The behaviour of Gröbner bases and Sagbi bases under composition is well known.In this paper,the autho...The process of substituting variables in a polynomial with other polynomials is dubbed polynomial composition.The behaviour of Gröbner bases and Sagbi bases under composition is well known.In this paper,the authors provide a sufficient and necessary condition on a setΘof polynomials under which the Sagbi-Gröbner basis computation commutes with composition.This has natural applications to the computations of Sagbi-Gröbner bases for subsets of composed polynomials of subalgebra.展开更多
In this paper we consider Hibi rings and Rees rings attached to a poset. We classify the ideal lattices of posets whose Hibi relations are indispensable and the ideal lattices of posets whose Hibi relations form a qua...In this paper we consider Hibi rings and Rees rings attached to a poset. We classify the ideal lattices of posets whose Hibi relations are indispensable and the ideal lattices of posets whose Hibi relations form a quadratic Grobner basis with respect to the rank lexicographic order. Similar classifications are obtained for Rees rings of Hibi ideals.展开更多
In this paper, an algorithm for computing the Janet bases of linear differential equations is described, which is the differential analogue of the algorithm JanetBasis improved by Gerdt. An implementation of the algor...In this paper, an algorithm for computing the Janet bases of linear differential equations is described, which is the differential analogue of the algorithm JanetBasis improved by Gerdt. An implementation of the algorithm in Maple is given. The implemented algorithm includes some subalgorithms: Janet division, Pommaret division, the judgement of involutive divisor and reducible, the judgement of conventional divisor and reducible, involutive normal form and conventional normal form, involutive autoreduction and conventional autoreduction, PJ-autoreduction and so on. As an application, the Janet Bases of the determining system of classical Lie symmetries of some partial differential equations are obtained using our package.展开更多
文摘The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of finding maximal independent sets of G to the problem of finding k-independent sets in G for. It is shown that the existence of k-independent sets in G is equivalent to the existence of solutions of a system of multivariate polynomial equations. It follows that the problem of finding k-independent sets can be realized by using Gröbner bases of polynomial ideals. Since the number of k-independent sets is finite, the triangular equations composed by Gröbner bases are easier to be solved. Consequently, the maximal independent sets and the independent number of G are obtained after solving at most n such equations. Finally, the numerical example is presented to illustrate the effectiveness of this algebraic computational method.
文摘The process of substituting variables in a polynomial with other polynomials is dubbed polynomial composition.The behaviour of Gröbner bases and Sagbi bases under composition is well known.In this paper,the authors provide a sufficient and necessary condition on a setΘof polynomials under which the Sagbi-Gröbner basis computation commutes with composition.This has natural applications to the computations of Sagbi-Gröbner bases for subsets of composed polynomials of subalgebra.
文摘In this paper we consider Hibi rings and Rees rings attached to a poset. We classify the ideal lattices of posets whose Hibi relations are indispensable and the ideal lattices of posets whose Hibi relations form a quadratic Grobner basis with respect to the rank lexicographic order. Similar classifications are obtained for Rees rings of Hibi ideals.
文摘In this paper, an algorithm for computing the Janet bases of linear differential equations is described, which is the differential analogue of the algorithm JanetBasis improved by Gerdt. An implementation of the algorithm in Maple is given. The implemented algorithm includes some subalgorithms: Janet division, Pommaret division, the judgement of involutive divisor and reducible, the judgement of conventional divisor and reducible, involutive normal form and conventional normal form, involutive autoreduction and conventional autoreduction, PJ-autoreduction and so on. As an application, the Janet Bases of the determining system of classical Lie symmetries of some partial differential equations are obtained using our package.
