Thèse doctorat : Informatique : Strasbourg 1 : 2006. / Titre provenant de l'écran-titre. Bibliogr.11 p.

Abstract not available. / text

The Ehrhart function L_P(t) of a polytope P is defined to be the number of integer points in the dilated polytope tP. Classical Ehrhart theory is mainly concerned with integer values of t; in this master thesis, we focus on how the Ehrhart function behaves when the parameter t is allowed to be an arbitrary real number. There are three main results concerning this behavior in this thesis. Some rational polytopes (like the unit cube [0, 1]^d) only gain integer points when the dilation parameter t is an integer, so that computing L_P(t) yields the same integer point count than L_P(t). We call them semi-reflexive polytopes. The first result is a characterization of these polytopes in terms of the hyperplanes that bound them. The second result is related to the Ehrhart theorem. In the classical setting, the Ehrhart theorem states that L_P(t) will be a quasipolynomial whenever P is a rational polytope. This is also known to be true with real dilation parameters; we obtained a new proof of this fact starting from the chraracterization mentioned above. The third result is about how the real Ehrhart function behaves with respect to translation in this new setting. It is known that the classical Ehrhart function is invariant under integer translations. This is far from true for the real Ehrhart function: not only there are infinitely many different functions L_{P + w}(t) (for integer w), but under certain conditions the collection of these functions identifies P uniquely. / A função de Ehrhart L_P(t) de um politopo P é definida como sendo o número de pontos com coordenadas inteiras no politopo dilatado tP. A teoria de Ehrhart clássica lida principalmente com valores inteiros de t; esta dissertação de mestrado foca em como a função de Ehrhart se comporta quando permitimos que o parâmetro t seja um número real arbitrário. São três os resultados principais desta dissertação a respeito deste comportamento. Alguns politopos racionais (como o cubo unitário [0, 1]^d) apenas ganham pontos inteiros quando o parâmetro de dilatação t é um inteiro, de tal forma que computar L_P(t) devolve a mesma contagem de pontos que L_P(t). Eles são chamados de politopos semi-reflexivos. O primeiro resultado desta dissertação é uma caracterização destes politopos em termos de suas descrições como interseção de semi-espaços. O segundo resultado é relacionado ao teorema de Ehrhart. No contexto clássico, o teorema de Ehrhart afirma que L_P(t) será um quasi-polinômio sempre que P for um politopo racional. Sabe-se que este teorema generaliza para parâmetros reais de dilatação; nesta dissertação é apresentada uma nova demonstração deste fato, baseada na caracterização mencionada acima. O terceiro resultado é sobre como a função real de Ehrhart se comporta com respeito à translação neste novo contexto. Sabe-se que a função de Ehrhart clássica é invariante sob translações por vetores com coordenadas inteiras. Por outro lado, a função real de Ehrhart está bem longe de ser invariante: não só existem infinitas funções L_{P + w}(t) distintas, mas também, sob certas condições, esta coleção de funções identifica P unicamente.

The Ehrhart function L_P(t) of a polytope P is defined to be the number of integer points in the dilated polytope tP. Classical Ehrhart theory is mainly concerned with integer values of t; in this master thesis, we focus on how the Ehrhart function behaves when the parameter t is allowed to be an arbitrary real number. There are three main results concerning this behavior in this thesis. Some rational polytopes (like the unit cube [0, 1]^d) only gain integer points when the dilation parameter t is an integer, so that computing L_P(t) yields the same integer point count than L_P(t). We call them semi-reflexive polytopes. The first result is a characterization of these polytopes in terms of the hyperplanes that bound them. The second result is related to the Ehrhart theorem. In the classical setting, the Ehrhart theorem states that L_P(t) will be a quasipolynomial whenever P is a rational polytope. This is also known to be true with real dilation parameters; we obtained a new proof of this fact starting from the chraracterization mentioned above. The third result is about how the real Ehrhart function behaves with respect to translation in this new setting. It is known that the classical Ehrhart function is invariant under integer translations. This is far from true for the real Ehrhart function: not only there are infinitely many different functions L_{P + w}(t) (for integer w), but under certain conditions the collection of these functions identifies P uniquely. / A função de Ehrhart L_P(t) de um politopo P é definida como sendo o número de pontos com coordenadas inteiras no politopo dilatado tP. A teoria de Ehrhart clássica lida principalmente com valores inteiros de t; esta dissertação de mestrado foca em como a função de Ehrhart se comporta quando permitimos que o parâmetro t seja um número real arbitrário. São três os resultados principais desta dissertação a respeito deste comportamento. Alguns politopos racionais (como o cubo unitário [0, 1]^d) apenas ganham pontos inteiros quando o parâmetro de dilatação t é um inteiro, de tal forma que computar L_P(t) devolve a mesma contagem de pontos que L_P(t). Eles são chamados de politopos semi-reflexivos. O primeiro resultado desta dissertação é uma caracterização destes politopos em termos de suas descrições como interseção de semi-espaços. O segundo resultado é relacionado ao teorema de Ehrhart. No contexto clássico, o teorema de Ehrhart afirma que L_P(t) será um quasi-polinômio sempre que P for um politopo racional. Sabe-se que este teorema generaliza para parâmetros reais de dilatação; nesta dissertação é apresentada uma nova demonstração deste fato, baseada na caracterização mencionada acima. O terceiro resultado é sobre como a função real de Ehrhart se comporta com respeito à translação neste novo contexto. Sabe-se que a função de Ehrhart clássica é invariante sob translações por vetores com coordenadas inteiras. Por outro lado, a função real de Ehrhart está bem longe de ser invariante: não só existem infinitas funções L_{P + w}(t) distintas, mas também, sob certas condições, esta coleção de funções identifica P unicamente.

Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, PG, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, PD. Basic properties of both families of simplices, PG and PD, are established using techniques from Ehrhart theory. Motivated by a well-known conjecture in the field, our investigation focuses on reflexivity, the integer decomposition property, and unimodality of Ehrhart h*-vectors of these polytopes. A systematic investigation of PG for trees, cycles, and complete graphs is provided, which is enhanced by an investigation of PD for cyclic digraphs. We form intriguing connections with other families of simplices and produce G and D such that the h*-vectors of PG and PD exhibit extremal behavior.

Lattices are an easy and clean class of periodic arrangements that are not only discrete but associated with algebraic structures. We will specifically discuss applying lattices theory to computing the area of polygons in the plane and some optimization problems. This thesis will details information about Pick's Theorem and the higher-dimensional cases of Ehrhart Theory. Closely related to Pick's Theorem and Ehrhart Theory is the Frobenius Problem and Integer Knapsack Problem. Both of these problems have higher-dimension applications, where the difficulties are similar to those of Pick's Theorem and Ehrhart Theory. We will directly relate these problems to optimization problems and operations research.

The broad topic of this dissertation is the study of algebraic structure arising from polyhedral geometric objects. There are three distinct topics covered over three main chapters. However, each of these topics are further linked by a connection to the Eulerian polynomials. Chapter 2 studies Euler-Mahonian identities arising from both the symmetric group and generalized permutation groups. Specifically, we study the algebraic structure of unit cube semigroup algebra using Gröbner basis methods to acquire these identities. Moreover, this serves as a bridge between previous methods involving polyhedral geometry and triangulations with descent bases methods arising in representation theory. In Chapter 3, the aim is to characterize Hilbert basis elements of certain 𝒔-lecture hall cones. In particular, the main focus is the classification of the Hilbert bases for the 1 mod 𝑘 cones and the 𝓁-sequence cones, both of which generalize a previous known result. Additionally, there is much broader characterization of Hilbert bases in dimension ≤ 4 for 𝒖-generated Gorenstein lecture hall cones. Finally, Chapter 4 focuses on certain algebraic and geometric properties of 𝒔-lecture hall polytopes. This consists of partial classification results for the Gorenstein property, the integer-decomposition property, and the existence of regular, unimodular triangulations.