23 - 24 Janvier 2018: Première réunion ANR CAPPS

Polytopes à Paris 2018


L'inscription est gratuite mais obligatoire. Inscriptions ici.


Mardi 23 Janvier 2018

9:30 - 10:30
Michèle Vergne (IMJ-PRG, Université Paris-Diderot Paris 7)
Polytopes et théorie des représentations

Convex rational polytopes arise naturally in Linear algebra and Representation theory. For example, given two sets $S_1$ , $S_2$ of $d$ real numbers, the Horn polytope $H(S_1, S_2)$ describes the possible eigenvalues of a matrix $A = A_1 + A_2$, where $A_1, A_2$ are $d \times d$ Hermitian matrices with set of eigenvalues $S_i$ , $i = 1, 2$. If the elements of the sets $S_i$ are integers, the number of integral points in $H(S_1, S_2)$ is the Littlewood-Richardson coefficient. I will discuss some other examples related to quantum computing, and techniques to compute number of integral points in polytopes.

10:30 - 11: 00
Pause café
11:00 - 12:00
Kolja Knauer (LIF, Université Aix-Marseille)
Oriented matroids and beyond

Acyclic orientations of a graph, linear extensions of a poset, hyperplane arrangements, linear dissections of polyhedra, pseudoline arrangements...all of these can be seen as (complexes of) oriented matroids (COMs).
The tope graph of a COM is a graph capturing all the information of this potentially quite complex object. In the above examples it corresponds to: the flip graph of acyclic orientations (two are linked by an edge if they differ in one arc), the linear extension graph of a poset (two are linked if they differ by one neighboring transposition), the region graphs of any of the other examples.
In this talk, I will explain all these concepts carefully. Finally we will give a purely graph theoretic characterization of tope graphs of COMs, which furthermore is polytime verifyable. This answers a kind of central question in Oriented Matroid Theory and in a sense identifies the latter as a branch of Metric Graph Theory.

12:00 - 14:00
Pause déjeuner
14:00 - 15:00
Xavier Allamigeon (INRIA et CMAP, École Polytechnique)
Tropical Linear Optimization

In this talk, I will explain how the study of the tropical analogue of linear programming bring new results in relation with two notoriously open problems in computational optimization. The first problem, known as 9th Smale's problem, is the existence of a strongly polynomial time algorithm for linear programming. The second one is whether or not mean payoff games (a class of repeated zero-sum games with perfect information) can be solved in polynomial time. These contributions are obtained by tropicalizing standard algorithms in linear programming, namely the simplex and interior-point methods.
This is joint work with Pascal Benchimol (EDF R&D), Stéphane Gaubert (INRIA and Ecole Polytechnique) and Michael Joswig (TU Berlin).

15:00 - 15:30
Pause café
15:30 - 17:30
Business meeting (discussion projet ANR CAPPS)

Mercredi 24 Janvier 2018

9:30 - 10:30
Samuel Fiorini (Université libre de Bruxelles)
Counting 2-level polytopes

Two-level polytopes are fascinating polytopes that appear in different contexts (Erhart theory, sum-of-squares hierarchies, and more). They generalize, for instance, stable set polytopes of perfect graphs. Although all the evidence we have indicates that they have a very constrained structure, so far there are very few general results about 2-level polytopes.
In this talk I will report on recent results about 2-level polytopes. In particular, we can show that there are very few 2-level polytopes: at most $2^{O(d^2 log(d))}$, up to isomorphism. The same bound also applies to 2-level cones. This result is joint work with Marco Macchia and Kanstantsin Pashkovich.

10:30 - 11: 00
Pause café
11:00 - 12:00
Frédéric Meunier (CERMICS, École Nationale des Ponts et Chaussées)
A tropical analogue of the linear complementarity problem

The linear complementarity problem is an important feasibility problem in mathematical programming related to the computation of equilibria in economics and to convex quadratic minimization. We formulate and investigate a tropical analogue of this problem. While solving this tropical analogue in its full generality is NP-complete, a special case, which can be interpreted as Nash equilibrium computation in a tropical bimatrix game, turns out to be polynomial. It departs from its classical counterpart that is known to be hard (PPAD-complete). The general motivation of this work relies on recent results of Allamigeon et al., which have shown how tropical analogues of linear programming improve the understanding of the classical versions of simplex and interior-points methods.
Joint work with Xavier Allamigeon and Stéphane Gaubert.

12:00 - 14:00
Pause déjeuner
14:00 - 15:00
Alfredo Hubard (LIGM, Université Paris-Est Marne-la-Vallée )
Une théorème topologique de superposition

Dans le début des années 80 Bàràny a montré qu'il existe une constante $c_d$, telle que pour tout ensemble de points $P \subset \mathbb{R}^d$, il existe un point $b$ in $\mathbb{R}^d$ t.q. une fraction d'au moins $c_d$ des $(d+1)$-tuples de points de $P$, contient $b$ dans son enveloppe convexe.
À la fin des années 80, Pach a prouvé une version chromatique de cette théorème: il existe une constante $c_d’$, telle que pour tout famille de $d+1$ ensembles $P_0, P_1\dots P_d$, il existe un point $p \in\mathbb{R}^d$, et sous-ensembles $A_i \subset P_i$, de taille $|A_i|>c_d'|P_i|$, tels que toute $(d+1)$-tuple “arc-en-ciel”, i.e. $a_0 \in A_0, a_1 \in A_1, \dots a_d \in A_d$, contient $p$ dans son enveloppe convexe.
En 2010 Gromov à prouvé une version topologique du théorème de Bàràny. Dans cette lecture j'expliquerai l'analogue topologique du théorème de Pach (la version chromatique du théorème de Gromov).
Il s’agit d’un travail commun avec Boris Bukh.

15:00 - 15:30
Pause café
15:30 - 16:30
Vincent Pilaud (LIX, École Polytechnique)

L'ordre faible est un treillis fondamental sur les permutations. Il s'obtient en orientant le permutaèdre dans une direction linéaire. Les quotients de ce treillis sont très souvent intéressants : par exemple, le treillis de Tamari sur les arbres binaires est le quotient de l'ordre faible par la relation sylvestre. Nathan Reading a étudié en détail la combinatoire et la géométrie des quotients de l'ordre faible (et plus généralement des posets des régions d'un arrangement d'hyperplans). Il a montré en particulier que pour toute congruence de l'ordre faible, les cones obtenus en recollant les régions de l'arrangement de Coxeter dans une même classe d'équivalence forment un éventail complet. Dans cet exposé, je vous montrerai que cet éventail est l'éventail normal d'un polytope que j'appelle quotientope. Travail en commun avec Francisco Santos.

16:30 - 17:30
Arnau Padrol (IMJ-PRG, Sorbonne Université)
Counting polytopes

I will start this talk by introducing the current knowledge on the enumeration of combinatorial types of convex polytopes and related objects. Despite this being a classical topic, only in dimensions up to 3 we have a good understanding on the asymptotic growth of the number of polytopes with respect to the number of vertices. I will present open problems and partial results on two lines of research: the enumeration of d-polytopes with d+3 vertices and the enumeration of d-polytopes in terms of their number of vertices and facets.


salle 101 1r étage barre 15-16, Campus Jussieu, Sorbonne Université


Arnau Padrol