96760 - GEOMETRIC AND TOPOLOGICAL TOOLS FOR APPLICATIONS

Conoscenze e abilità da conseguire

At the end of the course the student acquires the knowledge of geometric and topological tools that could be used to construct mathematical models. The student knows some examples that could be involved in applications.

Contenuti

PRESENTATION OF THE COURSE

Polytopes are the n-dimensional analogues of (convex) polygons and polyhedra. Polytopes and their triangulations are a fundamental tool in applied mathematics, optimization and computer science; at the same time, they play a crucial role in several areas of pure mathematics, such as algebraic geometry, representation theory and combinatorics.

In this course we will discover some of the basic geometric and combinatorial properties of polytopes and of other related objects, such as hyperplane arrangements and matroids. We will provide several examples of polytopes (such as zonotopes, associahedra and permutohedra), and we will outline applications to linear optimization.

A special focus will be on triangulation of polytopes of vector configurations: we will explore the rich combinatorics of flips and the connections with topology and algebra, together with algorithmic applications.

Fillippo De Dominicis (Professor of Architecture) will do some lectures on how polytope triangulations and zonotope tilings appear in achitectural composition.

We will also deal with the problem of counting lattice points in polytopes, studying Ehrhart polynomials and their properties and sketching applications to integer optimization.

TOPICS OF THE COURSE

1. Introduction to polytopes (with a glance to linear optimization)
Two ways of defining a (convex) polytope: convex hull of vertices, bounded intersection of half-spaces. First examples: simplices, cubes, regular polyhedra. Faces of a polytope; edges, facets. Linear optimization: several applications and examples. Feasible solutions and optimal solutions: connection with polytopes. Integer optimization and its applications; integer points in polytopes. Slack variables, equational form of a problem; a polytope can be expressed as an interaction of the positive orthant of R^n and of an affine subspace of R^n, for n large enough. The set of maxima of a linear functional on a polytope is a face, given by the convex hull of the vertices of the polytope that are maxima.

2. Catalan combinatorics
Triangulations of a polytope. The 2-dimensional case; Catalan numbers. Recursive and closed formula. Bijection between triangulations of a (n+2)-gon, rooted binary trees on n vertices, parenthesizations of a product of n+1 factors. Example: the triangulations of a pentagon. Flips, graph of flips of a polygon. Example: flips of the triangulations of the pentagon. The graph of flips is connected and regular of degree n-3. Extimations and bounds for its diameter.

3. Polytopes arising from algebraic, combinatorial or geometric data
The order polytope of a poset: definition, examples, main properties. Associahedra and permutohedra: definition and examples. Matroids, the basis polytope of a matroid. Examples. Generalized permutohedra. Matroids are precisely the 0/1 polytopes that are generalized permutohedra (without proof). Greedy algorithm. Theorem: matroids are precisely the families of subsets on which the greedy algorithm works for any choice of the weights.

4. Polyhedral subdivisions, triangulations, regularity
Point configurations with labels. Definition of a polyhedral subdivision; cells, simplices, triangulations. An algorithm for producing a subdivision (and possibly a triangulation) of a point configuration. Regular polyhedral subdivisions, regular triangulations; an example of a triangulation that is not regular. Refinement; the poset of subdivisions of a given configuration. Example: the poset of regular triangulations of a configuration of five points; stratification of the space of parameters.
The poset of polyhedral subdivision, with respect to refinement; examples. Two lemmas. Every polyhedral subdivision can be refined to a triangulation. Every regular polyhedral subdivision can be refined to a regular triangulations. Corank 1 configurations, definition of flips (for polytopes of arbitrary dimension).

5. Polytopes in architectural composition

-Polyope triangulations in architecture: examples and purposes;
-Zonotope tilings in architecture: examples and purposes.

6. The secondary polytope
Definition of GKZ vector of a triangulation; definition of the secondary polytope. Examples. Recalls on polyhedral cones and fans. The secondary fan and its properties (without proof). The secondary fan is the inner normal fan of the secondary polytope. GKZ Theorem: there is an order-preserving bijection between faces of the secondary polytope and regular polyhedral subdivisions of the point configuration.

7. Ehrhart theory: the basics
Integer points in polytopes, definition of the Ehrhart function. Theorem: the Ehrhart function is polynomial of degree the dimension of the polytope. Recalls on Moebius inversion formula. Ehrhart- Macdonald reciprocity theorem. Ehrhart quasi-polynomial, examples.

8. Ehrhart theory: applications and problems
Applications of Ehrhart theory to magic squares: semimagic squares and the Birkhoff- Von Neumann polytope, magic squares and their polytope, examples and open problems. Ehrhart polynomials of zonotopes and permutohedra. Ehrhart positivity: the Reeve's polytope, counterexamples to Ehrhart positivity for order polytopes and matroid polytopes.

Testi/Bibliografia

We will read a few pages from the books

1) "Triangulations. Structures for algorithms and applications" by J. De Loera, J. Rambau and F. Santos.

2) "Computing the Continuous Discretely. Integer-Point Enumeration in Polyhedra" by M. Beck and S. Robins

For applications, we will also have a look to:

3) "Understanding and using linear programming" by J. Matousek, B. Gärtner

Metodi didattici

Lessons will be interactive, encouraging the participation of students. Every week a few exercises will be proposed, for a better understanding of the theory.

Modalità di verifica e valutazione dell'apprendimento

Oral exam, including exercises and proofs

Strumenti a supporto della didattica

Usually chalk; occasionally slides, when the pictures to show are too complicated :)

Orario di ricevimento

Consulta il sito web di Luca Moci