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.

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 (REQUIRED FOR THE EXAM)

1. Introduction to polytopes and 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 combinatorial 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. 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.

6. 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.

7. 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.

EXTRA TOPICS TREATED IN THE COURSE (NOT REQUIRED FOR THE EXAM)

X1. An introduction to Grasmmannians and flag varieties
The Grassmannian: definition, examples; Plucker coordinates; transitive action of GL(V), stabilizer, dimension of the Grassmannian; Schubert cells, combinatorics of the stratification. Wedneday March 30: Flags; the (complete) flag variety: definition, examples; transitive action of GL(V), stabilizer, dimension of the complete flag variety; Schubert cells, combinatorics of the stratification: the Bruhat order.

X2. Stratified spaces and degenerations (by Allen Knutson)
Schubert varieties, matrix Schubert varieties, and pipe dreams.
Frobenius splitting, Kazhdan-Lusztig varieties, and quiver cycles.
Positroid varieties, Bruhat atlases, and wonderful compactifications of groups

X3. Grassmannians and statistical mechanical models (by Thomas Lam)
Dimer model and the positive Grassmannian
Ising model and the positive orthogonal Grassmannian
Resistor networks and the positive Lagrangian Grassmannian.

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