Germain Poullot
Home Research Teaching Images Computations

# Publications and pre-prints

| Title | Year | Authors | Pre-print | Publication | BibTeX | Abstract
--- | --- | --- | --- | --- | --- | --- | ---
10 | Many rays of the submodular cone | 2025 | Georg Loho, Arnau Padrol, Germain Poullot | ArXiv |  | BibTeX |
Abstract: The study of the cone of submodular functions goes back to Jack Edmonds' seminal 1970 paper, which already highlighted the difficulty of characterizing its extreme rays. Since then, researchers from diverse fields have sought to characterize, enumerate, and bound the number of such rays. In this paper, we introduce an inductive construction that generates new rays of the submodular cone. This allows us to establish that the $n$-th submodular cone has at least $2^{2^{n-2}}$ rays, which improves upon the lower bound obtained from Hien Q. Nguyen's 1986 characterization of indecomposable matroid polytopes by a factor of order $\sqrt{n^3}$ in the exponent.
9 | New criteria for polytope indecomposability and new rays of the submodular cone | 2025 | Arnau Padrol, Germain Poullot |  | Published FPSAC 93B | BibTeX |
Abstract: A polytope is indecomposable if it cannot be expressed (non-trivially) as a Minkowski sum of other polytopes. Certifying indecomposability is difficult, and several criteria have been developed since Gale introduced the concept in 1954. Our first contribution is a new indecomposability criterion that encompasses most of the previous techniques. The major new ingredient is the introduction of the (extended) graph of edge-length dependencies, which has diverse applications in the study of deformation cones of polytopes. Our main motivation is to provide new indecomposable deformed permutahedra that are not matroid polytopes. In 1970, Edmonds proposed the problem of characterizing the extreme rays of the submodular cone, that is, indecomposable deformed permutahedra. Matroid polytopes from connected matroids give one such family of polytopes. We present a new infinite disjoint family via truncations of certain graphical zonotopes. This way, we obtain $2 \lfloor (n-1)/2 \rfloor$ new indecomposable deformations of the n-permutahedron $\Pi_n \subseteq \mathbb{R}^n$.
8 | Ehrhart non-positivity and unimodular triangulations for classes of s-lecture hall simplices | 2025 | Martina Juhnke, Jhon B. Caicedo, Germain Poullot | ArXiv |  | BibTeX |
Abstract: Counting lattice points and triangulating polytopes are prominent subjects in discrete geometry, yet proving Ehrhart positivity or the existence of unimodular triangulations remain of utmost difficulty in general, even for "easy" simplices. Inspired by a question of Olsen, we present a natural new class of sequences s for which the s-lecture hall simplices are not Ehrhart positive, by explicitly estimating a negative coefficient. Meanwhile, motivated by a conjecture of Hibi, Olsen and Tsuchiya, we extend the previously known classes of sequences s for which the s-lecture hall simplices admit flag, regular, and unimodular triangulations. The triangulations we construct are explicit.
7 | Unimodality of the number of paths per length on polytopes: Examples, counter-examples, and central limit theorem | 2025 | Martina Juhnke, Germain Poullot | ArXiv | Accepted IRMN | BibTeX |
Abstract: To solve a linear program, the simplex method follows a path in the graph of a polytope, on which a linear function increases. The length of this path is an key measure of the complexity of the simplex method. Numerous previous articles focused on the longest paths, or, following Borgwardt, computed the average length of a path for certain random polytopes. We detail more precisely how this length is distributed, i.e., how many paths of each length there are. It was conjectured by De Loera that the number of paths counted according to their length forms a unimodal sequence. We give examples (old and new) for which this holds; but we disprove this conjecture by constructing counterexamples for several classes of polytopes. However, De Loera is "statistically correct": We prove that the length of coherent paths on a random polytope (with vertices chosen uniformly on a sphere) admits a central limit theorem.
6 | Vertices of the monotone path polytopes of hypersimplicies | 2024 | Germain Poullot | ArXiv |  | BibTeX |
Abstract: The monotone path polytope of a polytope P encapsulates the combinatorial behavior of the shadow vertex rule (a pivot rule used in linear programming) on P. On the other hand, computing monotone path polytopes is the entry door to the larger subject of fiber polytopes, for which explicitly computing examples remains a challenge. Monotone path polytopes of cubes and simplices have been known since the seminal article of Billera and Strumfels 1992. We (partially) extend these results to hypersimplices by linking this problem to the combinatorics of lattice paths. Indeed, we give a combinatorial model to describe the vertices of the monotone path polytope of the hypersimplex Δ(n, 2) (for any generic direction). With this model, we give a precise count of these vertices, and furthermore count the number of coherent monotone paths on Δ(n, 2) according to their lengths. We prove that some of the results obtained also hold for hypersimplices Δ(n, k) for k ≥ 2.
5 | Pivot polytopes of products of simplices and shuffles of associahedra | 2024 | Vincent Pilaud, Germain Poullot | ArXiv | Published DCG | BibTeX |
Abstract: We provide a piecewise linear isomorphism from the normal fan of the pivot polytope of a product of simplices to the normal fan of a shuffle of associahedra.
4 | Rays of the deformation cones of graphical zonotopes | 2024 | Germain Poullot | ArXiv |  | BibTeX |
Abstract: In this paper, we compute a triangulation of certain faces of the submodular cone. More precisely, graphical zonotopes are generalized permutahedra, and hence are associated to faces of the submodular cone. We give a triangulation of these faces for graphs without induced complete sub-graph on 4 vertices. This grants us access to the rays of these faces: Minkowski indecomposable deformations of these graphical zonotopes are segments and triangles. Besides, computer experiments lead to examples of graphs without induced complete sub-graph on 5 vertices, whose graphical zonotopes have high dimensional Minkowski indecomposable deformations.
3 | Deformation cones of hypergraphic polytopes | 2022 | Arnau Padrol, Vincent Pilaud, Germain Poullot | HAL | Published FPSAC 86B | BibTeX |
Abstract: A hypergraphic polytope is a Minkowski sum of faces of the standard simplex. We study deformations of two fundamental families of hypergraphic polytopes: the graphical zonotopes and the nestohedra. Namely, we provide irredundant facet descriptions for the deformation cones of these polytopes. Moreover, we show that the faces of the standard simplex contained in the deformation cone provide a linear basis of its vector span, a result that extends to any hypergraphic polytope.
2 | Deformed graphical zonotopes | 2021 | Arnau Padrol, Vincent Pilaud, Germain Poullot | ArXiv | Published DCG | BibTeX |
Abstract: We study deformations of graphical zonotopes. Deformations of the classical permutahedron (which is the graphical zonotope of the complete graph) have been intensively studied in recent years under the name of generalized permutahedra. We provide an irredundant description of the deformation cone of the graphical zonotope associated to a graph G, consisting of independent equations defining its linear span (in terms of non-cliques of G) and of the inequalities defining its facets (in terms of common neighbors of neighbors in G). In particular, we deduce that the faces of the standard simplex corresponding to induced cliques in G form a linear basis of the deformation cone, and that the deformation cone is simplicial if and only if G is triangle-free.
1 | Deformation cones of graph associahedra and nestohedra | 2021 | Arnau Padrol, Vincent Pilaud, Germain Poullot | ArXiv | Published EJC | BibTeX |
Abstract: We give the facet description of the deformation cones of graph associahedra and nestohedra, generalizing the classical parametrization of the family of deformed permutahedra by the cone of submodular functions. When the underlying building set is made of intervals, this leads in particular to the construction of kinematic nestohedra generalizing the kinematic associahedra that recently appeared in the theory of scattering amplitudes.

# Thesis

My Ph.D. thesis was done under the supervision of Arnau Padrol and Vincent Pilaud, at Sorbonne University (Institut Mathématique de Jussieu - Paris Rive Gauche), from October 2020 to October 2023.

You can find here my thesis on Geometric combinatorics of paths and deformations of convex polytopes.

You can find here the slides of my thesis defense (19 October 2023): thesis defense.

# Slides

Fell free to use some of my slides if you need: just make it clear that you have taken them from me.

As I have given each presentation several time, each has evolved over the years. Here are available their last iterations:

Title | Last update | File
--- | --- | ---
Submodular cone: an inductive construction | 2025 | Download
Number of paths per length on polytopes | 2025 | Download
Deformed permutahedra: let's visit the submodular cone | 2025 | Download
Monotone path polytope of hypersimplices Δ(n,2) | 2023 | Download
Pivot polytope of the products of simplices | 2023 | Download
Pivot polytope of cyclic polytopes | 2023 | Download
Deformation cones of nestohedra | 2021 | Download

# Posters

Title | Year | Conference | Poster
--- | --- | --- | ---
Pivot polytopes of products of polytopes | 2025 | PAGCAP (CIRM) | Download
Many rays of the Submodular Cone | 2025 | Closing Conference on Combinatorial Geometries and Geometric Combinatorics | Download
Indecomposable polytopes and rays of the submodular cone | 2025 | FPSAC 2025 | Download
Pivot rule polytope of cyclic polytopes | 2023 | 89th SLC days | Download
Monotone path polytopes of the hypersimplices Δ(n, 2) | 2023 | Journées GDR IM | Download
Deformation cone of hypergraphic polytopes | 2022 | FPSAC 2022 | Download

## BibTeX

×

@article{PadrolPilaudPoullot2023DeformationNestohedra,
title = {Deformation cones of graph associahedra and nestohedra},
journal = {European Journal of Combinatorics},
volume = {107},
pages = {103594},
year = {2023},
issn = {0195-6698},
doi = {https://doi.org/10.1016/j.ejc.2022.103594},
url = {https://www.sciencedirect.com/science/article/pii/S0195669822000907},
author = {Arnau Padrol and Vincent Pilaud and Germain Poullot},
abstract = {We give the facet description of the deformation cones of graph associahedra and nestohedra, generalizing the classical parametrization of the family of deformed permutahedra by the cone of submodular functions. When the underlying building set is made of intervals, this leads in particular to the construction of kinematic nestohedra generalizing the kinematic associahedra that recently appeared in the theory of scattering amplitudes.}
}

## BibTeX

×

@article{PadrolPilaudPoullot2025DeformedGraphicalZonotopes,
AUTHOR = {Padrol, Arnau and Pilaud, Vincent and Poullot, Germain},
TITLE = {Deformed graphical zonotopes},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
VOLUME = {73},
YEAR = {2025},
NUMBER = {2},
PAGES = {447--465},
ISSN = {0179-5376,1432-0444},
MRCLASS = {52B05 (52B11 52B12 52B35)},
MRNUMBER = {4865928},
DOI = {10.1007/s00454-023-00586-x},
URL = {https://doi.org/10.1007/s00454-023-00586-x},
}

## BibTeX

×

@misc{Poullot2025RaysDeformationConesGraphical,
title={Rays of the deformation cones of graphical zonotopes},
author={Germain Poullot},
year={2025},
eprint={2404.02669},
archivePrefix={arXiv},
primaryClass={math.CO},
url={https://arxiv.org/abs/2404.02669},
}

## BibTeX

×

@article{PilaudPoullot2025PivotPolytopesProductsSimplices,
AUTHOR = {Pilaud, Vincent and Poullot, Germain},
TITLE = {Pivot polytopes of products of simplices and shuffles of associahedra},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
YEAR = {2025},
MRCLASS = {52B11 52B12},
DOI = {10.1007/s00454-025-00765-y},
URL = {https://doi.org/10.1007/s00454-025-00765-y},
}

## BibTeX

×

@misc{Poullot2024VerticesMonotonePathPolytopes,
title={Vertices of the monotone path polytopes of hypersimplicies},
author={Germain Poullot},
year={2024},
eprint={2411.14102},
archivePrefix={arXiv},
primaryClass={math.CO},
url={https://arxiv.org/abs/2411.14102},
}

## BibTeX

×

@misc{JuhnkePoullot2025UnimodalityNumberPathsLength,
title={Unimodality of the number of paths per length on polytopes: Examples, counter-examples, and central limit theorem},
author={Martina Juhnke and Germain Poullot},
year={2025},
eprint={2504.20739},
archivePrefix={arXiv},
primaryClass={math.CO},
url={https://arxiv.org/abs/2504.20739},
}

## BibTeX

×

@inproceedings{PadrolPilaudPoullot2022DeformationHypergraphic,
AUTHOR = {Padrol, Arnau and Pilaud, Vincent and Poullot, Germain},
TITLE = {Deformation cones of hypergraphic polytopes},
JOURNAL = {S\'em. Lothar. Combin.},
FJOURNAL = {S\'eminaire Lotharingien de Combinatoire},
VOLUME = {86B},
YEAR = {2022},
PAGES = {Art. 72, 12},
ISSN = {1286-4889},
MRCLASS = {52B05 (05E45 52B12)},
MRNUMBER = {4490913},
}

## BibTeX

×

@misc{CaicedoJuhnkePoullot2025EhrhartNonPositivityUnimodularTriangulations,
title={Ehrhart non-positivity and unimodular triangulations for classes of s-lecture hall simplices},
author={Jhon B. Caicedo and Martina Juhnke and Germain Poullot},
year={2025},
eprint={2508.18890},
archivePrefix={arXiv},
primaryClass={math.CO},
url={https://arxiv.org/abs/2508.18890},
}

## BibTeX

×

@inproceedings{PadrolPoullot2025NewCriteriaIndecomposability,
AUTHOR = {Padrol, Arnau and Poullot, Germain},
TITLE = {New Criteria for Polytope Indecomposability and New Rays of the Submodular Cone},
JOURNAL = {S\'em. Lothar. Combin.},
FJOURNAL = {S\'eminaire Lotharingien de Combinatoire},
VOLUME = {93B},
YEAR = {2025},
PAGES = {Art. 155, 12},
}

## BibTeX

×

@misc{LohoPadrolPoullot2025RaysSubmodularCone,
title={Many rays of the submodular cone},
author={Georg Loho and Arnau Padrol and Germain Poullot},
year={2025},
eprint={2510.03177},
archivePrefix={arXiv},
primaryClass={math.CO},
url={https://arxiv.org/abs/2510.03177},
}