On complete intersection toric ideals of graphs

We study the graphs G for which their toric ideals I _G are complete intersections. In particular, we prove that for a connected graph G such that I _G is a complete intersection all of its blocks are bipartite except for at most two. We prove that toric ideals of graphs which are complete intersections are circuit ideals. In this case, the generators of the toric ideal correspond to even cycles of G except of at most one generator, which corresponds to two edge disjoint odd cycles joint at a vertex or with a path. We prove that the blocks of these graphs satisfy the odd cycle condition. Finally, we characterize all complete intersection toric ideals of graphs which are normal.     

Ring graphs and toric ideals

We study the family of simple graphs whose number of primitive cycles equals its cycle rank. Then we study toric ideals of simple and oriented graphs.     

On the universal Gröbner bases of toric ideals of graphs

The universal Gröbner basis of an ideal is a Gröbner basis with respect to all term orders simultaneously. We characterize in graph theoretical terms the elements of the universal Gröbner basis of the toric ideal of a graph. We also provide a new degree bound. Finally, we give examples of graphs for which the true degrees of their circuits are less than the degrees of some elements of the Graver basis.     

On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.     

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.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

The Krull-Schmidt Theorem in the Case Two

We study what happens if, in the Krull-Schmidt Theorem, instead of considering modules whose endomorphism rings have one maximal ideal, we consider modules whose endomorphism rings have two maximal ideals. If a ring has exactly two maximal right ideals, then the two maximal right ideals are necessarily two-sided. We call such a ring of type 2. The behavior of direct sums of finitely many modules whose endomorphism rings have type 2 is completely described by a graph whose connected components are either complete graphs or complete bipartite graphs. The vertices of the graphs are ideals in a suitable full subcategory of Mod-R. The edges are isomorphism classes of modules. The complete bipartite graphs give rise to a behavior described by a Weak Krull-Schmidt Theorem. Such a behavior had been previously studied for the classes of uniserial modules, biuniform modules, cyclically presented modules over a local ring, kernels of morphisms between indecomposable injective modules, and couniformly presented modules. All these modules have endomorphism rings that are either local or of type 2. Here we present a general theory that includes all these cases.     

Mixed ladder determinantal varieties from two-sided ladders

We study the family of ideals defined by mixed size minors of two-sided ladders of indeterminates. We compute their Gröbner bases with respect to a skew-diagonal monomial order, then we use them to compute the height of the ideals. We show that these ideals correspond to a family of irreducible projective varieties, that we call mixed ladder determinantal varieties. We show that these varieties are arithmetically Cohen-Macaulay, and we characterize the arithmetically Gorenstein ones. Our main result consists in proving that mixed ladder determinantal varieties belong to the same G-biliaison class of a linear variety.     

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.     

Deformations of Codimension 2 Toric Varieties

We prove Sturmfels' conjecture that toric varieties of codimension two have no other flat deformations than those obtained by Gröbner basis theory.     

Ideals of Graph Homomorphisms

In combinatorial commutative algebra and algebraic statistics many toric ideals are constructed from graphs. Keeping the categorical structure of graphs in mind we give previous results a more functorial context and generalize them by introducing the ideals of graph homomorphisms. For this new class of ideals we investigate how the topology of the graphs influences the algebraic properties. We describe explicit Gröbner bases for several classes, generalizing results by Hibi, Sturmfels, and Sullivant. One of our main tools is the toric fiber product, and we employ results by Engström, Kahle, and Sullivant. The lattice polytopes defined by our ideals include important classes in optimization theory, as the stable set polytopes.     

Gröbner bases of ideals cogenerated by Pfaffians

We characterise the class of one-cogenerated Pfaffian ideals whose natural generators form a Gröbner basis with respect to any anti-diagonal term order. We describe their initial ideals as well as the associated simplicial complexes, which turn out to be shellable and thus Cohen-Macaulay. We also provide a formula for computing their multiplicity.     

Normal toric ideals of low codimension

Every normal toric ideal of codimension two is minimally generated by a Gröbner basis with squarefree initial monomials. A polynomial time algorithm is presented for checking whether a toric ideal of fixed codimension is normal.     

Unmixed bipartite graphs and sublattices of the Boolean lattices

The correspondence between unmixed bipartite graphs and sublattices of the Boolean lattice is discussed. By using this correspondence, we show existence of squarefree quadratic initial ideals of toric ideals arising from minimal vertex covers of unmixed bipartite graphs.     

The Behaviors of Expansion Functor on Monomial Ideals and Toric Rings

In this article, we study some algebraic and combinatorial behaviors of expansion functor. We show that on monomial ideals some properties like polymatroidalness, weakly polymatroidalness, and having linear quotients are preserved under taking the expansion functor.

The main part of the article is devoted to study of toric ideals associated to the expansion of subsets of monomials which are minimal with respect to divisibility. It is shown that, for a given discrete polymatroid P, if toric ideal of P is generated by double swaps, then toric ideal of any expansion of P has such a property. This result, in a special case, says that White's conjecture is preserved under taking the expansion functor. Finally, the construction of Gröbner bases and some homological properties of toric ideals associated to expansions of subsets of monomials is investigated.     

Computing Gröbner fans

This paper presents algorithms for computing the Gröbner fan of an arbitrary polynomial ideal. The computation involves enumeration of all reduced Gröbner bases of the ideal. Our algorithms are based on a uniform definition of the Gröbner fan that applies to both homogeneous and non-homogeneous ideals and a proof that this object is a polyhedral complex. We show that the cells of a Gröbner fan can easily be oriented acyclically and with a unique sink, allowing their enumeration by the memory-less reverse search procedure. The significance of this follows from the fact that Gröbner fans are not always normal fans of polyhedra, in which case reverse search applies automatically. Computational results using our implementation of these algorithms in the software package Gfan are included.

     

On bipartite zero-divisor graphs

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.     

任意n个完备二分图的并图的k－优美性和算术性

证明了对于正整数k,n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是k-优美图;对于正整数k,d（d≥2）,k≠0（roodd）及n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是（k,d）-算术图,前一结论推广了文[6]的相应结果。     

Line graphs of complete multipartite graphs have small cycle double covers

It has been shown by MacGillivray and Seyffarth (Austral. J. Combin. 24 (2001) 91) that bridgeless line graphs of complete graphs, complete bipartite graphs, and planar graphs have small cycle double covers. In this paper, we extend the result for complete bipartite graphs, and show that the line graph of any complete multipartite graph (other than K_1,2) has a small cycle double cover.