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