Materials:

# DISCRETE CONVEXITY AND APPLICATIONS: FROM STABLE MATCHINGS TO QUANTUM GROUPS

Tuesday, 21 February 2017 to Tuesday, 07 March 2017
10:00

Amphi Becquerel, École polytechnique

February 21rst : 10h00 – 12h15 and 14h00 – 16h15

March 7th : 10h00 – 12h15 and 14h00 – 16h15

Discrete convexity is a theory of convexity on lattices, free Abelian groups. A class of discretely convex set is a maximal collection of subsets of a lattice which possess the separation axiom. An ample class of discrete convexity is determined by the set of directions of its one-dimensional subsets. Such a set of vectors is totally unimodular and we get a bijection between classes of discretely convex sets and totally unimodular sets.

Thanks to the Seymour theorem we know the construction of totally unimodular sets. For general classes, the characterization problem is an open question. To each class of discrete convexity is associated two dual classes of discretely concave/convex functions, one class is stable under the convolution and the dual is stable under summations. One can regard such functions as tropical hyper surfaces. For any function of such a class, a local extremum turns out to be global one. We discuss several explicit constructions of such functions and a decomposition theorem on primitive elements.

A class of discrete convexity, corresponding to the graphical unimodular system $A_n$, is closely related to the class of g-polymatroids, a well-known class of polyhedra in combinatorics and optimization. The corresponding class of functions which is stable under convolutions contains valuated matroids. We discuss several explicit constructions and show that stable matchings and equilibria in economies with indivisibles exist if preferences of agents belong to some class of discrete convexity. The Horn problem on spectra of Hermitean matrices is equivalent to the question on existence of discretely convex function on a triangular grid with given boundary conditions. Piece-wise linear combinatorics of the canonical bases due to Lusztig is related to piece-wise linear combinatorics of discretely convex functions for $A_n$.

We also discuss generalizations possessing classes of the form of combinations of several classes of discrete convexity.

This lecture series is organized by Fondation

and École polytechnique, in the framework

of the Gaspard Monge Optimization Programme

supported by EDF.

Lectures are open to researchers

Registration (free of charge) on