Boij-Söderberg theory shows that the Betti table of a graded module can be written as a linear combination of pure diagrams with integer coefficients. In chapter 2 using Ferrers hypergraphs and simplicial polytopes, we provide interpretations of these coefficients for ideals with a d-linear resolution, their quotient rings, and for Gorenstein rings whose resolution has essentially at most two linear strands. We also establish a structural result on the decomposition in the case of quasi-Gorenstein modules. These results are published in the Journal of Algebra, see [25]. In chapter 3 we provide some further results about Boij-Söderberg decompositions. We show how truncation of a pure diagram impacts the decomposition. We also prove constructively that every integer multiple of a pure diagram of codimension 2 can be realized as the Betti table of a module. In chapter 4 we introduce the idea of a c-polar self-dual polytope. We prove that in dimension 2 only the odd n-gons have an embedding which is polar self-dual. We also define the family of Ferrers polytopes. We prove that the Ferrers polytope in dimension d is d-polar self-dual hence establishing a nontrivial example of a polar self-dual polytope in all dimension. Finally we prove that the Ferrers polytope in dimension d supports a cellular resolution of the Stanley-Reisner ring of the (d+3)-gon.

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.

Thesis (Ph. D.)--University of Alabama at Birmingham, 2006. / Description based on contents viewed Jan. 26, 2007; title from title screen. Includes bibliographical references (p. 119-125).

Thesis (Ph. D.)--University of Washington, 2007. / Vita. Includes bibliographical references (p. 132-136).

[pt] Um politopo convexo é semiregular se todas as suas faces forem regulares e o grupo de isometrias agir transitivamente sobre os vértices. A classificação dos politopos semiregulares inclui algumas famílias infinitas, algumas exceções em dimensão baixa e uma família, os politopos de Gosset, que está definida para dimensão entre 3 e 8. Certos grupos de isometrias de R(n) gerados por reflexões são chamados grupos de Coxeter. A classificação dos grupos de Coxeter inclui três famílias infinitas, algumas exceções em dimensão menor ou igual a 4 e os grupos excepcionais E(6), E(7) e E(8). O grupo E(n) é o grupo das isometrias do politopo de Gosset em dimensao n. Nesta dissertação construiremos os grupos de Coxeter En, os politopos de Gosset e indicaremos a relação destes objetos com os reticulados e as álgebras de Lie também conhecidos como E(n). / [en] A convex polytope is semiregular if all its faces are regular and the group of isometries acts transitively over vertices. The classification of semiregular polytopes includes a few infinite families, some low dimensional exceptions and a family, the Gosset polytopes, which is defined for dimension 3 to 8. Certain groups of isometries of R(n) generated by reflections are called Coxeter groups. The classification of finite Coxeter groups includes three infinite families, some exceptions in dimension 4 or lower and the exceptional groups E(6), E(7) and E(8). The group En is the group of isometries of the Gosset polytope in dimension n. In this dissertation we construct the Coxeter groups En, the Gosset polytopes and indicate the relationship of these objects with the lattices and Lie algebras which are also known as E(n).

Diese Arbeit befasst sich mit der unimodularen Überdeckung und Triangulierung von Gitterpolytopen. Zentral ist in diesem Zusammenhang die Angabe einer möglichst guten oberen Schranke c0, so dass die Vielfachen cP eines Polytopes P für alle c>c0 eine unimodulare Überdeckung besitzen. Bruns und Gubeladze haben erstmals die Existenz einer solchen Schranke nachgewiesen und konnten sogar explizit eine solche in Abhängigkeit von der Dimension des Polytopes angeben. Allerdings war diese Schranke super-exponentiell. In dieser Arbeit wird nun u.a. eine polynomielle obere Schranke hergeleitet.

This dissertation presents recent contributions in tropical geometry with a view towards positivity, and on certain semialgebraic sets which are constructed from polytopes. Tropical geometry is an emerging field in mathematics, combining elements of algebraic geometry and polyhedral geometry. A key in establishing this bridge is the concept of tropicalization, which is often described as mapping an algebraic variety to its 'combinatorial shadow'. This shadow is a polyhedral complex and thus allows to study the algebraic variety by combinatorial means. Recently, the positive part, i.e. the intersection of the variety with the positive orthant, has enjoyed rising attention. A driving question in recent years is: Can we characterize the tropicalization of the positive part? In this thesis we introduce the novel notion of positive-tropical generators, a concept which may serve as a tool for studying positive parts in tropical geometry in a combinatorial fashion. We initiate the study of these as positive analogues of tropical bases, and extend our theory to the notion of signed-tropical generators for more general signed tropicalizations. Applying this to the tropicalization of determinantal varieties, we develop criteria for characterizing their positive part. Motivated by questions from optimization, we focus on the study of low-rank matrices, in particular matrices of rank 2 and 3. We show that in rank 2 the minors form a set of positive-tropical generators, which fully classifies the positive part. In rank 3 we develop the starship criterion, a geometric criterion which certifies non-positivity. Moreover, in the case of square-matrices of corank 1, we fully classify the signed tropicalization of the determinantal variety, even beyond the positive part. Afterwards, we turn to the study of polytropes, which are those polytopes that are both tropically and classically convex. In the literature they are also established as alcoved polytopes of type A. We describe methods from toric geometry for computing multivariate versions of volume, Ehrhart and h^*-polynomials of lattice polytropes. These algorithms are applied to all polytropes of dimensions 2,3 and 4, yielding a large class of integer polynomials. We give a complete combinatorial description of the coefficients of volume polynomials of 3-dimensional polytropes in terms of regular central subdivisions of the fundamental polytope, which is the root polytope of type A. Finally, we provide a partial characterization of the analogous coefficients in dimension 4. In the second half of the thesis, we shift the focus to study semialgebraic sets by combinatorial means. Intersection bodies are objects arising in geometric tomography and are known not to be semialgebraic in general. We study intersection bodies of polytopes and show that such an intersection body is always a semialgebraic set. Computing the irreducible components of the algebraic boundary, we provide an upper bound for the degree of these components. Furthermore, we give a full classification for the convexity of intersection bodies of polytopes in the plane. Towards the end of this thesis, we move to the study of a problem from game theory, considering the correlated equilibrium polytope $P_G$ of a game G from a combinatorial point of view. We introduce the region of full-dimensionality for this class of polytopes, and prove that it is a semialgebraic set for any game. Through the use of oriented matroid strata, we propose a structured method for classifying the possible combinatorial types of $P_G$, and show that for (2 x n)-games, the algebraic boundary of each stratum is a union of coordinate hyperplanes and binomial hypersurfaces. Finally, we provide a computational proof that there exists a unique combinatorial type of maximal dimension for (2 x 3)-games.:Introduction 1. Background 2. Tropical Positivity and Determinantal Varieties 3. Multivariate Volume, Ehrhart, and h^*-Polynomials of Polytropes 4. Combinatorics of Correlated Equilibria

No description available.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第23681号 / 理博第4771号 / 新制||理||1683(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 加藤 周, 教授 雪江 明彦, 教授 平岡 裕章 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

Cette thèse étudie différents problèmes de minimisations avec des fonctions de régularisations qui promeuvent la parcimonie. Plus précisément, on souhaite reconstruire une image, que l'on suppose parcimonieuse et qui a subit une transformation après un opérateur linéaire, à l'aide de problèmes de minimisations. Dans ce manuscrit, on s'intéressera plus particulièrement à la minimisation l1 synthèse, analyse et bloc qui sont très utilisées pour reconstruction une image que l'on sait parcimonieuse. Ces minimisations produisent en pratique des résultats convaincants qui n'ont été compris théoriquement que récemment. Les différents travaux sur le sujet mettent en évidence le rôle d'un vecteur particulier appelé certificat dual. L'existence d'un certificat dual permet à la fois d'assurer la reconstruction exacte d'une image dans le cas où il n'y a pas de perturbations et d'estimer l'erreur de la reconstruction en présence de perturbations. Dans nos travaux, nous allons introduire l'existence d'un certifical dual optimal pour la minimisation l1 synthèse qui minimisent l'erreur de reconstruction. Ces résultats ayant une forte interprétation géométrique, nous avons développé un critère identifiabilité, c'est à dire que ce critère assure que l'image recherchée est l'unique solution du problème de minimisation. Ce critère permet d'étendre nos travaux à la minimisation l1 analyse, l1 bloc et à d'autres cas. / This thesis studies different minimization problems with sparses based regularization. More precisely, we want to reconstruct a sparses image, which undergone a linear transformation, with minimization problems. In this manuscript, we will be focused on l1 synthesis, analysis and block minimization which are widely used in sparse approximations. These problems offer competitive results which are theorietical understood only recntly. Different studies on the subject emphasized the contribution of a particular vector called dual certificate. The existence of this dual certificate allows simultaneously to guarantee the exact recovey of an image in noiseless case and to estimate the noise robustness in noisy case. In this work, we introduce eth existence of an optimal dual certificate for the l1 synthesis minimization which minimizes the reconstruction error. As those results have a strong geometrical interpretation, we develop an identifiability criterion which ensures the uniqueness of a solution. This criterion generalizes the work on l1 synthesis minimization tothe analysis case, block case and others.