Search

This thesis deals with toric ideals associated with finite simple graphs. In particular we establish some results pertaining to the nature of the generators and syzygies of toric ideals associated with finite simple graphs. The first result dealt with in this thesis expands upon work by Favacchio, Hofscheier, Keiper, and Van Tuyl which states that for G, a graph obtained by "gluing" a graph H1 to a graph H2 along an induced subgraph, we can obtain the toric ideal associated to G from the toric ideals associated to H1 and H2 by taking their sum as ideals in the larger ring and saturating by a particular monomial f. Our contribution is to sharpen the result and show that instead of a saturation by f, we need only examine the colon ideal with f^2. The second result treated by this thesis pertains to graded Betti numbers of toric ideals of complete bipartite graphs. We show that by counting specific subgraphs one can explicitly compute a minimal set of generators for the corresponding toric ideals as well as minimal generating sets for the first two syzygy modules. Additionally we provide formulas for some of the graded Betti numbers. The final topic treated pertains to a relationship between the fundamental group the finite simple graph G and the associated toric ideal to G. It was shown by Villareal as well as Hibi and Ohsugi that the generators of a toric ideal associated to a finite simple graph correspond to the closed even walks of the graph G, thus linking algebraic properties to combinatorial ones. Therefore it is a natural question whether there is a relationship between the toric ideal associated to the graph G and the fundamental group of the graph G. We show, under the assumption that G is a bipartite graph with some additional assumptions, one can conceive of the set of binomials in the toric ideal with coprime terms, B(IG), as a group with an appropriately chosen operation ⋆ and establish a group isomorphism (B(IG), ⋆) ∼= π1(G)/H where H is a normal subgroup. We exploit this relationship further to obtain information about the generators of IG as well as bounds on the Betti numbers. We are also able to characterise all regular sequences and hence compute the depth of the toric ideal of G. We also use the framework to prove that IG = (⟨G⟩ : (e1 · · · em)^∞) where G is a set of binomials which correspond to a generating set of π1(G). Thesis Doctor of Philosophy (PhD)

We provide a new foundation for combinatorial commutative algebra and Stanley-Reisner theory using the partition complex introduced in [Adi18]. One of the main advantages is that it is entirely self-contained, using only a minimal knowledge of algebra and topology. On the other hand, we also develop new techniques and results using this approach. In particular, we provide - A novel, self-contained method of establishing Reisner's theorem and Schenzel's formula for Buchsbaum complexes. - A simple new way to establish Poincare duality for face rings of manifolds, in much greater generality and precision than previous treatments. - A "master-theorem" to generalize several previous results concerning the Lefschetz theorem on subdivisions. - Proof for a conjecture of Kuhnel concerning triangulated manifolds with boundary.

Freiman’s theorem gives a lower bound for the cardinality of the doubling of a finite set in $${\mathbb R}^n$$ . In this paper we give an interpretation of his theorem for monomial ideals and their fiber cones. We call a quasi-equigenerated monomial ideal a Freiman ideal, if the set of its exponent vectors achieves Freiman’s lower bound for its doubling. Algebraic characterizations of Freiman ideals are given, and finite simple graphs are classified whose edge ideals or matroidal ideals of its cycle matroids are Freiman ideals.

A numerical monoid is an additive submonoid of the non-negative integers. Given a numerical monoid $S$, consider the family of "shifted" monoids $M_n$ obtained by adding $n$ to each generator of $S$. In this paper, we examine minimal relations among the generators of $M_n$ when $n$ is sufficiently large, culminating in a description that is periodic in the shift parameter $n$. We explore several applications to computation, combinatorial commutative algebra, and factorization theory., 15 pages, 2 figures

The study of the h-vectors of graded Gorenstein algebras is an important topic in combinatorial commutative algebra, which despite the large amount of literature produced during the last several ye...

Since the early 1990s, a classical object in commutative algebra has been the study of binomial ideals. A widely-investigated class of binomial ideals is the one containing those generated by a subset of 2-minors of an (m x n)-matrix of indeterminates. This thesis is devoted to illustrate some algebraic and homological properties of two classes of ideals of 2-minors: binomial edge ideals and polyomino ideals. Binomial edge ideals arise from finite graphs and their appeal results from the fact that their homological properties reflect nicely the combinatorics of the underlying graph. First, we focus on the binomial edge ideals of block graphs. We give a lower bound for their Castelnuovo-Mumford regularity by computing the two distinguished extremal Betti numbers of a new family of block graphs, called flower graphs. Moreover, we present a linear time algorithm to compute Castelnuovo-Mumford regularity and Krull dimension of binomial edge ideals of block graphs. Secondly, we consider some classes of 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 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. Polyomino ideals arise from polyominoes, plane figures formed by joining one or more equal squares edge to edge. It is known that the polyomino ideal of simple polyominoes is prime. We consider multiply connected polyominoes, namely polyominoes with holes, and observe that the non-existence of a certain sequence of inner intervals of the polyomino, called zig-zag walk, gives a necessary condition for the primality of the polyomino ideal. Moreover, by computational approach, we prove that for all polyominoes with rank less than or equal to 14 the above condition is also sufficient. Lastly, we present an infinite class of prime polyomino ideals.

The goal of this short note is to study the secant varieties of the triple Segre product of type (1,a,b) by means of the standard tools of combinatorial commutative algebra. We reprove and extend to arbitrary characteristic results of Landsberg and Weyman regarding the defining ideal and the Cohen-Macaulay property of the secant varieties. Furthermore for these varieties we compute the degree and give a bound for their Castelnuovo-Mumford regularity which is sharp in many cases., Typos corrected. After the paper was published we came to know that our results have some overlap with the paper "Gr\"obner bases and the Cohen-Macaulay property of Li's double determinantal varieties" by Fieldsteel, Nathan; Klein, Patricia arXiv:1906.06817 published in Proc. Amer. Math. Soc. Ser. B 7 (2020), 142--158

Esta tesis pretende explorar el nexo de unión que existe entre la estructura algebraica de un código lineal y el proceso de descodificación completa. Sabemos que el proceso de descodificación completa para códigos lineales arbitrarios es NP-completo, incluso si se admite preprocesamiento de los datos. Nuestro objetivo es realizar un análisis algebraico del proceso de la descodificación, para ello asociamos diferentes estructuras matemáticas a ciertas familias de códigos. Desde el punto de vista computacional, nuestra descripción no proporciona un algoritmo eficiente pues nos enfrentamos a un problema de naturaleza NP. Sin embargo, proponemos algoritmos alternativos y nuevas técnicas que permiten relajar las condiciones del problema reduciendo los recursos de espacio y tiempo necesarios para manejar dicha estructura algebraica., Departamento de Algebra, Geometría y Topología

A graph $G$ is said to be chordal if it has no induced cycles of length four or more. In a recent preprint Culbertson, Guralnik, and Stiller give a new characterization of chordal graphs in terms of sequences of what they call `edge-erasures'. We show that these moves are in fact equivalent to a linear quotient ordering on $I_{\overline{G}}$, the edge ideal of the complement graph. Known results imply that $I_{\overline G}$ has linear quotients if and only if $G$ is chordal, and hence this recovers an algebraic proof of their characterization. We investigate higher-dimensional analogues of this result, and show that in fact linear quotients for more general circuit ideals of $d$-clutters can be characterized in terms of removing exposed circuits in the complement clutter. Restricting to properly exposed circuits can be characterized by a homological condition. This leads to a notion of higher dimensional chordal clutters which borrows from commutative algebra and simple homotopy theory. The interpretation of linear quotients in terms of shellability of simplicial complexes also has applications to a conjecture of Simon regarding the extendable shellability of $k$-skeleta of simplices. Other connections to combinatorial commutative algebra, chordal complexes, and hierarchical clustering algorithms are explored., 18 pages, 6 figures; V2: improved organization and corrected typos, added discussion regarding Simon's conjecture; V3: more corrections and revisions, incorporating suggestions from referees

We study multiple simultaneous cut events for k-out-of-n:F and linear consecutive k-out-of-n:F systems in which each component has a constant failure probability. We list the multicuts of these systems and describe the structural differences between them. Our approach, based on combinatorial commutative algebra, allows complete enumeration of the sets of multicuts for both kinds of systems. We also analyze the computational issues of multicut enumeration and reliability computations., Comment: To appear in Pattern Recognition Letters

In this chapter we will discuss a profound connection between commutative rings and some combinatorial properties of simplicial complexes. The deepest and most interesting results in this area require a background in algebraic topology and homological algebra beyond the scope of this book.

The bigraded Betti numbers β−i,2j(P) of a simple polytope P are the dimensions of the bigraded components of the Tor groups of the face ring k[P]. The numbers β−i,2j(P) reflect the combinatorial structure of P, as well as the topological structure of the corresponding moment-angle manifold ZP; thus, they find numerous applications in combinatorial commutative algebra and toric topology. We calculate certain bigraded Betti numbers of the type β−i,2(i+1) for associahedra and apply the calculation of bigraded Betti numbers for truncation polytopes to study the topology of their moment-angle manifolds. Presumably, for these two series of simple polytopes, the numbers β−i,2j(P) attain their minimum and maximum values among all simple polytopes P of fixed dimension with a given number of facets.

Ehrenborg, Govindaiah, Park, and Readdy recently introduced the van der Waerden complex, a pure simplicial complex whose facets correspond to arithmetic progressions. Using techniques from combinatorial commutative algebra, we classify when these pure simplicial complexes are vertex decomposable or not Cohen-Macaulay. As a corollary, we classify the van der Waerden complexes that are shellable., Comment: 7 pages

We continue the program started in Manon (2010) [M1] to understand the combinatorial commutative algebra of the projective coordinate rings of the moduli stack M C , p → ( SL 2 ( C ) ) of quasi-parabolic SL 2 ( C ) principal bundles on a generic marked projective curve. We find general bounds on the degrees of polynomials needed to present these algebras by studying their toric degenerations. In particular, we show that the square of any effective line bundle on this moduli stack yields a Koszul projective coordinate ring. This leads us to formalize the properties of the polytopes used in proving our results by constructing a category of polytopes with term orders. We show that many of results on the projective coordinate rings of M C , p → ( SL 2 ( C ) ) follow from closure properties of this category with respect to fiber products.

The Riemann–Roch theorem on a graph G is related to Alexander duality in combinatorial commutative algebra. We study the lattice ideal given by chip firing on G and the initial ideal whose standard monomials are the G-parking functions. When G is a saturated graph, these ideals are generic and the Scarf complex is a minimal free resolution. Otherwise, syzygies are obtained by degeneration. We also develop a self-contained Riemann–Roch theory for Artinian monomial ideals.

A model for statistical ranking is a family of probability distributions whose states are orderings of a fixed finite set of items. We represent the orderings as maximal chains in a graded poset. The most widely used ranking models are parameterized by rational function in the model parameters, so they define algebraic varieties. We study these varieties from the perspective of combinatorial commutative algebra. One of our models, the Plackett-Luce model, is non-toric. Five others are toric: the Birkhoff model, the ascending model, the Csiszar model, the inversion model, and the Bradley-Terry model. For these models we examine the toric algebra, its lattice polytope, and its Markov basis., 25 pages

There are two seemingly unrelated ideals associated with a simplicial complex \Delta. One is the Stanley-Reisner ideal I_\Delta, the monomial ideal generated by minimal non-faces of \Delta, well-known in combinatorial commutative algebra. The other is the toric ideal I_{M(\Delta)} of the facet subring of \Delta, whose generators give a Markov basis for the hierarchical model defined by \Delta, playing a prominent role in algebraic statistics. In this note we show that the complexity of the generators of I_{M(\Delta)} is determined by the Betti numbers of I_\Delta. The unexpected connection between the syzygies of the Stanley-Reisner ideal and degrees of minimal generators of the toric ideal provide a framework for further exploration of the connection between the model and its many relatives in algebra and combinatorics., Comment: Section 6 outlines few open problems. (Final version, differs slightly then publication.) Version3 was a major revision: proved Conjecture from previous version for all simplicial complexes

We characterize the monomial complete intersections in three variables satisfying the Weak Lefschetz Property (WLP), as a function of the characteristic of the base field. Our result presents a surprising, and still combinatorially obscure, connection with the enumeration of plane partitions. It turns out that the rational primes p dividing the number, M(a,b,c), of plane partitions contained inside an arbitrary box of given sides a,b,c are precisely those for which a suitable monomial complete intersection (explicitly constructed as a bijective function of a,b,c) fails to have the WLP in characteristic p. We wonder how powerful can be this connection between combinatorial commutative algebra and partition theory. We present a first result in this direction, by deducing, using our algebraic techniques for the WLP, some explicit information on the rational primes dividing M(a,b,c)., 16 pages. Minor revisions, mainly to keep track of two interesting developments following the original posting. Final version to appear in Discrete Math

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. These mesoprimary decompositions are highly combinatorial in nature, and are designed to parallel standard primary decomposition over Noetherean rings. In this paper, we generalize mesoprimary decomposition from binomial ideals to "binomial submodules" of certain graded modules over the corresponding monoid algebra, analogous to the way primary decomposition of ideals over a Noetherean ring $R$ generalizes to $R$-modules. The result is a combinatorial method of constructing primary decompositions that, when restricting to the special case of binomial ideals, coincides with the method introduced by Kahle and Miller.

In this article we prove that every toric ideal associated with a gap-free graph $G$ has a squarefree lexicographic initial ideal. Moreover, in the particular case when the complementary graph of $G$ is chordal (i.e. when the edge ideal of $G$ has a linear resolution), we show that there exists a reduced Gr\"obner basis $\mathcal{G}$ of the toric ideal of $G$ such that all the monomials in the support of $\mathcal{G}$ are squarefree. Finally, we show (using work by Herzog and Hibi) that if $I$ is a monomial ideal generated in degree 2, then $I$ has a linear resolution if and only if all powers of $I$ have linear quotients, thus extending a result by Herzog, Hibi and Zheng., Comment: 13 pages, v2. To appear in Journal of Pure and Applied Algebra

We survey the Stanley–Reisner correspondence in combinatorial commutative algebra, describing fundamental applications involving Alexander duality, associated primes, f- and h-vectors, and Betti numbers of monomial ideals.

A Gorenstein polytope of index r is a lattice polytope whose r-th dilate is a reflexive polytope. These objects are of interest in combinatorial commutative algebra and enumerative combinatorics, and play a crucial role in Batyrev's and Borisov's computation of Hodge numbers of mirror-symmetric generic Calabi-Yau complete intersections. In this paper, we report on what is known about smooth Gorenstein polytopes, i.e., Gorenstein polytopes whose normal fan is unimodular. We classify d-dimensional smooth Gorenstein polytopes with index larger than (d+3)/3. Moreover, we use a modification of Oebro's algorithm to achieve classification results for smooth Gorenstein polytopes in low dimensions. The first application of these results is a database of all toric Fano d-folds whose anticanonical divisor is divisible by an integer r larger than d-8. As a second application we verify that there are only finitely many families of Calabi-Yau complete intersections of fixed dimension that are associated to a smooth Gorenstein polytope via the Batyrev-Borisov construction., Comment: 18 pages

At the MONICA conference “MONomial Ideals, Computations and Applications” at the CIEM, Castro Urdiales (Cantabria, Spain) in July 2011, I gave three lectures covering different topics of Combinatorial Commutative Algebra: (1) A survey on Stanley decompositions. (2) Generalized Hibi rings and Hibi ideals. (3) Ideals generated by two-minors with applications to Algebraic Statistics. In this article I will restrict myself to give an extended presentation of the first lecture. The CoCoA tutorials following this survey will deal also with topics related to the other two lectures. Complementing the tutorials, the reader finds in [165] a CoCoA routine to compute the Stanley depth for modules of the form I ∕ J, where J ⊂ I are monomial ideals.

The set of f-vectors of pure simplicial complexes is an important but little understood object in combinatorics and combinatorial commutative algebra. Unfortunately, its explicit characterization appears to be a virtually intractable problem, and its structure very irregular and complicated. The purpose of this note, where we combine a few different algebraic and combinatorial techniques, is to lend some further evidence to this fact. We first show that pure (in fact, Cohen-Macaulay) f-vectors can be nonunimodal with arbitrarily many peaks, thus improving the corresponding results known for level Hilbert functions and pure O-sequences. We provide both an algebraic and a combinatorial argument for this result. Then, answering negatively a question of the second author and collaborators posed in the recent AMS Memoir on pure O-sequences, we show that the Interval Property fails for the set of pure f-vectors, even in dimension 2., A few minor changes. To appear in the Proc. of the AMS

We study equivariant resolutions and local cohomologies of toric sheaves for affine toric varieties, where our focus is on the construction of new examples of decomposable maximal Cohen-Macaulay modules of higher rank. A result of Klyachko states that the category of reflexive toric sheaves is equivalent to the category of vector spaces together with a certain family of filtrations. Within this setting, we develop machinery which facilitates the construction of minimal free resolutions for the smooth case as well as resolutions which are acyclic with respect to local cohomology functors for the general case. We give two main applications. First, over the polynomial ring, we determine in explicit combinatorial terms the Z^n-graded Betti numbers and local cohomology of reflexive modules whose associated filtrations form a hyperplane arrangement. Second, for the non-smooth, simplicial case in dimension d >= 3, we construct new examples of indecomposable maximal Cohen-Macaulay modules of rank d - 1., 39 pages, requires packages ams*, enumerate

We consider the problem of computing the Euler characteristic of an abstract simplicial complex given by its vertices and facets. We show that this problem is #P-complete and present two new practical algorithms for computing Euler characteristic. The two new algorithms are derived using combinatorial commutative algebra and we also give a second description of them that requires no algebra. We present experiments showing that the two new algorithms can be implemented to be faster than previous Euler characteristic implementations by a large margin., Comment: 28 pages

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 influence the algebraic properties. We describe explicit Grobner 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 Engstrom, Kahle and Sullivant. The lattice polytopes defined by our ideals include important classes in optimization theory, as the stable set polytopes., 34 pages, 12 figures. To appear in Annals of Combinatorics. Fixed some typos

A simplicial polytope is combinatorially rigid if its combinatorial structure is determined by its graded Betti numbers which are important invariant coming from combinatorial commutative algebra. We find a necessary condition to be combinatorially rigid for 3-dimensional reducible simplicial polytopes and provide some rigid reducible simplicial polytopes., 13 pages, 4 figures

In this note we consider monoidal complexes and their associated algebras, called toric face rings. These rings generalize Stanley-Reisner rings and affine monoid algebras. We compute initial ideals of the presentation ideal of a toric face ring, and determine its graded Betti numbers. Our results generalize celebrated theorems of Hochster in combinatorial commutative algebra., Comment: 18 pages

A simple convex polytope $P$ is \emph{cohomologically rigid} if its combinatorial structure is determined by the cohomology ring of a quasitoric manifold over $P$. Not every $P$ has this property, but some important polytopes such as simplices or cubes are known to be cohomologically rigid. In this article we investigate the cohomological rigidity of polytopes and establish it for several new classes of polytopes including products of simplices. Cohomological rigidity of $P$ is related to the \emph{bigraded Betti numbers} of its \emph{Stanley--Reisner ring}, another important invariants coming from combinatorial commutative algebra., Comment: 18 pages, 1 figure, 2 tables; revised version

A tetrahedral curve is a (usually nonreduced) curve in P^3 defined by an unmixed, height two ideal generated by monomials. We characterize when these curves are arithmetically Cohen-Macaulay by associating a graph to each curve and, using results from combinatorial commutative algebra and Alexander duality, relating the structure of the complementary graph to the Cohen-Macaulay property., 15 pages; minor revisions to v. 1 to improve clarity; to appear in JPAA