A Gröbner basis characterization for chordal comparability graphs

In this paper, we study toric ideals associated with multichains of posets. It is shown that the comparability graph of a poset is chordal if and only if there exists a quadratic Gröbner basis of the toric ideal of the poset. Strong perfect elimination orderings of strongly chordal graphs play an important role.     

Gröbner–Shirshov basis for the Braid group in the Birman–Ko–Lee generators

In this paper, we obtain Gröbner–Shirshov (non-commutative Gröbner) bases for braid groups in the Birman–Ko–Lee generators enriched by “Garside word” δ [J. Birman, K.H. Ko, S.J. Lee, A new approach to the word and conjugacy problems for the braid groups, Adv. Math. 139 (1998) 322–353]. It gives a new algorithm for getting the Birman–Ko–Lee normal forms in braid groups, and thus a new algorithm for solving the word problem in these groups.     

Gröbner–Shirshov Bases for Schreier Extensions of Groups

In this article, by using the Gröbner–Shirshov bases, we give characterizations of the Schreier extensions of groups when the group is presented by generators and relations. An algorithm to find the conditions of a group to be a Schreier extension is obtained. By introducing a special total order, we obtain the structure of the Schreier extension by an HNN group.     

Gröbner–Shirshov bases for brace algebras

Let A be a brace algebra. This structure implies that A is also a pre-Lie algebra. In this paper, we establish Composition-Diamond lemma for brace algebras. For each pre-Lie algebra L, we find a Gröbner–Shirshov basis for its universal brace algebra U_b(L). As applications, we determine an explicit linear basis for U_b(L) and prove that L is a pre-Lie subalgebra of U_b(L).     

Gröbner–Shirshov bases for pre-associative algebras

We develop Gröbner–Shirshov bases technique for pre-associative (dendriform) algebras and prove a version of composition-diamond lemma.     

Gröbner–Shirshov Basis for HNN Extensions of Groups and for the Alternating Group

In this article, we generalize the Shirshov's Composition Lemma by replacing the monomial order for others. By using Gröbner–Shirshov bases, the normal forms of HNN extension of a group and the alternating group are obtained.     

Gröbner–Shirshov bases for some Lie algebras

Siberian Mathematical Journal - We give Gröbner–Shirshov bases for the Drinfeld–Kohno Lie algebra L n in [1] and the Kukin Lie algebra A P in [2], where P is a semigroup. By way of...     

Gröbner Bases for Ideals of σ-PBW Extensions

In this article, we introduce the σ-PWB extensions and construct the theory of Gröbner bases for the left ideals of them. We prove the Hilbert's basis theorem and the division algorithm for this more general class of Poincaré–Birkhoff–Witt extensions. For the particular case of bijective and quasi-commutative σ-PWB extensions, we implement the Buchberger's algorithm for computing Gröbner bases of left ideals.     

Hilbert Series of Group Representations and Gröbner Bases for Generic Modules

Each matrix representation :G GL_n() of a finite Group G over a field induces an action of G on the module ⁿ over the polynomial algebra The graded -submodule M() of _n generated by the orbit of is studied. A decomposition of M() into generic modules is given. Relations between the numerical invariants of and those of M(), the latter being efficiently computable by Gröbner bases methods, are examined. It is shown that if is multiplicity-free, then the dimensions of the irreducible constituents of can be read off from the Hilbert series of M(Pi;). It is proved that determinantal relations form Gröbner bases for the syzygies on generic matrices with respect to any lexicographic order. Gröbner bases for generic modules are also constructed, and their Hilbert series are derived. Consequently, the Hilbert series of M(Pi;) is obtained for an arbitrary representation.     

Gröbner bases and triangulations of the second hypersimplex

The algebraic technique of Gröbner bases is applied to study triangulations of the second hypersimplex (2,n). We present a quadratic Gröbner basis for the associated toric idealK(K _n ). The simplices in the resulting triangulation of (2,n) have unit volume, and they are indexed by subgraphs which are linear thrackles [28] with respect to a circular embedding ofK _n . Forn6 the number of distinct initial ideals ofI(K _n ) exceeds the number of regular triangulations of (2,n); more precisely, the secondary polytope of (2,n) equals the state polytope ofI(K _n ) forn5 but not forn6. We also construct a non-regular triangulation of (2,n) forn9. We determine an explicit universal Gröbner basis ofI(K _n ) forn8. Potential applications in combinatorial optimization and random generation of graphs are indicated.Research partially supported by a doctoral fellowship of the National University of Mexico, the National Science Foundation, the David and Lucile Packard Foundation and the U.S. Army Research Office (through ACSyAM/MSI, Cornell).     

Gröbner–Shirshov bases for Vinberg–Koszul–Gerstenhaber right-symmetric algebras

In this paper, we establish the composition-diamond lemma for right-symmetric algebras. As an application, we give a Gröbner–Shirshov basis for the universal enveloping right-symmetric algebra of a Lie algebra.     

Gröbner Bases for Complete Uniform Families

We describe (reduced) Gröbner bases of the ideal of polynomials over a field, which vanish on the set of characterisic vectors of the complete unifom families . An interesting feature of the results is that they are largely independent of the monomial order selected. The bases depend only on the ordering of the variables. We can thus use past results related to the lex order in the presence of degree-compatible orders, such as deglex. As applications, we give simple proofs of some known results on incidence matrices.     

Gröbner bases in Asymptotic Analysis of Perturbed Polynomial Programs

We consider a perturbed mathematical programming problem where both the objective and the constraint functions are polynomial in all underlying decision variables and in the perturbation parameter $\varepsilon.We consider a perturbed mathematical programming problem where both the objective and the constraint functions are polynomial in all underlying decision variables and in the perturbation parameter We study the behaviour of the solutions of such a perturbed problem as Though the solutions of the programming problems are real, we consider the Karush–Kuhn–Tucker optimality system as a one-dimensional complex algebraic variety in a multi-dimensional complex space. We use the Buchberger’s elimination algorithm of the Gr?bner bases theory to replace the defining equations of the variety by its Gr?bner basis, that has the property that one of its elements is bivariate, that is, a polynomial in and one of the decision variables only. Changing the elimination order in the Buchberger’s algorithm, we obtain such a bivariate polynomial for each of the decision variables. Thus, the solutions of the original system reduces to a number of algebraic functions in that can be represented as a Puiseux series in a neighbourhood of . A detailed analysis of the branching order and the order of the pole is also provided. The latter is estimated via characteristics of these bivariate polynomials of Gr?bner bases.This research was supported by a grant from the Australian Research Council no. DP0343028. We are indebted to K. Avrachenkov, P. Howlett, and V. Gaitsgory for many helpful discussions.     

Gröbner–Shirshov Basis of Quantum Group of Type G 2

By using the generating sequence and relations given by Ringel for his Ringel–Hall algebra in [8 Ringel , C. M. ( 1996 ). PBW-bases of quantum groups . J. Reine Angew. Math. 470 : 51 – 88 .[Web of Science ®] , [Google Scholar]], we give a Gröbner–Shirshov basis for quantum group of type G ₂.