In this thesis, we study Hilbert functions of monomial ideals in the polynomial ring and the Kruskal-Katona ring. In particular, we classify Gotzmann edge ideals and, more generally, Gotzmann squarefree monomial ideals. In addition, we discuss Betti numbers of Gotzmann ideals and measure how far certain edge ideals are from Gotzmann. This thesis also contains a thorough account the combinatorial relationship between lex segments and Macaulay representations of their dimensions and codimensions.

Placement games are a subclass of combinatorial games which are played on graphs. In this thesis, we demonstrate that placement games could be considered as games played on simplicial complexes. These complexes are constructed using square-free monomials. We define new classes of placement games and the notion of Doppelgänger. To aid in exploring the simplicial complex of a game, we introduce the bipartite flip and develop tools to compare known bounds on simplicial complexes (such as the Kruskal-Katona bounds) with bounds on game complexes.

In this thesis, we undertake a combinatorial study of certain aspects of triangulations of cartesian products of simplices, particularly in relation to their relevance in toric algebra and to their underlying product structure. The first chapter reports joint work with Samu Potka. The object of study is a class of homogeneous toric ideals called cut ideals of graphs, that were introduced by Sturmfels and Sullivant 2006. Apart from their inherent appeal to combinatorial commutative algebra, these ideals also generalize graph statistical models for binary data and are related to some statistical models for phylogenetic trees. Specifically, we consider minimal free resolutions for the cut ideals of trees. We propose a method to combinatorially estimate the Betti numbers of the ideals in this class. Using this method, we derive upper bounds for some of the Betti numbers, given by formulas exponential in the number of vertices of the tree. Our method is based on a common technique in commutative algebra whereby arbitrary homogeneous ideals are deformed to initial monomial ideals, which are easier to analyze while conserving some of the information of the original ideals. The cut ideal of a tree on n vertices turns out to be isomorphic to the Segre product of the cut ideals of its n-1 edges (in particular, its algebraic properties do not depend on its shape). We exploit this product structure to deform the cut ideal of a tree to an initial monomial ideal with a simple combinatorial description: it coincides with the edge ideal of the incomparability graph of the power set of the edges of the tree. The vertices of the incomparability graph are subsets of the edges of the tree, and two subsets form an edge whenever they are incomparable. In order to obtain algebraic information about these edge ideals, we apply an idea introduced by Dochtermann and Engström in 2009 that consists in regarding the edge ideal of a graph as the (monomial) Stanley-Reisner ideal of the independence complex of the graph. Using Hochster\'s formula for computting Betti numbers of Stanley-Reisner ideals by means of simplicial homology, the computation of the Betti numbers of these monomial ideals is turned to the enumeration of induced subgraphs of the incomparability graph. That the resulting values give upper bounds for the Betti numbers of the cut ideals of trees is an important well-known result in commutative algebra. In the second chapter, we focus on some combinatorial features of triangulations of the point configuration obtained as the cartesian product of two standard simplices. These were explored in collaboration with César Ceballos and Arnau Padrol, and had a two-fold motivation. On the one hand, we intended to understand the influence of the product structure on the set of triangulations of the cartesian product of two point configurations; on the other hand, the set of all triangulations of the product of two simplices is an intricate and interesting object that has attracted attention both in discrete geometry and in other fields of mathematics such as commutative algebra, algebraic geometry, enumerative geometry or tropical geometry. Our approach to both objectives is to examine the circumstances under which a triangulation of the polyhedral complex given by the the product of an (n-1)-simplex times the (k-1)-skeleton of a (d-1)-simplex extends to a triangulation of an (n-1)-simplex times a (d-1)-simplex. We refer to the former as a partial triangulation of the product of two simplices. Our main result says that if d >= k > n, a partial triangulation always extends to a uniquely determined triangulation of the product of two simplices. A somewhat unexpected interpretation of this result is as a finiteness statement: it asserts that if d is sufficiently larger than n, then all partial triangulations are uniquely determined by the (compatible) triangulations of its faces of the form “(n-1)-simplex times n-simplex”. Consequently, one can say that in this situation ‘\'triangulations of an (n-1)-simplex times a (d-1)-simplex are not much more complicated than triangulations of an (n-1)-simplex times an n-simplex\'\'. The uniqueness assertion of our main result holds already when d>=k>=n. However, the same is not true for the existence assertion; namely, there are non extendable triangulations of an (n-1)-simplex times the boundary of an n-simplex that we explicitly construct. A key ingredient towards this construction is a triangulation of the product of two (n-1)-simplices that can be seen as its ``second simplest triangulation\'\' (the simplest being its staircase triangulation). It seems to be knew, and we call it the Dyck path triangulation. This triangulation displays symmetry under the cyclic group of order n that acts by simultaneously cycling the indices of the points in both factors of the product. Next, we exhibit a natural extension of the Dyck path triangulation to a triangulation of an (n-1)-simplex times an n-simplex that, in a sense, enjoys some sort of ‘\'rigidity\'\' (it also seems new). Performing a ‘\'local modification\'\' on the restriction of this extended triangulation to the polyhedral complex given by (n-1)-simplex times the boundary of an n-simplex yields the non-extendable partial triangulation. The thesis includes two appendices on basic commutative algebra and triangulations of point configuration, included to make it slightly self-contained.

In this thesis, we undertake a combinatorial study of certain aspects of triangulations of cartesian products of simplices, particularly in relation to their relevance in toric algebra and to their underlying product structure. The first chapter reports joint work with Samu Potka. The object of study is a class of homogeneous toric ideals called cut ideals of graphs, that were introduced by Sturmfels and Sullivant 2006. Apart from their inherent appeal to combinatorial commutative algebra, these ideals also generalize graph statistical models for binary data and are related to some statistical models for phylogenetic trees. Specifically, we consider minimal free resolutions for the cut ideals of trees. We propose a method to combinatorially estimate the Betti numbers of the ideals in this class. Using this method, we derive upper bounds for some of the Betti numbers, given by formulas exponential in the number of vertices of the tree. Our method is based on a common technique in commutative algebra whereby arbitrary homogeneous ideals are deformed to initial monomial ideals, which are easier to analyze while conserving some of the information of the original ideals. The cut ideal of a tree on n vertices turns out to be isomorphic to the Segre product of the cut ideals of its n-1 edges (in particular, its algebraic properties do not depend on its shape). We exploit this product structure to deform the cut ideal of a tree to an initial monomial ideal with a simple combinatorial description: it coincides with the edge ideal of the incomparability graph of the power set of the edges of the tree. The vertices of the incomparability graph are subsets of the edges of the tree, and two subsets form an edge whenever they are incomparable. In order to obtain algebraic information about these edge ideals, we apply an idea introduced by Dochtermann and Engström in 2009 that consists in regarding the edge ideal of a graph as the (monomial) Stanley-Reisner ideal of the independence complex of the graph. Using Hochster\''s formula for computting Betti numbers of Stanley-Reisner ideals by means of simplicial homology, the computation of the Betti numbers of these monomial ideals is turned to the enumeration of induced subgraphs of the incomparability graph. That the resulting values give upper bounds for the Betti numbers of the cut ideals of trees is an important well-known result in commutative algebra. In the second chapter, we focus on some combinatorial features of triangulations of the point configuration obtained as the cartesian product of two standard simplices. These were explored in collaboration with César Ceballos and Arnau Padrol, and had a two-fold motivation. On the one hand, we intended to understand the influence of the product structure on the set of triangulations of the cartesian product of two point configurations; on the other hand, the set of all triangulations of the product of two simplices is an intricate and interesting object that has attracted attention both in discrete geometry and in other fields of mathematics such as commutative algebra, algebraic geometry, enumerative geometry or tropical geometry. Our approach to both objectives is to examine the circumstances under which a triangulation of the polyhedral complex given by the the product of an (n-1)-simplex times the (k-1)-skeleton of a (d-1)-simplex extends to a triangulation of an (n-1)-simplex times a (d-1)-simplex. We refer to the former as a partial triangulation of the product of two simplices. Our main result says that if d >= k > n, a partial triangulation always extends to a uniquely determined triangulation of the product of two simplices. A somewhat unexpected interpretation of this result is as a finiteness statement: it asserts that if d is sufficiently larger than n, then all partial triangulations are uniquely determined by the (compatible) triangulations of its faces of the form “(n-1)-simplex times n-simplex”. Consequently, one can say that in this situation ‘\''triangulations of an (n-1)-simplex times a (d-1)-simplex are not much more complicated than triangulations of an (n-1)-simplex times an n-simplex\''\''. The uniqueness assertion of our main result holds already when d>=k>=n. However, the same is not true for the existence assertion; namely, there are non extendable triangulations of an (n-1)-simplex times the boundary of an n-simplex that we explicitly construct. A key ingredient towards this construction is a triangulation of the product of two (n-1)-simplices that can be seen as its ``second simplest triangulation\''\'' (the simplest being its staircase triangulation). It seems to be knew, and we call it the Dyck path triangulation. This triangulation displays symmetry under the cyclic group of order n that acts by simultaneously cycling the indices of the points in both factors of the product. Next, we exhibit a natural extension of the Dyck path triangulation to a triangulation of an (n-1)-simplex times an n-simplex that, in a sense, enjoys some sort of ‘\''rigidity\''\'' (it also seems new). Performing a ‘\''local modification\''\'' on the restriction of this extended triangulation to the polyhedral complex given by (n-1)-simplex times the boundary of an n-simplex yields the non-extendable partial triangulation. The thesis includes two appendices on basic commutative algebra and triangulations of point configuration, included to make it slightly self-contained.

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.

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)