No description available.

No description available.

Steeb, W.H., Prof.

Thesis (Ph.D.) - University of Queensland, 2005. / Includes bibliography.

Orientador: Patrícia Helena Araújo da Silva Nogueira / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-17T08:03:36Z (GMT). No. of bitstreams: 1 Staib_FredericoFontes_M.pdf: 14016255 bytes, checksum: 4ec6112a82029b5e16c1c450779bf803 (MD5) Previous issue date: 2010 / Resumo: Neste trabalho, estudamos a teoria das bases de Gröbner e sua aplicação ao problema da k-coloração de grafos, estabelecendo assim uma interessante conexão entre a álgebra abstrata e a matemática discreta. Fazemos também uma abordagem de caráter lúdico, traduzindo o passatempo chamado Sudoku em um problema de 9-coloração e utilizando a teoria apresentada para resolvê-lo através das bases de Gröbner / Abstract: In the present work, we study the Gröbner basis theory and its application on the graph k-coloring problem, establishing an interesting relation between abstract algebra and discrete mathematics. We make a ludic approach, translating the puzzle called Sudoku to a 9-coloring problem and using the given theory to solve it by the Gröbner basis / Mestrado / Algebra / Mestre em Matemática

xi, 95 p. : ill. A print copy of this thesis is available through the UO Libraries. Search the library catalog for the location and call number. / We investigate some homological properties of graded algebras. If A is an R -algebra, then E (A) := Ext A ( R, R ) is an R-algebra under the cup product and is called the Yoneda algebra. (In most cases, we assume R is a field.) A well-known and widely-studied condition on E(A) is the Koszul property. We study a class of deformations of Koszul algebras that arises from the study of equivariant cohomology and algebraic groups and show that under certain circumstances these deformations are Poincaré-Birkhoff-Witt deformations. Some of our results involve the [Special characters omitted] property, recently introduced by Cassidy and Shelton, which is a generalization of the Koszul property. While a Koszul algebra must be quadratic, a [Special characters omitted] algebra may have its ideal of relations generated in different degrees. We study the structure of the Yoneda algebra corresponding to a monomial [Special characters omitted.] algebra and provide an example of a monomial [Special characters omitted] algebra whose Yoneda algebra is not also [Special characters omitted]. This example illustrates the difficulty of finding a [Special characters omitted] analogue of the classical theory of Koszul duality. It is well-known that Poincaré-Birkhoff-Witt algebras are Koszul. We find a [Special characters omitted] analogue of this theory. If V is a finite-dimensional vector space with an ordered basis, and A := [Special characters omitted] (V)/I is a connected-graded algebra, we can place a filtration F on A as well as E (A). We show there is a bigraded algebra embedding Λ: gr F E (A) [Special characters omitted] E (gr F A ). If I has a Gröbner basis meeting certain conditions and gr F A is [Special characters omitted], then Λ can be used to show that A is also [Special characters omitted]. This dissertation contains both previously published and co-authored materials. / Committee in charge: Brad Shelton, Chairperson, Mathematics; Victor Ostrik, Member, Mathematics; Christopher Phillips, Member, Mathematics; Sergey Yuzvinsky, Member, Mathematics; Van Kolpin, Outside Member, Economics

Given the result $v_0$ of a survey and a nested collection of summary statistics that could be used to describe that result, it is natural to ask which of these summary statistics best describe $v_0$. In 1998 Diaconis and Sturmfels presented an approach for determining the conditional significance of a higher order statistic, after sampling a space conditioned on the value of a lower order statistic. Their approach involves the computation of a Markov basis, followed by the use of a Markov process with stationary hypergeometric distribution to generate a sample.This technique for data analysis has become an accepted tool of algebraic statistics, particularly for the study of fully ranked data. In this thesis, we explore the extension of this technique for data analysis to the study of partially ranked data, focusing on data from surveys in which participants are asked to identify their top $k$ choices of $n$ items. Before we move on to our own data analysis, though, we present a thorough discussion of the Diaconis–Sturmfels algorithm and its use in data analysis. In this discussion, we attempt to collect together all of the background on Markov bases, Markov proceses, Gröbner bases, implicitization theory, and elimination theory, that is necessary for a full understanding of this approach to data analysis.

The theory of Grobner bases has garnered the interests of a large number of researchers in computational algebra due to its applications not only in mathematics but also in areas like control systems, robotics, cryptography to name a few. It is well known that the computation of Grobner bases takes time doubly exponential in the number of indeterminates rendering it impractical in all but a few places.The current known algorithms for Grobner bases depend on the term order over which Grobner bases is computed. In this thesis, we study computational complexity of some problems in computational ideal theory. We also study the algebraic formulation of combinatorial optimization problems. Gritzmann and Sturmfels (1993) posed the following question: Given a set of generators, decide whether it is a Gr¨obner bases with respect to some term order. This problem, termed as the Grobner Basis Detection(GBD)problem, was introduced as an application of Minkowski addition of polytopes. It was shown by Sturmfels and Wiegelmann (1997) that GBD is NP-hard. We study the problem for the case of zero-dimensional ideals and show that the problem is hard even in this special case. We study the detection problem in the case of border bases which are an alternative to Grobner bases in the case of zero dimensional ideals. We propose the Border Basis Detection(BBD) problem which is defined as follows: Given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. It is shown that BBD is NP-complete. We also formulate the rainbow connectivity problem as a system of polynomial equations such that solving the polynomial system yields a solution to it. We give an alternate formulation of the rainbow connectivity problem as a membership problem in polynomial ideals.

Tropical geometry is an area of mathematics that interfaces algebraic geometry and combinatorics. The main object of study in tropical geometry is the tropical variety, which is the combinatorial counterpart of a classical variety. A classical variety is converted into a tropical variety by a process called tropicalization, thus reducing the problems of algebraic geometry to problems of combinatorics. This new tropical variety encodes several useful information about the original variety, for example an algebraic variety and its tropical counterpart have the same dimension. In this thesis, we look at the some of the computational aspects of tropical algebraic geometry. We study a generalization of Grobner basis theory of modules which unlike the standard Grobner basis also takes the valuation of coefficients into account. This was rst introduced in (Maclagan & Sturmfels, 2009) in the settings of polynomial rings and its computational aspects were first studied in (Chan & Maclagan, 2013) for the polynomial ring case. The motivation for this comes from tropical geometry as it can be used to compute tropicalization of varieties. We further generalize this to the case of modules. But apart from that it has many other computational advantages. For example, in the standard case the size of the initial submodule generally grows with the increase in degree of the generators. But in this case, we give an example of a family of submodules where the size of the initial submodule remains constant. We also develop an algorithm for computation of Grobner basis of submodules of modules over Z=p`Z[x1; : : : ; xn] that works for any weight vector. We also look at some of the important applications of this new theory. We show how this can be useful in efficiently solving the submodule membership problem. We also study the computation of Hilbert polynomials, syzygies and free resolutions.