%% if you are submitting an initial manuscript then you should have submission as an option here %% if you are submitting a revised manuscript then you should have revision as an option here %% otherwise options taken by the article class will be accepted \documentclass[submission]{FPSAC2026} %% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc %% note that the class file already loads {amsmath, amsthm, amssymb} %\usepackage[capitalize,nameinlink,noabbrev]{cleveref} \newtheorem{thm}{Theorem} \newtheorem{lem}[thm]{Lemma} \newtheorem{corollary}[thm]{Corollary} \newtheorem{conjecture}[thm]{Conjecture} \newtheorem{example}[thm]{Example} \newtheorem{prop}[thm]{Proposition} \newtheorem{proposition}[thm]{Proposition} \newtheorem{rmk}[thm]{Remark} \theoremstyle{definition} \newtheorem{defn}[thm]{Definition} \newcommand{\rspace}[1]{\mathcal{R}(#1)} \newcommand{\ospace}{\mathcal{R}_{\mathcal{O}}} \newcommand{\MSB}[1]{\textcolor{red}{[MSB: #1]}} \newcommand{\TB}[1]{\textcolor{blue}{[TB: #1]}} \newcommand{\JDL}[1]{\textcolor{green}{[J: #1]}} \newcommand{\bR}{\mathbb{R}} \newcommand{\cA}{{A}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cP}{\mathcal{P}} \def\cF{\mathcal{F}} \def\ba{\mathbf{a}} \def\perm_#1{P(#1)} \def\wperm_#1{P^W(#1)} \def\cS{\mathcal{S}} \DeclareMathOperator{\conv}{conv} %% define your title in the usual way \title[Orbit Realizations]{On Orbit Realizations of Coxeter Permutahedra} %% define your authors in the usual way %% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details %% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author \author[T. Blanton, J. De Loera, M. Sherman-Bennett]{Timothy Blanton \thanks{\href{mailto:trblanton@ucdavis.edu}{trblanton@ucdavis.edu} T. Blanton was partially supported by DMS-2444020, DMS-2348578, and DMS-2434665}\addressmark{1} \and Jes\'us A. De Loera \thanks{\href{mailto:jadeloera@ucdavis.edu}{jadeloera@ucdavis.edu} J. De Loera was partially supported by DMS-2348578 and DMS-2434665}\addressmark{1} \and Melissa Sherman-Bennett \thanks{\href{mailto:mshermanbennett@ucdavis.edu}{mshermanbennett@ucdavis.edu} M. Sherman-Bennett was partially supported by DMS-2444020} \addressmark{1}} %% then use \addressmark to match authors to institutions here \address{\addressmark{1}Department of Mathematics, University of California Davis} %% put the date of submission here \received{\today} %% leave this blank until submitting a revised version %\revised{} %% put your English abstract here, or comment this out if you don't have one yet %% please don't use custom commands in your abstract / resume, as these will be displayed online %% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year) \abstract{The permutahedron is a fundamental polytope associated with the symmetric group and serves as a central example of the interaction between geometry, combinatorics, and algebra. More generally, for $W$ a finite reflection group, one can define the $W$-permutahedron. In this work, we study the \emph{orbit realizations} of the $W$-permutahedron, which are obtained by taking the convex hull of the $W$-orbit of any point in the fundamental chamber. Although all orbit realizations have the same normal fan, they do not have the same geometric structure. We show that the orbit realization space of the $W$-permutahedron is contractible. We also explore whether various geometric and combinatorial features persist among all orbit realizations. In particular, we show that certain subsets of vertices always form simplices, and some triangulations similarly persist. We experimentally explore the cases of $S_3$ and $S_4$ and we uncover some non-persistent phenomena. Our results suggest a rich internal structure within orbit realization spaces, motivating further study of their topology and combinatorial geometry.} %% put your French abstract here, or comment this out if you don't have one % \resume{\lipsum[2]} %% put your keywords here, or comment this out if you don't have them yet \keywords{permutahedron, realization space, triangulation, oriented matroid} %% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier %% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text %% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex %% but you can use bibtex if you want \usepackage[backend=bibtex]{biblatex} \usepackage{subcaption} \addbibresource{sample.bib} %% note the \printbibliography command at the end of the file which goes with these biblatex commands \articlenumber{103} \begin{document} \maketitle %% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above % \begin{itemize} % \item Add content about persistent triangulations/simplices: refer to Defant--Sherman-Bennett--Williams Proposition 3.3, which implies e.g. that any triangulation consisting of persistent simplices is persistent. Could also mention that a class of persistent simplices can be obtained from the Bruhat graph (the vertices form a tree in the Bruhat graph, and the edge labels give a spanning tree of the complete graph). Melissa can add the details about the Bruhat graph if needed. % \item Complete bibliography % \item Distinguish btw realization space and orbit realization space, give figures to illustrate % \item Update statements to general Coxeter permutahedra where possible (including about orbit realization space) % \item Add figures to illustrate e.g. different chirotopes % \item Deal with ``up to affine transformations" in the orbit realization space % \end{itemize} \section{Introduction} % The permutahedron is a central object in algebraic combinatorics. In this note we start a systematic investigation of its geometric realizations. The permutahedron is a classical polytope associated with the symmetric group, first studied by Schoute in 1911 \cite{Schoute1911}. Its vertices are labeled bijectively by the elements of $S_n$ and its geometry reflects the combinatorics of $S_n$. Its one-skeleton is the Hasse diagram of the weak order. Its face lattice is isomorphic to the lattice of cosets of parabolic subgroups (ordered by inclusion), or equivalently, to ordered block partitions of $[n]$ (ordered by coarsening). The best known realization of the permutahedron is the convex hull of all permutation vectors $\{(w(1), \dots, w(n)): w \in S_n\}$, which we call the \emph{regular permutahedron}. This polytope has a myriad of interpretations and connections to other objects in algebraic and geometric combinatorics. The regular permutahedron is the graphical zonotope associated to the complete graph, as well as the secondary polytope of a simplicial prism \cite{DLRS10}. There is also a canonical surjection from the Birkhoff polytope (the convex hull of permutation matrices) to the regular permutahedron, reflecting the projection from matrix space to coordinate permutations. The normal fan of the regular permutahedron is the famous braid arrangement, providing a connection to Coxeter groups and algebraic geometry. For instance, \cite{DeConciniProcesi1995} constructs the permutohedral variety – the toric variety whose fan is the braid arrangement. %Since then, it has become a central example of the interplay between geometry, combinatorics, and algebraic structures. There are many other realizations of the permutahedron besides the regular permutahedron. Recall that the \emph{realization space} $\mathcal{R}(P)$ of a $d$-dimensional polytope $P$ with vertex set $V$ is a semi-algebraic set inside $(\bR^d)^{|V|}$ defined by the face lattice of the polytope and describing all coordinate configurations of $V$ that preserve the combinatorial incidence relations of $P$ (see \cite{Bjorneretal1999, RichterGebert96} for formal definitions). The entire $\mathcal{R}(P)$ is a mysterious, difficult object even for familiar polytopes. However, as we know the face lattice of the permutahedron is invariant under the $S_n$-action so it is natural to restrict one's attention to realizations which are also preserved by the $S_n$-action. In this paper, we investigate such realizations of the permutahedron, called the \emph{orbit permutahedra}, and we denote by $\ospace$ the set of all orbit permutahedra, which we call the \emph{orbit realization space}. It is a proper subset of the realization space $\rspace{P}$. Concretely, for $\ba\in\mathbb{R}^n$ with strictly increasing coordinates, the \emph{orbit permutahedron} $\perm_\ba$ is the convex hull of the $n!$ points obtained by permuting the coordinates of $\ba$. The normal fan of an orbit permutahedron is again the braid arrangement. Their facet inequalities are described by a classical result of Rado \cite{Rado52}. The volume and Ehrhart polynomial of orbit permutahedra were studied in the beautiful work of Postnikov~\cite{Post09}. Other combinatorial properties are described in \cite{Pons2023}. More generally, one may replace $S_n$ by an arbitrary finite reflection group $W$, the braid arrangement by the hyperplane arrangement $H^W$ for $W$, and define the \emph{orbit $W$-permutahedron} in exactly the same way: for any base point $\ba$ in the fundamental chamber $B$ of $H^W$, $\wperm_\ba:= \conv (W \cdot \ba)$. The \emph{orbit realization space} $\ospace^W$ of $W$-permutahedra consists exactly of $\{\wperm_\ba: \ba \in B\}$. The main focus of our work is $\ospace^W$. For more details on $H^W$ and $\wperm_\ba$ see \cite{BjornerBrenti05,Humphreys90}. %with strictly increasing coordinates and taking the convex hull of all $n!$ points obtained by permuting its coordinates. The resulting polytope, which we will refer to as an \emph{orbit} permutahedron, encodes rich combinatorial structure; we refer the reader to Postnikov’s work~\cite{Post09} for a detailed treatment as well as explanations for many of the results. %Each vertex of the permutahedron corresponds naturally to an element of the symmetric group $S_n$, and its face lattice reflects the parabolic subgroup structure of $S_n$. A classical result of Rado (1952) \cite{Rado52} provides an explicit description of facet-defining inequalities, providing bijections between the permutahedron and certain algebraic structures. In particular, faces are in bijection with cosets of parabolic subgroups which can also be represented as ordered block partitions of $[n]$. %From a geometric viewpoint, the regular permutahedron which is constructed from the orbit of the vector $(1,2,3,\dots,n)$ is a zonotope, in fact the graphical zonotope associated with the complete graph $K_n$. More general orbit permutahedra, however, lose this property and need not be zonotopes. The normal fan of the permutahedron is the braid arrangement, linking its geometry closely to hyperplane arrangements and Coxeter theory. Moreover, the regular permutahedron can be viewed as the secondary polytope of a simplicial prism, situating it within the theory of polyhedral subdivisions. %There are also intriguing algebraic and enumerative connections. There exists a canonical surjection from the Birkhoff polytope, the convex hull of permutation matrices, to the permutahedron, reflecting the projection from matrix space to coordinate permutations. Additionally, Postnikov provides explicit volume formulas for orbit permutahedra, illustrating the deep combinatorial structure underlying its geometry. % History prior work Rado equations of the permutahedron.\cite{greenwade93} %Now, given a convex polytope $P \subset \mathbb{R}^d$, the \emph{realization space} of $P$ (denoted $\mathcal{R}(P)$) is the set of all convex polytopes $P’ \subset \mathbb{R}^d$ that are combinatorially equivalent to $P$ (i.e., have the same face lattice), modulo projective or affine transformations. The orbit realization space $\ospace^W$ is the key object of study of this paper and we list now our contributions: While we do not know the topology of $\mathcal{R}(\wperm_\ba)$, in \cref{thm:realization-space} we show that the orbit realization space $\ospace^W$ of the $W$-permutahedron is homeomorphic to an open ball. This opens up the possibility of studying orbit permutahedra via continuous deformation arguments. We also explore geometric properties of $\wperm_\ba$ that hold regardless of the choice of $\ba$. We focus specifically on triangulations, oriented matroids, and related properties, with an eye towards determining structures which ``persist" for all choices of base point $\ba$. Our initial motivation was \cite[Theorem 1.5]{DSBW25}, which provided many triangulations of $\wperm_\ba$ that persist for all choices of $\ba$. This leads to a number of natural questions we explore: Which triangulations of $\wperm_\ba$ remain triangulations as we move the base point? Given $S \subset W$ of size $d+1$, when is $\conv(S \cdot \ba)$ a simplex for all choices of $\ba$? What can be said about the \emph{oriented matroid} (see \cite{Bjorneretal1999}) of $\wperm_\ba$ over different choices of $\ba$? % --------------{\bf TIMOTHY LET US START THE LIST See WHAT I WROTE BELOW} % \MSB{Please add/tweak to tailor to the results we actually include! Also may be reasonable to mention chirotope/oriented matroid here?} % \JDL{Timothy can you do the list of all results we do include here? In particular I think we forgot to say anything about your enumeration of Oriented matroids you found among orbit realizations.} The answers to questions of this flavor prove to be quite subtle; We begin with Section \ref{warmup} where we explore the permutahedra for $S_3$ and $S_4$. This is an experimental investigation of what is preserved or persists under different choices of $\ba$, we show a number of interesting phenomena, including a count on the number of oriented matroids. Next, in Section \ref{sec:realization} we discuss the contractibility of the orbit realization space, showing that for orbit realizations the space is homeomorphic to an open cone. In Section \ref{persist} we give a sufficient and necessary condition for a triangulation to persist, as well as sufficient conditions on persistent simplices and persistently coplanar sets in relation to subsets that are related by transpositions. In Section \ref{nonpersist} we show that for generic $\ba$, the set of $\ba$ simplices (and thus the associated matroid) is constant, however, we also demonstrate that the oriented matroid is not constant for generic $\ba$. Finally, in Section \ref{future} we propose open questions on several topics: properties of the realization spaces of the permutahedron, persistent simplices, persistently coplanar sets, persistent hyperplanes, and persistent triangulations. %Understanding these spaces is important in polyhedral combinatorics, as it links combinatorial types of polytopes to their possible geometric realizations. For example, a trivial case: if $P$ is a polygon, $\mathcal{R}(P)$ is essentially a single point (all convex $n$-gons are projectively equivalent). In higher dimensions, however, realization spaces can be non-trivial and even extremely complicated. Indeed, in a breakthrough result, N. Mnëv \cite{Mnev88} proved that realization spaces of convex polytopes (indeed, of oriented matroids; see below) %can be as complicated as \emph{any} semialgebraic set. %More precisely, for every primary semialgebraic set $V$ defined over the integers, there exists a (sufficiently high-dimensional) convex polytope $P$ whose realization space $\mathcal{R}(P)$ is “stably equivalent” (in homotopy type, and rationally equivalent) to $V$. In particular, questions about solutions to polynomial equations over $\mathbb{R}$ can be encoded as instances of polytope realization problems. Later work by J. Richter-Gebert \cite{RichterGebertZiegler95,RichterGebert96,RichterGebert99} greatly strengthened the universality phenomenon by showing it already occurs in 4-dimensional polytopes. This is in contrast to the fact that 3-dimensional polytopes have contractible realization spaces. % {\bf EXPLAIN ORBIT REALizATIONS TIMOTHY! MAKE CLEAR THEY ARE A SUBSET OF ALL} %Within full realization space of permutahedra, a natural subset to consider is that of \emph{orbit realizations}. That is, those obtained by fixing some finite Coxeter group (classically the symmetric group $S_n$) and acting on points within a chosen fundamental chamber. Each such vector produces a polytope which is combinatorially equivalent to any other choice, but with potentially distinct geometric and algebraic properties. This defines a proper subset $\ospace$ within $\rspace{P}$ with a well established combinatorial definition. %{\bf Our contributions:} The goal of this project is to investigate the realizations of permutahedra. We focus and obtain results about the orbit realizations which come directly from taking a Coxeter group action on different points. As motivation and illustration of our results in Section \ref{warmup} we look at all realizations for n=3,4. The natural question is what properties or structures remain intact, or persistent, across different orbit realizations. In Section \ref{persist} we look at persistent properties, and in %Section \ref{nonpersist} non-persistent properties. We end with some open problems and future work \ref{future}. % \subsection{Our Contributions} % Motivated by questions the third author posed, we look at the persistence of triangulations for various orbit permutahedra. Along the way, we investigate other objects commonly associated to polytopes. % In this work, we look at how choosing different orbit realizations can change the geometry underlying the permutahedra. In section $2$, we give complete characterizations of the orbit realization space for type $A_2$ and $A_3$. Using this, we describe for which choices of point in $\mathbb{R}^n$ certain sets of points are coplaner. We also discuss some combinatorial permutahedron that are not isomorphic to any orbit realizations and thus must necessarily live outside of our classification scheme. % In section $3$, we look at nice constructions that work for all orbit permutahedra. Specifically, we show that % \begin{thm} % The realization space of orbit realizations for Coxeter permutahedra is contractible and thus connected. % \end{thm} % This tells us that at least for orbit realizations, the realization space is relatively nice. % As we are interested in looking at triangulations, we provide some results on simplicies. Specifically that % \begin{thm*} % The space where $n$ points form a simplex is either dense or empty. % \end{thm*} % In section $4$, we look at triangulations of the permutahedron and how they change under various orbit realizations. We show that, starting with $n=4$ in type $A$, different orbit realizations of the permutahedron can have different triangulations. We also show that no orbit permutahedron consists of just common triangulations, that is, there is not realization whose triangulations will necessarily exist for any other choice of orbit point. % On the dual side to triangulations and simplicies, we show that just because a hyperplane defined by $n-1$ is parallel to a facet does not mean it will continue to remain parallel. % In section $5$, we discuss our future work, specifically some conjectures about commonly shared "never simplicies", as well as other questions involving different realizations and which triangulations are persistent. \section{Definitions and warmup} \label{warmup} As in the introduction, $W$ is a finite reflection group with $d$ simple reflections and $B$ is the fundamental chamber of the associated hyperplane arrangement. We always identify the vertices of $\wperm_\ba$ with $W$, so that the vertices of $\wperm_\ba$ and $\wperm_{\ba'}$ are in natural correspondence and it makes sense to talk about structure ``persisting" for different choices of base point. To streamline notation, we introduce the following. \begin{defn} For $\cS \subset W$ of size $d+1$ and $\ba \in B$, $\cS$ is an \emph{$\ba$-simplex} if $\conv(\cS \cdot \ba)$ is a $d$-dimensional simplex and is $\ba$-coplanar otherwise. A collection $\{\cS_i\}_{i=1}^p$ of $\ba$-simplices is called an \emph{$\ba$-triangulation} if $\{\conv(\cS_i \cdot \ba )\}_{i=1}^p$ is a triangulation of $\wperm_\ba$. That is, $\wperm_\ba = \cup_{i} \conv(\cS_i \cdot \ba)$ and for all $i,j$, $\conv(\cS_i \cdot \ba)$ and $\conv(\cS_j \cdot \ba)$ intersect in a common face (possibly empty). \end{defn} We note that the set of $\ba$-simplices is exactly the set of bases of the \emph{matroid} of $\wperm_\ba$. As we shall see in subsequent sections, the set of $\ba$-simplices and of $\ba$-triangulations is heavily dependent on the choice of $\ba$. So we are more interested in the following notion. \begin{defn} We say that $\cS \subset W$ of size $d +1$ is a \emph{persistent simplex} (respectively, is \emph{persistently coplanar}) if it is an $\ba$-simplex for every choice of $\ba \in B$ (respectively, is $\ba$-coplanar for all $\ba \in B$). A collection $\{\cS_i\}$ of persistent simplices is a \emph{persistent triangulation} if $\{\cS_i\}$ is an $\ba$-triangulation for each $\ba \in B$. \end{defn} Through several examples we illustrate these concepts in the next two subsections. %We note that for an arbitrary polytope $P$, determining which simplices or triangulations ``persist" after a small deformation of the vertices of $P$ is subtle, even if the deformation preserves %We start by looking at orbit permutahedra for $S_3$ (respectively $S_4$), which are 2-dimensional polytopes in $\bR^3$ (respectively, 3-dimensional in $\bR^4$). \subsection{The $S_3$ case} For $W=S_3$ orbit permutahedra, the fundamental chamber $B$ consists of vectors with strictly increasing coordinates. For $\ba = (a_1, a_2, a_3) \in B$, $\perm_\ba$ lies in the hyperplane $\{x_1+x_2+x_3=a_1 + a_2 + a_3 \}$ and is a hexagon that is invariant under permuting coordinates. All 3-element subsets $\cS \subset S_3$ are persistent simplices. In addition, all triangulations are persistent. %look at positive increasing vectors in $\mathbb{R}^3$, specifically we look at $v\in\{0t_0$, the vertex lies on the other side of the hyperplane $H_t$. Perturbing our path slightly if necessary, we can assume that for $t\in [t_0 - \epsilon, t_0 + \epsilon]$, $\ba(t)$ is generic in the sense of Proposition~\ref{prop:generic-simplices}, and that the only simplex which collapses for $\ba(t_0)$ is $\Delta(t_0)$. For $t \in [t_0 - \epsilon, t_0)$, $\cS$ is part of some $\ba(t)$-triangulation $\{\cS_i\}$ (for example, there is a regular triangulation of $\wperm_{\ba(t)}$ that includes $\Delta(t)$). As such, the hyperplane $H_t$ intersects $\Delta(t)$ and another simplex, say $\conv(\cS_1 \cdot \ba(t))$ in a common facet. This means that $\{\cS_i\}$ cannot be an $\ba(t)$-triangulation for $t \in (t_0, t_0 + \epsilon]$, because for those $t$, $\Delta(t)$ and $\conv(\cS_1 \cdot \ba(t))$ have intersecting interiors. \begin{figure}[h] \centering \begin{subfigure}[b]{0.46\textwidth} \centering \includegraphics[height=0.75\linewidth]{Pictures/(1236).png} \caption{$(1,2,3,6)$} \end{subfigure} \begin{subfigure}[b]{0.46\textwidth} \centering \includegraphics[height=0.75\linewidth]{Pictures/(1567).png} \caption{$(1,5,6,7)$} \end{subfigure} % \includegraphics[width=0.5\linewidth]{FPSAC/Pictures/perm_4_101714-753589-861628-925275.png} \caption{The convex hull of $\{(1234), (1324), (2143), (3142)\} \cdot \ba$ in two different orbit permutahedra. Note how the simplex has negative volume in (a) and positive volume in (b).} \label{fig:changesign} \end{figure} % \subsection{Triangulations} % We are now prepared to analyze triangulations, motivated by the questions at the end of $3.2$ \MSB{If you want to refer back to them, they should go in an environment so the reader can find them}. Our first question is if we can find a set of $n$ permutations which is full dimensional \MSB{What?} for one orbit realization but not another. % Since the oriented matroid of a permutahedron is defined by the signed volumes of all subsets of size $n$, the oriented matroids of $(101714,753589,861628,925275)$ and $(1,2,3,4)$ can not be isomorphic. We thus have: % % \begin{rmk} % % The oriented matroid of an orbit permutahedron is not determined by its Coxeter group and dimension. % % \end{rmk} % Since for every simplex one can construct a regular triangulation, this directly implies that the sets of triangulations can not be isomorphic. % We can further eliminate the other two possibilities from section 3. % \begin{example} % Let $S=\{(1,2,3,4), (1, 3, 4, 2), (2, 4, 3, 1), (3, 4, 1, 2)\}$. Then the signed volume of $S$ for the orbit permutahedron associated to $(1,2,3,6)$ has positive volume while the one associated to $(1,5,6,7)$ has negative volume. \MSB{Can we include a figure here?} % \end{example} % Another natural question one can ask is if there is some "minimal orbit realization", that is, an orbit realization whose triangulations are also triangulations for any other orbit realization. This is unfortunately not the case. For type $\cA_{3}$, there is no orbit realization such that every set of $4$ points that can be coplaner is coplanar. % While all of the results in this section rely on computations for $\cA_3$, they can be extended to type $\cA_n$ for all $n\geq 3$. This follows from the fact that type $\cA_n$ permutahedra have a type $\cA_{n-1}$ permutahedron as a facet, and triangulations can be extended by adding some other point not in the facet to each simplex. \section{Future Work and Conjectures} \label{future} There are a couple of further questions that we plan to explore next: \subsection{More on the Realization Spaces} One can weaken the restriction of the realizations from coming from just orbit realizations to those of a combinatorial permutahedron. Not much work has been done on the contractibility or connectivity of these spaces, nor has much work been done on different ways to realize the permutahedron through other methods. This leads to several questions: \begin{itemize} \item Orbit realization of permutahedra are parametrized by elements of the fundamental chamber of finite reflection groups. What objects, if any, parametrize combinatorial permutahedra? % What other objects index combinatorial permutahedron? \MSB{I don't understand what this means} \item Is there a uniform method to produce all realizations of the permutahedron up to some kind of equivalence (affine, projective, normal, etc.)? % Is there a classification that realizes all combinatorial permutahedron? \MSB{Do you mean "is there a uniform method to produce all realizations of the permutahedron?" I don't know if this is a reasonable question unless you say ``up to some kind of equivalence". If you use normal equivalence, you're asking about classifying the rays of the submodular fan, I think.} \item Is the realization space of the permutahedron contractible or connected? More generally, what is its topology? \end{itemize} \subsection{Persistence} % \MSB{Timothy will edit in light of Propositions~\ref{prop:bruhat-graph-persistent-simplices} and \ref{prop:transposition-connected-persistence-classification}} As we described in Proposition~\ref{prop:bruhat-graph-persistent-simplices}, one class of persistent simplices are those determined by their transpositions. These represent a fraction of total persistent simplices as we explicitly compute for $S_4$ in Proposition~\ref{prop:s4-classification}. This leads to the following questions: Is there a classification of all the persistent simplices in type A? Is there one that extends naturally to all types? The dual question of which sets are persistently coplanar is also of interest. Proposition~\ref{prop:coplanar-sufficient-cond} gives a sufficient condition for $\cS \subset S_n$ to be persistently nonplanar. This condition is also necessary for $n=4$, but is not necessary for $n=5$. Adding in a couple more conditions gives us the following conjectural characterization of persistently coplanar sets. % As in Proposition~\ref{prop:bruhat-graph-persistent-simplices}, let $\cS\subset S_n$ that has size $n$ and consider the graph $G$ on $\cS$ with edge set % \[\{\{v, w\}: v, w \in \cS \text{ and } vw^{-1} \text{ is a transposition}\}\] % Now, consider the subgraphs of $G$ which are forests. If the roots \[D=\{e_i-e_j:v=(ij)w \text{ for some }\{v,w\}\in\cF\}\] % are linearly dependent for some choice of forest $\cF$, then $\cS$ is a persistently coplanar set. % This is a relaxation of the conditions in Proposition~\ref{prop:transposition-connected-persistence-classification} as it no longer requires $\cS$ to be transposition-connected (equivalently, $G$ to be connected). %The subsets of $S_n$ described above are exactly the persistently coplanar sets for $n=4$ but are only a subset of the persistently coplanar sets for $n=5$. Adding in a couple more conditions gives us the following conjecture: %One class of simplex that is known to persist is that governed by root directions which are in bijection with transpositions. Simply put, if the set of indices in the root directions form a spanning tree of the graph $K_n$, then the points will always form a simplex. A similar result is possible for the negation, that is, if the set of root directions is affinely dependent, then the points will never form a simplex. This classification of always persistent simplices fails to account for all of them, even in the $n=4$ case, but the never simplex classification is complete for $n=4$. For $n=5$, however, new behavior is introduced that requires additional classes: \begin{conjecture} %\MSB{Timothy will rephrase this using the current notation} Let $\cS\subset S_n$ have size $n$, $T$ be as in Proposition~\ref{prop:bruhat-graph-persistent-simplices}, and $G_\cS$ be as in Proposition~\ref{prop:coplanar-sufficient-cond}. Then $\cS$ is a persistently coplanar set if and only if it satisfies one of the following: \begin{itemize} \item There is a forest $F \subset G_\cS$ such that the associated transposition graph $T_F$ is not a forest; %\item There is a $\cF\subset \cS$ such that $\cF$ has linearly dependent differences $D$ \item There are $d$ elements of $\cS$ contained in a parabolic subgroup generated by $d-2$ simple transpositions %given by removing $n+1-d= n-1-(d-2)$ simple transpositions \item Viewing the elements of $T$ as transpositions, for some subset $T'\subseteq T$ of size at least 2 consisting of commuting transpositions, there is some $v,w\in \cS$ such that $vw^{-1}=\prod_{\sigma\in T'} \sigma$ \item There are four distinct elements, $v,w,x,y\in \cS$, such that $vw^{-1}=\sigma$, $vx^{-1}=\tau$, and $vy^{-1}=\sigma \tau$ where $\sigma$ and $\tau$ are two commuting permutations. % \MSB{Again, better to say ``$\sigma, \tau$ commute" or something. Were there any conditions on what $\sigma, \tau$ are? E.g. are they cycles?} \end{itemize} \end{conjecture} %Currently, a counter-example to the classification seems likely but one has not been found. \MSB{If we don't think the conjecture is true, we shouldn't include it.} %\subsection{Persistent Hyperplanes and Triangulations} A similar style of problem one can ask is which hyperplanes persist under different choices of orbits? One obvious example of a persistent family of hyperplanes are the facet-defining hyperplanes of orbit permutahedra (they only depend on the combinatorics). But finding persistent families seems tricky. For example, we discovered (inner) hyperplanes parallel to facets are not necessarily preserved under varying choice of basepoint. This family is interesting as it contains the Duistermaat--Heckman hyperplanes (see \cite{Rassart04} and references there). Note that just like the study of persistent simplices ties in with the bases of the oriented matroid defined by the vertices of the permutahedron, the persistent hyperplanes are related to the covectors and cocircuits of the same oriented matroid. It is known that two point configurations with the same oriented matroid will have the same set of triangulations \cite{DLRS10}, and some classes of triangulations are known to depend only on the combinatorial type of a polytope, the main class being lexicographic triangulations. We have the following conjecture: \begin{conjecture} The persistent triangulations of the permutahedron are exactly its lexicographic triangulations. \end{conjecture} % If this conjecture is not true, it leads to the following natural question: % \begin{itemize} % \item Are there any triangulations that only persist for the orbit permutahedron? % \item What other classes of triangulations persist based on just the face lattice? % \end{itemize} %\acknowledgements{} %% if you use biblatex then this generates the bibliography %% if you use some other method then remove this and do it your own way \printbibliography \end{document}