%% 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[finalversion]{FPSAC2025}
\articlenumber{19}
%% 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}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\usepackage{float}
\usepackage{lipsum}
\usepackage{mathtools}
\usepackage{tikz}
\usetikzlibrary{calc,decorations.markings,arrows.meta}
\usepackage{tkz-graph}
\usepackage{tikz-cd}
\usepackage[dvipsnames]{xcolor}
\usepackage{caption}
\usepackage{graphicx}
\newcommand{\colorD}{NavyBlue}
\newcommand{\colorA}{Orchid}
\newcommand{\colorC}{JungleGreen}
\newcommand{\colorB}{Tan}
\newcommand{\colorE}{gray}
\newcommand{\sw}{\textcolor{cyan}}
\newcommand{\colorF}{Brown}
\newcommand{\colorG}{Cerulean}
\newcommand{\colorH}{CadetBlue}
\newcommand{\colorI}{NavyBlue}

\allowdisplaybreaks[3]
%% define your title in the usual way
\title[Newton polytopes of dual Schubert polynomials]{Newton polytopes of dual Schubert polynomials}

%% 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[An, Tung, and Zhang]{\texorpdfstring{Serena An \thanks{\href{mailto:anser@mit.edu}{anser@mit.edu}.}\addressmark{1}, Katherine Tung\thanks{\href{mailto:katherinetung@college.harvard.edu}{katherinetung@college.harvard.edu}.}\addressmark{2}, \and Yuchong Zhang\thanks{\href{mailto:zongxun@umich.edu}{zongxun@umich.edu}.\\
All authors were supported by the UMN Combinatorics and Algebra REU, NSF grant DMS-2053288, and the D.E.\ Shaw group.}\addressmark{3}}{Serena An , Katherine Tung, and Yuchong Zhang}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139 \\ \addressmark{2}Department of Mathematics, Harvard University, Cambridge, MA 02138 \\ \addressmark{3}Department of Mathematics, University of Michigan, Ann Arbor, MI 48104}

%% 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 M-convexity of the support of dual Schubert polynomials was first proven by Huh, Matherne, M\'esz\'aros, and St.\ Dizier in 2022. We give a full characterization of the support of dual Schubert polynomials, which yields an elementary alternative proof of the M-convexity result, and furthermore strengthens it by explicitly characterizing the vertices of their Newton polytopes combinatorially. Using this characterization, we give a polynomial-time algorithm to determine if a coefficient of a dual Schubert polynomial is zero, analogous to a result of Adve, Robichaux, and Yong for Schubert polynomials.
}

%% 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{dual Schubert polynomial, saturated Newton polytope, generalized permutahedron, M-convex}

%% 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, giveninits]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands


\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}

\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\ZZZ}{\mathbb{Z}_{\ge 0}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\B}{\mathcal{B}}

\newcommand{\N}{\mathbb{N}}
\newcommand{\YY}{\mathbb{Y}}
\newcommand{\T}{\mathrm{T}}
\newcommand{\call}{\mathcal{L}}
\newcommand{\calr}{\mathcal{R}}
\newcommand{\V}{\mathcal{V}}

\newcommand{\G}{\mathcal{G}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\Hh}{\mathbb{H}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\RP}{\mathbb{RP}}
\newcommand{\Oh}{\mathcal{O}}

\newcommand{\la}{\mathbf{a}}
\newcommand{\lgl}{\mathfrak{gl}}
\newcommand{\lsl}{\mathfrak{sl}}
\newcommand{\lieg}{\mathfrak{g}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\q}{\mathfrak{q}}
\newcommand{\m}{\mathfrak{m}}
\newcommand{\mfS}{\mathfrak{S}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\Mod}{\mathrm{Mod}}
\newcommand{\Mor}{\mathrm{Mor}}
\newcommand{\Proj}{\mathrm{Proj}}
\newcommand{\Hom}{\mathrm{Hom}}
\newcommand{\obj}{\mathrm{obj}}
\newcommand{\im}{\mathrm{im}}
\newcommand{\colim}{\mathrm{colim}}
\newcommand{\res}{\mathrm{res}}
\newcommand{\Spec}{\text{Spec }}
\newcommand{\Supp}{\text{Supp }}
\newcommand{\Ann}{\text{Ann }}
\newcommand{\Pic}{\text{Pic }}
\newcommand{\Isom}{\mathrm{Isom}}
\newcommand{\Des}{\mathrm{Des}}

\newcommand{\Newton}{\mathrm{Newton}}
\newcommand{\conv}{\mathrm{conv}}
\newcommand{\Inv}{\mathrm{Inv}}
\newcommand{\GW}{\mathrm{GW}}
\newcommand{\Mon}{\mathrm{Mon}}
\newcommand{\Par}{\mathrm{Par}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\Ver}{\mathrm{Ver}}

\usepackage{dsfont}
\newcommand{\1}{\mathds{1}}
\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{example}[theorem]{Example}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{question}[theorem]{Question}
\newtheorem*{remark}{Remark}
\newtheorem*{notation}{Notation}
\begin{document}

\maketitle

\section{Introduction}\label{section:introduction}

Dual Schubert polynomials $\{\mathfrak{D}^w\}_{w\in \mathfrak{S}_n}$, introduced by Bernstein, Gelfand, and Gelfand \cite{BGG}, are given by the following combinatorial formula \cite{PostnikovStanley}. Let the edge $u \lessdot ut_{ab}$ in the (strong) Bruhat order have weight 
\[m(u \lessdot ut_{ab}) \coloneqq x_a + x_{a+1} + \cdots + x_{b-1},\] 
and let the saturated chain $C = (u_0 \lessdot u_1\lessdot\cdots \lessdot u_{\ell})$ have weight 
\[m_C\coloneq m(u_0 \lessdot u_1)m(u_1 \lessdot u_2)\cdots m(u_{\ell - 1} \lessdot u_{\ell}).\]

\begin{definition}\label{def:dualSchubert}
    For $w \in \mathfrak{S}_n$, the \emph{dual Schubert polynomial $\mathfrak{D}^w$} is defined by \[\mathfrak{D}^w(x_1, \dots,x_{n-1}) \coloneqq \frac{1}{\ell(w)!} \sum_C m_C(x_1, \dots,x_{n-1})\] where $\ell(w)$ denotes the Coxeter length of $w$, and the sum is over all saturated chains $C$ from $\id$ to $w$.
\end{definition}

Dual Schubert polynomials possess deep geometric and algebraic properties. For example, the $\lambda$-degree of a Schubert variety $X_w$ can be expressed as $\ell(w)! \cdot \mathfrak{D}^w(\lambda)$ \cite{PostnikovStanley}. In addition, dual Schubert polynomials form a dual basis to Schubert polynomials under a certain natural pairing $\langle \cdot, \cdot \rangle$ on polynomials \cite{PostnikovStanley}. 

In recent years, dual Schubert polynomials have attracted increasing interest \cite{InvolRC, Hamaker,HuhMeszaroLorSchur}. We continue the study of dual Schubert polynomials by fully characterizing their \emph{supports} (set of exponent vectors) and \emph{Newton polytopes} (convex hull of the support).

\begin{theorem}\label{theorem:support}
    The support of the dual Schubert polynomial $\mathfrak{D}^w$ is
    \[\supp (\mathfrak{D}^w)= \sum_{(a,b) \in \Inv(w)}\{e_a, e_{a+1}, \dots, e_{b-1}\},\]
    where the right-hand side is a Minkowski sum of sets of elementary basis vectors. The sum is over pairs of indices $(a, b)$ for which there is an inversion in $w$.
\end{theorem}

Moreover, we show that \Cref{theorem:support} implies a polynomial-time algorithm to determine whether a term lies in the support of a dual Schubert polynomial, analogous to a result of Adve, Robichaux, and Yong \cite{ARY} for Schubert polynomials.

\begin{corollary}\label{thm:vanish}
    Given $w \in \mathfrak{S}_n$ and $\alpha = (c_1, \ldots, c_{n-1}) \in \ZZZ^{n-1}$, there exists an $O(n^5)$ algorithm to determine whether $\alpha \in \supp(\mathfrak{D}^w)$.
\end{corollary}


A polynomial $f$ has a \emph{saturated Newton polytope (SNP)} if its support is all integer points in its Newton polytope. The SNP property was first defined by Monical, Tokcan and Yong \cite{NewtonPolyinAC}. 
Many polynomials with algebraic combinatorial significance are known to have SNP, such as Schur polynomials \cite{Rado}, resultants \cite{GKZ}. 
Monical, Tokcan, and Yong proved SNP for additional families of polynomials, including cycle index polynomials, Reutenauer’s symmetric polynomials linked to the free Lie algebra and to Witt vectors, Stembridge’s symmetric polynomials associated to totally nonnegative matrices, and symmetric Macdonald polynomials. 
Subsequent work of Fink, M\'esz\'aros, and St.\ Dizier proved SNP for key polynomials and Schubert polynomials \cite{FMD}, work of Castillo, Cid Ruiz, Mohammadi, and Monta\~no proved SNP for double Schubert polynomials \cite{CCMM}, and work of Huh, Matherne, M\'esz\'aros, and St.\ Dizier \cite{HuhMeszaroLorSchur} proved Lorentzian-ness, which implies SNP, for dual Schubert polynomials.

Proving SNP can be difficult given that many polynomial operations, such as multiplication, do not preserve SNP. However, a wide range of techniques have been harnessed to prove SNP. For instance, Rado uses elementary combinatorial techniques \cite{Rado}, Fink, M\'esz\'aros, and St.\ Dizier rely on representation theory \cite{FMD}, and Castillo et al.\ as well as Huh et al.\ use results from algebraic geometry \cite{CCMM,HuhMeszaroLorSchur}. 

As a corollary of \Cref{theorem:support}, we obtain an elementary proof of the following result.

\begin{corollary}(cf.\ \cite[Proposition~18]{HuhMeszaroLorSchur})\label{thm:M-conv}
Dual Schubert polynomials have M-convex support; equivalently, they have SNP and their Newton polytopes are generalized permutahedra.
\end{corollary}

Strengthening this result, we fully characterize the vertices of $\Newton(\mathfrak{D}^w)$.

\begin{corollary}\label{thm:DSPNPVert}
    For $w\in \mathfrak{S}_n$, the vertices of $\Newton(\mathfrak{D}^w)$ are
    \[\{\alpha\in\ZZ_{\ge 0}^{n-1} \mid x^{\alpha}\text{ has coefficient }1\text{ in }\prod_{(a,b) \in \Inv(w)} (x_a+x_{a+1}+\dots +x_{b-1})\}.\]
\end{corollary}

Furthermore, in light of \cite[Corollary~8.2]{postnikovpermutohedra}, we give a combinatorial characterization of the vertices of $\Newton(\mathfrak{D}^w)$ using rectangle tilings of staircase Young diagrams.

This paper is organized as follows. In \Cref{section:preliminaries}, we give the necessary relevant background and definitions. In \Cref{section:Mconvexity}, we characterize the support of dual Schubert polynomials. In \Cref{section:vanishing}, we give a polynomial-time algorithm to determine whether a term lies in a 
dual Schubert polynomial. In \Cref{section:vertices}, we characterize the vertices of Newton polytopes of dual Schubert polynomials in two different ways.

This is an extended abstract summarizing our work, and readers are referred to \cite{whole} for a complete version.

\section{Preliminaries}\label{section:preliminaries}
\subsection{Bruhat order}
In this paper, we use standard terminology for the (strong) Bruhat order. The content of this section may be also found in \cite[Chapter~2]{BjornerBrenti}, for example.

Let $\mathfrak{S}_n$ be the symmetric group on the set $[n] \coloneqq \{1, \dots, n\}$. 
We write each permutation $w\in \mathfrak{S}_n$ in one-line notation as $w = w(1)w(2)\cdots w(n)$.

Each permutation $w \in \mathfrak{S}_n$ can be expressed as a product of \emph{simple transpositions} $s_i = \{(i, i+1) : 1\le i\le n-1\}$. If $w = s_{i_1}\cdots s_{i_{\ell}}$ is expressed as a product of simple transpositions with $\ell$ minimal among all such expressions, then the string $s_{i_1}\cdots s_{i_{\ell}}$ is called a \emph{reduced decomposition} of $w$. We call $\ell \coloneqq \ell(w)$ the \emph{(Coxeter) length} of $w$.

An \emph{inversion} of $w$ is an ordered pair $(a,b)\in [n]^2$ such that $a< b$ and $w(a)>w(b)$. We denote the set of all inversions of $w$ by $\Inv(w)$. It is well-known that $\ell(w) = |\Inv(w)|$. 

Given $1\le a < b\le n$, let $t_{ab}$ act on $w\in \mathfrak{S}_n$ such that $wt_{ab}$ is the permutation obtained by transposing the two numbers at positions $a$ and $b$ in $w$.

\begin{definition}(\cite{BjornerBrenti})\label{def:bruhatorder}
    We define a partial order $\le$ on $\mathfrak{S}_n$ called the \emph{strong Bruhat order} as follows. Let $u, v\in \mathfrak{S}_n$ and $\ell = \ell(v)$. 
    We have $u\le v$ if and only if for any reduced decomposition $s_{i_1}\cdots s_{i_{\ell}}$ of $v$, there exists a reduced decomposition $s_{j_1}\cdots s_{j_k}$ of $u$ such that $s_{j_1}\cdots s_{j_k}$ is a substring of $s_{i_1}\cdots s_{i_{\ell}}$. If additionally $\ell(v) = \ell(u) + 1$, we write $u\lessdot v$. Alternatively, we may characterize the covering relation as follows. For $u, v \in \mathfrak{S}_n$, we have $u \lessdot v$ if and only if $v = ut_{ab}$ and $\ell(v) = \ell(u) + 1$.
\end{definition}

For $u\le w$ in the Bruhat order of $\mathfrak{S}_n$, the \emph{(Bruhat) interval} $[u, w]$ is the subposet containing all $v\in \mathfrak{S}_n$ such that $u\le v\le w$. 

\subsection{Postnikov--Stanley polynomials}
We define Postnikov--Stanley polynomials, which generalize dual Schubert polynomials. 

\begin{definition}(\cite{PostnikovStanley})
    Given $u\le w $ in $ \mathfrak{S}_n$, the \emph{Postnikov--Stanley polynomial} $\mathfrak{D}_u^w$ is defined by
    \[\mathfrak{D}_u^w(x_1, \dots, x_{n-1}) \coloneqq \frac{1}{(\ell(w) - \ell(u))!}\sum_{C} m_C(x_1, \dots, x_{n-1}),\]
    where the sum is over all saturated chains $C$ from $u$ to $w$.
\end{definition}
As defined in the introduction, the \emph{dual Schubert polynomial} $\mathfrak{D}^w$ is given by $\mathfrak{D}^w\coloneq \mathfrak{D}_{\id}^w$.
\begin{example}\label{ex:PS}
    In the Bruhat order of $\mathfrak{S}_3$, there are two saturated chains in $[123,321]$, namely $213\lessdot 231\lessdot 321$ and $213\lessdot 312\lessdot 321$. The first chain has weight $x_1x_2$ and the second chain has weight $(x_1 + x_2) \cdot x_2$. Thus, $\mathfrak{D}_{213}^{321} = \frac{1}{2!}(x_1 x_2 + (x_1 + x_2)\cdot x_2)$.
\end{example}

\subsection{Newton polytopes}
Elaborating on our parenthetical definitions in the introduction, we give a full definition of the Newton polytope.
\begin{definition}\label{def:expvector}
    For a tuple $\alpha = (\alpha_1, \dots, \alpha_n)\in \ZZ_{\ge 0}^n$, let $x^\alpha$ denote the monomial 
    \[x^\alpha \coloneqq x_1^{\alpha_1}\cdots x_n^{\alpha_n}\in \R[x_1, \dots, x_n].\]
    We call $\alpha$ the \emph{exponent vector} of $x^{\alpha}$.
\end{definition}
\begin{definition}\label{def:supp}
Let $f = \sum_{\alpha \in \ZZZ^{n}} c_{\alpha} x^{\alpha} \in \R[x_{1}, \ldots, x_{n}]$ be a polynomial. 
    The \emph{support} of $f$, denoted $\supp(f)$, is the set of its {exponent vectors} $\alpha$.
\end{definition}
The support behaves nicely with respect to polynomial addition and multiplication. 
\begin{proposition}\label{prop:suppsumprod}
    For two polynomials $f, g\in\R_{\ge 0}[x_1, \dots, x_n]$, we have \[\supp(fg)=\supp(f)+\supp(g), \qquad \supp(f+g)=\supp(f)\cup\supp(g),\] where $\supp(f)+\supp(g)$ denotes the Minkowski sum of $\supp(f)$ and $\supp(g)$.
\end{proposition}
\begin{definition}\label{def:newton}
    The \emph{Newton polytope} of $f$, denoted $\Newton(f)$, is the convex hull of $\supp(f)$ in $\mathbb{R}^n$.
\end{definition}

\begin{definition}(\cite{NewtonPolyinAC})
    A polynomial $f \in \R[x_1, \dots, x_n]$ is said to have a \emph{saturated Newton polytope (SNP)} if $\supp(f)$ is precisely all integer points in $\Newton(f)$.    
\end{definition}
\begin{example}\label{ex:snp}
    As computed in \Cref{ex:PS}, $\mathfrak{D}_{213}^{321} = x_1x_2+\frac{1}{2}x_2^2$, so its Newton polytope $\Newton(\mathfrak{D}_{213}^{321})$ is the line segment from $(1, 1)$ to $(0, 2)$ in $\R^2$. There are no integer points on this line segment besides the endpoints, so $\mathfrak{D}_{213}^{321}$ has SNP.
\end{example}

\begin{remark}
    A nonexample for SNP is the polynomial
    \[f = x^{(0, 1, 3)} + x^{(0,3,1)} + x^{(1,0,3)} + x^{(1,3,0)} + x^{(3,0,1)} + x^{(3,1,0)},\] 
    because $\Newton(f)$ contains the integer point $(0, 2, 2)$, but there is no $cx^{(0, 2, 2)}$ monomial in $f$ for $c$ nonzero.
\end{remark}


\subsection{Generalized permutahedra} \label{section:matroidpolytopes}

A standard \emph{permutahedron} (or \emph{permutohedron}) is the convex hull in $\R^n$ of the vector $(0, 1, \dots, n-1)$ and all permutations of its entries. \emph{Generalized permutahedra} are deformations of standard permutahedra and are defined as follows.
\begin{definition}(\cite{postnikovpermutohedra})\label{def:gp}
    The \emph{generalized permutahedron} $P_n^z(\{z_I\})$ associated to the collection of real numbers $\{z_I\}$ for $I\subseteq [n]$ is given by
    \[P_n^z(\{z_I\}) \coloneqq \left\{t\in\R^n : \sum_{i\in I} t_i\ge z_I \text{ for } I\neq [n], \sum_{i=1}^n t_i = z_{[n]}\right\}.\]
\end{definition}

\begin{proposition}(\cite{MatroidPolytopes})\label{prop:permutahedraminkowskisum}
    Generalized permutahedra are closed under the Minkowski sum:
    \[P_n^z(\{z_I\}) + P_n^z(\{z_I'\}) = P_n^z(\{z_I + z_I'\}).\]
\end{proposition}

\emph{M-convexity} is a concept closely related to generalized permutahedra.

\begin{definition}(\cite{DicreteConvexAnaly})
A subset $\mathcal{J} \subseteq \ZZZ^n$ is \emph{M-convex} if for any index $i \in [n]$ and any $\alpha ,\beta \in \mathcal{J}$ whose $i$-th coordinates satisfy $\alpha_i > \beta_i$, there is an index $j \in [n]$ satisfying
\[
\alpha_j < \beta_j, \quad \alpha - e_i + e_j \in \mathcal{J},\text{ and} \quad \beta - e_j + e_i \in \mathcal{J}.
\]
\end{definition}
\begin{proposition}(\cite[Theorem 4.15]{DicreteConvexAnaly} and \cite{HuhMeszaroLorSchur})\label{prop:Mconvex=SNP+GP}
    A homogeneous polynomial $f$ has M-convex support if and only if $f$ has SNP and $\Newton(f)$ is a generalized permutahedron.
\end{proposition}

\section{Support of dual Schubert polynomials}\label{section:Mconvexity}
In this section, we prove \Cref{theorem:support} and \Cref{thm:M-conv}. Our key insight is that the support of any dual Schubert polynomial $\mathfrak{D}^w$ always matches the support of the weight of some specific chain in $[\id,w]$. Since it is easy to show each chain weight has SNP and its Newton polytope is a generalized permutahedron, we obtain the desired result.

\subsection{Single-chain Newton polytopes}\label{section:SCNP}
We introduce the single-chain Newton polytope property and show that it implies SNP.

\begin{definition} \label{SCNP}
    Given $u \le w$ in $\mathfrak{S}_n$, the Postnikov--Stanley polynomial $\mathfrak{D}_{u}^w$ is said to have a \emph{single-chain Newton polytope (SCNP)} if there exists a saturated chain $C$ in the interval $[u, w]$ such that
    \[\supp(m_C) = \supp(\mathfrak{D}_u^w).\]
    Such a saturated chain $C$ is called a \emph{dominant chain} of the interval $[u, w]$.
\end{definition}
\begin{example}
    Given the Postnikov--Stanley polynomial $\mathfrak{D}_{213}^{321} = \frac{1}{2!}(x_1 x_2 + (x_1 + x_2)\cdot x_2)$, the saturated chain $C = (213 \lessdot 312 \lessdot 321)$ has weight $m_C = (x_1 + x_2)\cdot x_2$, which satisfies 
    \[\supp(m_C) = \supp(\mathfrak{D}_{213}^{321}).\] 
    Thus, $C$ is a dominant chain of $[213, 321]$ and $\mathfrak{D}_{213}^{321}$ has SCNP. 
\end{example}

The following observation, which can be proved by \cite[Theorem~3.4]{2009minkowski}, motivates our definition of SCNP.

\begin{proposition}\label{prop:linearprodSNP}
    If a polynomial $f\in \R[x_1,x_2,\dots,x_n]$ can be written as a product of nonnegative linear combinations of $x_1, \dots, x_n$, then $f$ has SNP.
\end{proposition}

Since each chain weight is a product of nonnegative linear combinations of variables, we have the following property.

\begin{proposition}\label{prop:SCNPtoSNP}
    If $\mathfrak{D}_u^w$ has SCNP, then $\mathfrak{D}_u^w$ has SNP.
\end{proposition}

\begin{remark}\label{example:13244231}
    The SCNP property is strictly stronger than SNP: for example, $\mathfrak{D}_{1324}^{4231}$ has SNP but not SCNP.
    As Postnikov--Stanley polynomials do not necessarily have SCNP, the method of using SCNP to prove SNP for dual Schubert polynomials does not generalize to Postnikov--Stanley polynomials. 
\end{remark}

For the SCNP property, we have the following conjecture.

\begin{conjecture}
        For $w\in \mathfrak{S}_n$, all $\mathfrak{D}_{u}^w$ have SCNP if and only if $w$ avoids 4231 pattern.
\end{conjecture}

\subsection{Saturated Newton polytopes}\label{subsec:dualschubSCNP}

We prove that dual Schubert polynomials have SCNP and obtain as a corollary that they have SNP. We first describe a ``greedy'' procedure for finding a dominant chain.

\begin{definition}
    In a saturated chain 
    \[u = w_0\lessdot w_1\lessdot w_2\lessdot \dots \lessdot w_{\ell} = w,\] 
    we may express $w_i$ as $w_{i-1}t_{ab}$ for all $i \in [\ell]$. This chain from $u$ to $w$
    is \emph{greedy} if, for all $i$, there does not exist $w'_{i-1}\lessdot w_{i}$ with $w'_{i-1} \in [u,w]$ such that 
    \begin{enumerate}[label=\textnormal{(\roman*)}]
        \item $w_{i}=w'_{i-1}t_{ab'}$ for $b'>b$, or
        \item $w_{i}=w'_{i-1}t_{a'b}$ for $a'<a$.
    \end{enumerate}
\end{definition}

\begin{example}
    In the interval $[123, 321]$, the saturated chain $123 \lessdot 132\lessdot 231 \lessdot 321$ is greedy, while $123 \lessdot 213 \lessdot 231 \lessdot 321$ is not. This latter chain fails to be greedy because $w_2 = 231 = 213t_{23} = w_{1}t_{23},$ but $132 \lessdot w_2$ with $231 = 132t_{13}$, violating condition (ii). In general, greedy chains are not unique. For example, $123 \lessdot 213 \lessdot 312 \lessdot 321$ is another greedy chain in $[123,321]$.
\end{example}

\begin{lemma}\label{lem:existsgreedychain}
    There exists a greedy chain in every interval $[u, w]$. 
\end{lemma}
\begin{proof}[Proof sketch]
    We may build a greedy chain inductively downward from $w$.
\end{proof}

Moreover, we can explicitly compute the weight of a greedy chain from $\id$ to $w$.

\begin{definition}\label{def:globalweight}
    For a permutation $w\in \mathfrak{S}_n$, the \emph{global weight} $\GW(w)$ of $w$ is defined by
    \[\GW(w) \coloneqq \prod_{(a,b) \in \Inv(w)} (x_a+x_{a+1}+\dots +x_{b-1}).\]
\end{definition}

\begin{lemma}\label{lemma:greedy=GW}
    Given $w\in \mathfrak{S}_n$, the weight of any greedy chain in $[\id,w]$ is $\GW(w)$.
\end{lemma}
\begin{proof}[Proof sketch]
    We induct on $\ell(w)$. As part of our inductive step, we show that $\Inv(w_{\ell-1})=\Inv(w)\setminus {(a,b)}$ by performing casework on $\Inv(w_{\ell}) \setminus \Inv(w_{\ell-1})$. 
\end{proof}


Then, we show that for any interval $[\id,w]$, the support of any greedy chain contains the support of any other saturated chain. Equivalently, any saturated chain $C$ in $[\id,w]$ satisfies $\supp(m_C)\subseteq \supp(\GW(w))$. To prove this, we define a pairing that allows us to match up linear factors in $m_C$ with linear factors in $\GW(w)$.

\begin{definition}\label{def:dominant pairing}
    We define a partial order $\preceq$ on $\{(a,b)\in \N^2\mid a<b\}$ such that $(a,b)\preceq (c,d)$ if and only if $[a,b]\subseteq [c,d]$. 

    Given a positive integer $\ell$, we define a partial order $\preceq_{\ell}$ on $\ell$-element multisets in $\{(a,b)\in \N^2\mid a<b\}$ as follows: for two multisets $G$ and $H$, we say $G \preceq_{\ell} H$ if and only if there exists a pairing of elements in $G$ and $H$ such that for each pair $((a_i,b_i),(c_i,d_i))\in G\times H$ in this pairing, we have $(a_i,b_i)\preceq (c_i,d_i)$. We call this pairing \emph{dominant}.
\end{definition}

\begin{definition}
    For a saturated chain $C = (u_0 \lessdot u_1\lessdot\cdots \lessdot u_{\ell})$ in the Bruhat interval $[u_0,u_{\ell}]$ in $\mathfrak{S}_n$,
    we define its \emph{generating set} $G_C$ to be the multiset containing the pairs of the positions $(a_i, b_i)$ swapped along edges in $C$:
    \[G_C \coloneqq \{(a_i,b_i)\in [n]\mid u_{i}=u_{i-1}t_{a_ib_i}, a_i < b_i, i\in[\ell]\}.\]
\end{definition}
\begin{example}\label{ex:Gc}
    For $C = 1234 \lessdot 2134 \lessdot 2143 \lessdot 2413 \lessdot 4213$, the multiset $G_C$ is equal to $\{(1,2),(3,4),(2,3),(1,2)\}$.
\end{example}
\begin{lemma}\label{lemma:chainorder}
    Given a permutation $w\in \mathfrak{S}_n$ with $\ell(w) = \ell$, for every saturated chain \[C=(\id=w_0\lessdot w_1\lessdot w_2\lessdot \dots \lessdot w_{\ell} =w)\] in $[\id, w]$, we have
    $G_C\preceq_{\ell} \Inv(w)$.
\end{lemma}
\begin{proof}[Proof sketch]
    The strategy is similar to that in the proof of \Cref{lemma:greedy=GW}.
\end{proof}
\begin{example}\label{ex:Gc-lemma}
    Continuing \Cref{ex:Gc}, we note that the chain $C$ has top element $w = 4213$ and $\Inv(w) = \{(1,2),(1,3),(1,4),(2,3)\}.$ Write $G_C = \{(1,2),(1,2),(3,4),(2,3)\},$ we can see that pairing the elements of $G_C$ and $\Inv(w)$ in the given order yields a dominant pairing, so $G_C\preceq_{4} \Inv(w)$.
\end{example}

By \Cref{lemma:chainorder}, there exists a dominant pairing $\P$ of $G_C$ and $\Inv(w)$ such that $[a,b]\subseteq [c,d]$ for each pair $((a,b),(c,d))\in \P$, thereby allowing us to pair the linear factors of $m_C$ with the linear factors of $\GW(w)$. We deduce the following lemma.

\begin{lemma}\label{lemma:chaincontainment}
    Given a permutation $w\in \mathfrak{S}_n$, for every saturated chain $C$ in $[\id, w]$, we have $\supp(m_C)\subseteq \supp(\GW(w))$.
\end{lemma}

\begin{lemma}\label{lemma:DWsubsetGW}
    Given a permutation $w \in \mathfrak{S}_n$, we have \[\supp(\mathfrak{D}^w)\subseteq \supp(\GW(w)).\]
\end{lemma}
\begin{proof}
    By \Cref{lemma:chaincontainment} and \Cref{prop:suppsumprod}, we have \[\supp(\mathfrak{D}^w)=\bigcup_{C: u = u_0 \lessdot u_1\lessdot\cdots \lessdot u_{\ell} = w} \supp(m_C)\subseteq \supp(\GW(w)).\]
\end{proof}

\begin{lemma}\label{lemma:DWsupsetGW}
    Given a permutation $w \in \mathfrak{S}_n$, we have \[\supp(\mathfrak{D}^w)\supseteq \supp(\GW(w)).\]
\end{lemma}
\begin{proof}
    This result follows immediately from \Cref{lem:existsgreedychain} and \Cref{lemma:greedy=GW}.
\end{proof}

We combine \Cref{lemma:DWsubsetGW} and \Cref{lemma:DWsupsetGW} to obtain the following result.
\begin{theorem}\label{theorem:DualSchubSCNP}
    
    Given a permutation $w \in \mathfrak{S}_n$, we have \[\supp (\mathfrak{D}^w)= \supp(\GW(w)).\]
\end{theorem}
We are now equipped to prove \Cref{theorem:support}.
\begin{proof}[Proof of \Cref{theorem:support}]
    Applying \Cref{theorem:DualSchubSCNP} and \Cref{prop:suppsumprod}, we obtain
    \[\supp (\mathfrak{D}^w)= \supp(\GW(w))=\sum_{(a,b) \in \Inv(w)}\{e_a, e_{a+1}, \dots, e_{b-1}\},\]
    as desired.
\end{proof}

We have shown that every greedy chain of $[\id, w]$ is a dominant chain of $\mathfrak{D}^w$, and therefore that $\mathfrak{D}^w$ has SCNP. Now by \Cref{prop:SCNPtoSNP}, we have the following corollary.

\begin{corollary}\label{cor:DualSchubSNP}
    For all $w\in \mathfrak{S}_n$, the dual Schubert polynomial $\mathfrak{D}^w$ has SNP.
\end{corollary}

\subsection{Newton polytopes as generalized permutahedra}\label{section:newtongeneralizedpermutahedra}

\begin{theorem}\label{thm:DualSchubertAsGeneralizedPermutahedron}
    For $w\in \mathfrak{S}_n$, $\Newton(\mathfrak{D}^w)$ is a generalized permutahedron $P_n^z(\{z_I\})_{I\subseteq [n]}$ with
    \[z_I = \sum_{(a, b)\in \Inv(w)}\1_{I\supseteq[a, b)}\]
    for all $I\subseteq [n]$, where $I\supseteq [a, b)$ denotes $I\supseteq \{a, a+1, \dots, b-1\}$.
\end{theorem}
\begin{proof}[Proof sketch]
    This follows from \Cref{theorem:support} and \Cref{prop:permutahedraminkowskisum}.
\end{proof}

\begin{proof}[Proof of \Cref{thm:M-conv}]
    This follows directly from \Cref{prop:Mconvex=SNP+GP}, \Cref{cor:DualSchubSNP}, and \Cref{thm:DualSchubertAsGeneralizedPermutahedron}.
\end{proof}

\section{The vanishing problem for dual Schubert polynomials}\label{section:vanishing}

In light of \Cref{theorem:support}, we give a polynomial-time algorithm to determine whether a given term is found in a given dual Schubert polynomial.

\begin{proof}[Proof of \Cref{thm:vanish}]
    We first check if $\sum_{i=1}^{n-1} c_i = \ell(w)$. If not, the algorithm terminates and we conclude that $x^\alpha$ vanishes in $\mathfrak{D}^w$. If so, we construct a bipartite graph $B = (U,V,E)$ where $U = \Inv(w)$ and 
    $V$ contains $c_i$ copies of $x_i$ for each $i$. Let $E$ consist of all edges $(a,b) \to x_i$ with $a \le i < b$. We now use the blossom algorithm \cite{inproceedings} to compute the maximum cardinality of a matching in $B$. By \Cref{theorem:support}, $\alpha \in \supp(\mathfrak{D}^w)$ if and only if the maximum matching of $B$ has $\ell$ edges. The runtime of the algorithm in our case is $O(\sqrt{|U|+|V|}|E|) = O(\sqrt{n^2}n^4) = O(n^5)$. 
\end{proof}
\begin{example}
\Cref{fig:vanish} shows the graph used to verify that the term $x_1^2x_2$ is in $\mathfrak{D}^{321}$.
    \begin{figure}[H]
\[\begin{tikzcd}[cramped]
	{(1,2)\bullet} &&& {\bullet x_1} \\
	{(1,3)\bullet} &&& {\bullet x_1} \\
	{(2,3)\bullet} &&& {\bullet x_2}
	\arrow[from=1-1, to=1-4]
	\arrow[from=1-1, to=2-4]
	\arrow[from=2-1, to=1-4]
	\arrow[from=2-1, to=2-4]
	\arrow[from=2-1, to=3-4]
	\arrow[from=3-1, to=3-4]
\end{tikzcd}\]

\caption{
    A maximum matching has $3 = \ell(321)$ edges, so $(2,1)\in\supp(\mathfrak{D}^{321})$. 
}\label{fig:vanish}
\end{figure}
\end{example}

\section{Vertices of Newton polytopes}\label{section:vertices}

In \Cref{thm:DSPNPVert}, we characterize the vertices of $\Newton(\mathfrak{D}^w)$.

\begin{proof}[Proof of \Cref{thm:DSPNPVert}]
    This follows from \Cref{theorem:DualSchubSCNP} and \cite[Theorem 3.5]{2009minkowski}.
\end{proof}

Furthermore, given $w \in \mathfrak{S}_n$, we describe a procedure to obtain the vertices of the polytope $\Newton(\mathfrak{D}^w)$. Figures illustrating each step of the procedure are given in the appendix (\Cref{section:appx}). The validity of this procedure may be justified using \cite[Corollary~8.2]{postnikovpermutohedra}.

\begin{itemize}
    \item \textit{Step 1:} Construct a Young diagram of staircase shape $(n-1, n - 2, \ldots, 1)$, and label the boxes by the following pairs of inversions. In the $i$-th row of the diagram for $1\le i \le n-1$, label the boxes from left to right by $(i,n), (i,n-1), \dots, (i,i+1)$.
    \item \textit{Step 2:} Write a $1$ in the box if the corresponding inversion pair is in $\Inv(w)$, and write a $0$ in the box if not.
    \item \textit{Step 3:} Construct the $\frac{1}{n+1}\binom{2n}{n}$ tilings of the Young diagram by $n-1$ rectangles. 
    \item \textit{Step 4:} For each tiling, sum the entries of each rectangle and write the sum at the bottom right corner of the rectangle. Reading the summands from top to bottom gives a vertex of $\Newton(\mathfrak{D}^w)$. 
\end{itemize}

After completing the procedure, we get all the vertices of $\Newton(\mathfrak{D}^w)$, possibly with multiplicity. See \Cref{fig:partition-tiling} for an illustration of the case $w = 4213$.


\section{Appendix}\label{section:appx}

\begin{figure}[H]
\centering
\begin{minipage}{0.45\textwidth}
\centering
\begin{tikzpicture}[scale=1.1]
    \draw (0.35, -0.2) node {\scalebox{0.8}{$(1,6)$}};
    \draw (1.35, -0.2) node {\scalebox{0.8}{$(1,5)$}};
    \draw (2.35, -0.2) node {\scalebox{0.8}{$(1,4)$}};
     \draw (3.35, -0.2) node {\scalebox{0.8}{$(1,3)$}};
    \draw (4.35, -0.2) node {\scalebox{0.8}{$(1,2)$}};
    \draw (0.35, -1.2) node {\scalebox{0.8}{$(2,6)$}};
    \draw (1.35, -1.2) node {\scalebox{0.8}{$(2,5)$}};
    \draw (2.35, -1.2) node {\scalebox{0.8}{$(2,4)$}};
    \draw (3.35, -1.2) node {\scalebox{0.8}{$(2,3)$}};
    \draw (0.35, -2.2) node {\scalebox{0.8}{$(3,6)$}};
    \draw (1.35, -2.2) node {\scalebox{0.8}{$(3,5)$}};
    \draw (2.35, -2.2) node {\scalebox{0.8}{$(3,4)$}};
    \draw (0.35, -3.2) node {\scalebox{0.8}{$(4,6)$}};
    \draw (1.35, -3.2) node {\scalebox{0.8}{$(4,5)$}};
    \draw (0.35, -4.2) node {\scalebox{0.8}{$(5,6)$}};
    
    \draw[thick] (0, -1) -- (4, -1);
    \draw[thick] (0, -2) -- (3, -2);
    \draw[thick] (0, -3) -- (2, -3);
    \draw[thick] (0, -4) -- (1, -4);
    
    \draw[thick] (1, 0) -- (1, -4);
    \draw[thick] (2, 0) -- (2, -3);
    \draw[thick] (3, 0) -- (3, -2);
    \draw[thick] (4, 0) -- (4, -1);



    \draw[thick] (0, 0) -- (5, 0) -- (5, -1) -- (4, -1) -- (4, -2) -- (3, -2) -- (3, -3) -- (2, -3) -- (2,-4) -- (1,-4) -- (1, -5) -- (0, -5) -- (0,0);
\end{tikzpicture}
\caption{A staircase Young diagram with $n= 6$.}
\label{fig:step1}
    
\end{minipage}
\hfill
\begin{minipage}{0.45\textwidth}
\centering
    \begin{tikzpicture}[scale=1.1]

    \draw (0.35, -0.2) node {\scalebox{0.8}{$(1,6)$}};
    \draw (1.35, -0.2) node {\scalebox{0.8}{$(1,5)$}};
    \draw (2.35, -0.2) node {\scalebox{0.8}{$(1,4)$}};
     \draw (3.35, -0.2) node {\scalebox{0.8}{$(1,3)$}};
    \draw (4.35, -0.2) node {\scalebox{0.8}{$(1,2)$}};
    \draw (0.35, -1.2) node {\scalebox{0.8}{$(2,6)$}};
    \draw (1.35, -1.2) node {\scalebox{0.8}{$(2,5)$}};
    \draw (2.35, -1.2) node {\scalebox{0.8}{$(2,4)$}};
    \draw (3.35, -1.2) node {\scalebox{0.8}{$(2,3)$}};
    \draw (0.35, -2.2) node {\scalebox{0.8}{$(3,6)$}};
    \draw (1.35, -2.2) node {\scalebox{0.8}{$(3,5)$}};
    \draw (2.35, -2.2) node {\scalebox{0.8}{$(3,4)$}};
    \draw (0.35, -3.2) node {\scalebox{0.8}{$(4,6)$}};
    \draw (1.35, -3.2) node {\scalebox{0.8}{$(4,5)$}};
    \draw (0.35, -4.2) node {\scalebox{0.8}{$(5,6)$}};
    \draw (0.5, -0.5) node {1};
    \draw (1.5, -0.5) node {0};
    \draw (2.5, -0.5) node {0};
    \draw (3.5, -0.5) node {0};
    \draw (4.5, -0.5) node {0};
    \draw (0.5, -1.5) node {1};
    \draw (1.5, -1.5) node {1};
    \draw (2.5, -1.5) node {0};
    \draw (3.5, -1.5) node {1};
    \draw (0.5, -2.5) node {1};
    \draw (1.5, -2.5) node {0};
    \draw (2.5, -2.5) node {0};
    \draw (0.5, -3.5) node {1};
    \draw (1.5, -3.5) node {1};
    \draw (0.5, -4.5) node {1};


    
    \draw[thick] (0, -1) -- (4, -1);
    \draw[thick] (0, -2) -- (3, -2);
    \draw[thick] (0, -3) -- (2, -3);
    \draw[thick] (0, -4) -- (1, -4);
    
    \draw[thick] (1, 0) -- (1, -4);
    \draw[thick] (2, 0) -- (2, -3);
    \draw[thick] (3, 0) -- (3, -2);
    \draw[thick] (4, 0) -- (4, -1);



    \draw[thick] (0, 0) -- (5, 0) -- (5, -1) -- (4, -1) -- (4, -2) -- (3, -2) -- (3, -3) -- (2, -3) -- (2,-4) -- (1,-4) -- (1, -5) -- (0, -5) -- (0,0);
\end{tikzpicture}
\caption{When $w = 253641$, the boxes are filled with $1$'s as above.}
\label{fig:step2}
\end{minipage}

\end{figure}

\begin{figure}[H]
\centering
\begin{minipage}{0.45\textwidth}
\centering
\begin{tikzpicture}[scale=1.1]
    \fill[\colorA, nearly transparent] (0, 0) -- (2, 0) -- (2, -4) -- (0, -4);
    \fill[\colorB, nearly transparent] (2,-1) -- (2, -3) -- (3, -3) -- (3, -1);
    \fill[\colorC, nearly transparent] (2, 0) -- (5, 0) -- (5, -1) -- (2, -1);
    \fill[\colorD, nearly transparent] (3, -1) -- (4, -1) -- (4, -2) -- (3, -2);
     \fill[\colorE, nearly transparent] (0, -4) -- (1, -4) -- (1, -5) -- (0, -5);

    \draw (0.35, -0.2) node {\scalebox{0.8}{$(1,6)$}};
    \draw (1.35, -0.2) node {\scalebox{0.8}{$(1,5)$}};
    \draw (2.35, -0.2) node {\scalebox{0.8}{$(1,4)$}};
     \draw (3.35, -0.2) node {\scalebox{0.8}{$(1,3)$}};
    \draw (4.35, -0.2) node {\scalebox{0.8}{$(1,2)$}};
    \draw (0.35, -1.2) node {\scalebox{0.8}{$(2,6)$}};
    \draw (1.35, -1.2) node {\scalebox{0.8}{$(2,5)$}};
    \draw (2.35, -1.2) node {\scalebox{0.8}{$(2,4)$}};
    \draw (3.35, -1.2) node {\scalebox{0.8}{$(2,3)$}};
    \draw (0.35, -2.2) node {\scalebox{0.8}{$(3,6)$}};
    \draw (1.35, -2.2) node {\scalebox{0.8}{$(3,5)$}};
    \draw (2.35, -2.2) node {\scalebox{0.8}{$(3,4)$}};
    \draw (0.35, -3.2) node {\scalebox{0.8}{$(4,6)$}};
    \draw (1.35, -3.2) node {\scalebox{0.8}{$(4,5)$}};
    \draw (0.35, -4.2) node {\scalebox{0.8}{$(5,6)$}};
    \draw (0.5, -0.5) node {1};
    \draw (1.5, -0.5) node {0};
    \draw (2.5, -0.5) node {0};
    \draw (3.5, -0.5) node {0};
    \draw (4.5, -0.5) node {0};
    \draw (0.5, -1.5) node {1};
    \draw (1.5, -1.5) node {1};
    \draw (2.5, -1.5) node {0};
    \draw (3.5, -1.5) node {1};
    \draw (0.5, -2.5) node {1};
    \draw (1.5, -2.5) node {0};
    \draw (2.5, -2.5) node {0};
    \draw (0.5, -3.5) node {1};
    \draw (1.5, -3.5) node {1};
    \draw (0.5, -4.5) node {1};

    
    \draw[thick] (0, -1) -- (4, -1);
    \draw[thick] (0, -2) -- (3, -2);
    \draw[thick] (0, -3) -- (2, -3);
    \draw[thick] (0, -4) -- (1, -4);
    
    \draw[thick] (1, 0) -- (1, -4);
    \draw[thick] (2, 0) -- (2, -3);
    \draw[thick] (3, 0) -- (3, -2);
    \draw[thick] (4, 0) -- (4, -1);


    \draw[thick] (0, 0) -- (5, 0) -- (5, -1) -- (4, -1) -- (4, -2) -- (3, -2) -- (3, -3) -- (2, -3) -- (2,-4) -- (1,-4) -- (1, -5) -- (0, -5) -- (0,0);
\end{tikzpicture}
\caption{Continuing the above example, we consider a tiling with $n - 1$ rectangles.}
\label{fig:step3}
\end{minipage}
\hfill
\begin{minipage}{0.45\textwidth}
    \begin{tikzpicture}[scale=1.1]
    \fill[\colorA, nearly transparent] (0, 0) -- (2, 0) -- (2, -4) -- (0, -4);
    \fill[\colorB, nearly transparent] (2,-1) -- (2, -3) -- (3, -3) -- (3, -1);
    \fill[\colorC, nearly transparent] (2, 0) -- (5, 0) -- (5, -1) -- (2, -1);
    \fill[\colorD, nearly transparent] (3, -1) -- (4, -1) -- (4, -2) -- (3, -2);
     \fill[\colorE, nearly transparent] (0, -4) -- (1, -4) -- (1, -5) -- (0, -5);

    \draw (0.35, -0.2) node {\scalebox{0.8}{$(1,6)$}};
    \draw (1.35, -0.2) node {\scalebox{0.8}{$(1,5)$}};
    \draw (2.35, -0.2) node {\scalebox{0.8}{$(1,4)$}};
     \draw (3.35, -0.2) node {\scalebox{0.8}{$(1,3)$}};
    \draw (4.35, -0.2) node {\scalebox{0.8}{$(1,2)$}};
    \draw (0.35, -1.2) node {\scalebox{0.8}{$(2,6)$}};
    \draw (1.35, -1.2) node {\scalebox{0.8}{$(2,5)$}};
    \draw (2.35, -1.2) node {\scalebox{0.8}{$(2,4)$}};
    \draw (3.35, -1.2) node {\scalebox{0.8}{$(2,3)$}};
    \draw (0.35, -2.2) node {\scalebox{0.8}{$(3,6)$}};
    \draw (1.35, -2.2) node {\scalebox{0.8}{$(3,5)$}};
    \draw (2.35, -2.2) node {\scalebox{0.8}{$(3,4)$}};
    \draw (0.35, -3.2) node {\scalebox{0.8}{$(4,6)$}};
    \draw (1.35, -3.2) node {\scalebox{0.8}{$(4,5)$}};
    \draw (0.35, -4.2) node {\scalebox{0.8}{$(5,6)$}}; \draw (0.5, -0.5) node {1};
    \draw (1.5, -0.5) node {0};
    \draw (2.5, -0.5) node {0};
    \draw (3.5, -0.5) node {0};
    \draw (4.5, -0.5) node {0};
    \draw (0.5, -1.5) node {1};
    \draw (1.5, -1.5) node {1};
    \draw (2.5, -1.5) node {0};
    \draw (3.5, -1.5) node {1};
    \draw (0.5, -2.5) node {1};
    \draw (1.5, -2.5) node {0};
    \draw (2.5, -2.5) node {0};
    \draw (0.5, -3.5) node {1};
    \draw (1.5, -3.5) node {1};
    \draw (0.5, -4.5) node {1};

    \draw (5.25, -1.25) node {0};
    \draw (4.25, -2.25) node {1};
    \draw (3.25, -3.25) node {0};
    \draw (2.25, -4.25) node {6};
    \draw (1.25, -5.25) node {1};
    
    \draw[thick] (0, -1) -- (4, -1);
    \draw[thick] (0, -2) -- (3, -2);
    \draw[thick] (0, -3) -- (2, -3);
    \draw[thick] (0, -4) -- (1, -4);
    
    \draw[thick] (1, 0) -- (1, -4);
    \draw[thick] (2, 0) -- (2, -3);
    \draw[thick] (3, 0) -- (3, -2);
    \draw[thick] (4, 0) -- (4, -1);



    \draw[thick] (0, 0) -- (5, 0) -- (5, -1) -- (4, -1) -- (4, -2) -- (3, -2) -- (3, -3) -- (2, -3) -- (2,-4) -- (1,-4) -- (1, -5) -- (0, -5) -- (0,0);
\end{tikzpicture}
\caption{$\Newton(\mathfrak{D}^{253641})$ has a vertex at $(0,1,0,6,1)$. }
\label{fig:step5}
\end{minipage}
\end{figure}

 \begin{figure}[H]
       \centering
       \begin{tikzpicture}[scale=1.1]
    \fill[\colorA, nearly transparent] (0, 0) -- (3, 0) -- (3, -1) -- (0, -1);
    \fill[\colorB, nearly transparent] (0, -1) -- (2, -1) -- (2, -2) -- (0, -2);
    \fill[\colorC, nearly transparent] (0, -2) -- (1, -2) -- (1, -3) -- (0, -3);

    \draw (0.35, -0.2) node {\scalebox{0.8}{$(1,4)$}};
    \draw (1.35, -0.2) node {\scalebox{0.8}{$(1,3)$}};
    \draw (2.35, -0.2) node {\scalebox{0.8}{$(1,2)$}};
    \draw (0.35, -1.2) node {\scalebox{0.8}{$(2,4)$}};
    \draw (1.35, -1.2) node {\scalebox{0.8}{$(2,3)$}};
    \draw (0.35, -2.2) node {\scalebox{0.8}{$(3,4)$}};

    \draw (0.5, -0.5) node {1};
    \draw (1.5, -0.5) node {1};
    \draw (2.5, -0.5) node {1};
    \draw (0.5, -1.5) node {0};
    \draw (1.5, -1.5) node {1};
    \draw (0.5, -2.5) node {0};

    \draw (3.25, -1.25) node {3};
    \draw (2.25, -2.25) node {1};
    \draw (1.25, -3.25) node {0};
    
    \draw (0, -1) -- (2, -1);
    \draw (0, -2) -- (1, -2);
    \draw (1, 0) -- (1, -2);
    \draw (2, 0) -- (2, -1);

    \draw[thick] (0, -1) -- (2, -1);
    \draw[thick] (0, -2) -- (1, -2);

    \draw[thick] (0, 0) -- (3, 0) -- (3, -1) -- (2, -1) -- (2, -2) -- (1, -2) -- (1, -3) -- (0, -3) -- (0, 0);
\end{tikzpicture}
\qquad
\begin{tikzpicture}[scale=1.1]
    \fill[\colorA, nearly transparent] (2, 0) -- (3, 0) -- (3, -1) -- (2, -1);
    \fill[\colorB, nearly transparent] (0, 0) -- (2, 0) -- (2, -2) -- (0, -2);
    \fill[\colorC, nearly transparent] (0, -2) -- (1, -2) -- (1, -3) -- (0, -3);

    \draw (0.35, -0.2) node {\scalebox{0.8}{$(1,4)$}};
    \draw (1.35, -0.2) node {\scalebox{0.8}{$(1,3)$}};
    \draw (2.35, -0.2) node {\scalebox{0.8}{$(1,2)$}};
    \draw (0.35, -1.2) node {\scalebox{0.8}{$(2,4)$}};
    \draw (1.35, -1.2) node {\scalebox{0.8}{$(2,3)$}};
    \draw (0.35, -2.2) node {\scalebox{0.8}{$(3,4)$}};

    \draw (0.5, -0.5) node {1};
    \draw (1.5, -0.5) node {1};
    \draw (2.5, -0.5) node {1};
    \draw (0.5, -1.5) node {0};
    \draw (1.5, -1.5) node {1};
    \draw (0.5, -2.5) node {0};

    \draw (3.25, -1.25) node {1};
    \draw (2.25, -2.25) node {3};
    \draw (1.25, -3.25) node {0};
    
    \draw (0, -1) -- (2, -1);
    \draw (0, -2) -- (1, -2);
    \draw (1, 0) -- (1, -2);
    \draw (2, 0) -- (2, -1);

    \draw[thick] (0, -1) -- (2, -1);
    \draw[thick] (0, -2) -- (1, -2);

    \draw[thick] (0, 0) -- (3, 0) -- (3, -1) -- (2, -1) -- (2, -2) -- (1, -2) -- (1, -3) -- (0, -3) -- (0, 0);
\end{tikzpicture}
\qquad
\begin{tikzpicture}[scale=1.1]
    \fill[\colorA, nearly transparent] (0, 0) -- (3, 0) -- (3, -1) -- (0, -1);
    \fill[\colorB, nearly transparent] (1, -1) -- (2, -1) -- (2, -2) -- (1, -2);
    \fill[\colorC, nearly transparent] (0, -1) -- (1, -1) -- (1, -3) -- (0, -3);

    \draw (0.35, -0.2) node {\scalebox{0.8}{$(1,4)$}};
    \draw (1.35, -0.2) node {\scalebox{0.8}{$(1,3)$}};
    \draw (2.35, -0.2) node {\scalebox{0.8}{$(1,2)$}};
    \draw (0.35, -1.2) node {\scalebox{0.8}{$(2,4)$}};
    \draw (1.35, -1.2) node {\scalebox{0.8}{$(2,3)$}};
    \draw (0.35, -2.2) node {\scalebox{0.8}{$(3,4)$}};

    \draw (0.5, -0.5) node {1};
    \draw (1.5, -0.5) node {1};
    \draw (2.5, -0.5) node {1};
    \draw (0.5, -1.5) node {0};
    \draw (1.5, -1.5) node {1};
    \draw (0.5, -2.5) node {0};

    \draw (3.25, -1.25) node {3};
    \draw (2.25, -2.25) node {1};
    \draw (1.25, -3.25) node {0};
    
    \draw (0, -1) -- (2, -1);
    \draw (0, -2) -- (1, -2);
    \draw (1, 0) -- (1, -2);
    \draw (2, 0) -- (2, -1);

    \draw[thick] (0, -1) -- (2, -1);
    \draw[thick] (0, -2) -- (1, -2);

    \draw[thick] (0, 0) -- (3, 0) -- (3, -1) -- (2, -1) -- (2, -2) -- (1, -2) -- (1, -3) -- (0, -3) -- (0, 0);
\end{tikzpicture}

\begin{tikzpicture}[scale=1.1]
    \fill[\colorA, nearly transparent] (2, 0) -- (3, 0) -- (3, -1) -- (2, -1);
    \fill[\colorB, nearly transparent] (1, 0) -- (2, 0) -- (2, -2) -- (1, -2);
    \fill[\colorC, nearly transparent] (0, 0) -- (1, 0) -- (1, -3) -- (0, -3);

    \draw (0.35, -0.2) node {\scalebox{0.8}{$(1,4)$}};
    \draw (1.35, -0.2) node {\scalebox{0.8}{$(1,3)$}};
    \draw (2.35, -0.2) node {\scalebox{0.8}{$(1,2)$}};
    \draw (0.35, -1.2) node {\scalebox{0.8}{$(2,4)$}};
    \draw (1.35, -1.2) node {\scalebox{0.8}{$(2,3)$}};
    \draw (0.35, -2.2) node {\scalebox{0.8}{$(3,4)$}};

    \draw (0.5, -0.5) node {1};
    \draw (1.5, -0.5) node {1};
    \draw (2.5, -0.5) node {1};
    \draw (0.5, -1.5) node {0};
    \draw (1.5, -1.5) node {1};
    \draw (0.5, -2.5) node {0};

    \draw (3.25, -1.25) node {1};
    \draw (2.25, -2.25) node {2};
    \draw (1.25, -3.25) node {1};
    
    \draw (0, -1) -- (2, -1);
    \draw (0, -2) -- (1, -2);
    \draw (1, 0) -- (1, -2);
    \draw (2, 0) -- (2, -1);

    \draw[thick] (0, -1) -- (2, -1);
    \draw[thick] (0, -2) -- (1, -2);

    \draw[thick] (0, 0) -- (3, 0) -- (3, -1) -- (2, -1) -- (2, -2) -- (1, -2) -- (1, -3) -- (0, -3) -- (0, 0);
\end{tikzpicture}
\qquad
\begin{tikzpicture}[scale=1.1]
    \fill[\colorA, nearly transparent] (1, 0) -- (3, 0) -- (3, -1) -- (1, -1);
    \fill[\colorB, nearly transparent] (1, -1) -- (2, -1) -- (2, -2) -- (1, -2);
    \fill[\colorC, nearly transparent] (0, 0) -- (1, 0) -- (1, -3) -- (0, -3);

    \draw (0.35, -0.2) node {\scalebox{0.8}{$(1,4)$}};
    \draw (1.35, -0.2) node {\scalebox{0.8}{$(1,3)$}};
    \draw (2.35, -0.2) node {\scalebox{0.8}{$(1,2)$}};
    \draw (0.35, -1.2) node {\scalebox{0.8}{$(2,4)$}};
    \draw (1.35, -1.2) node {\scalebox{0.8}{$(2,3)$}};
    \draw (0.35, -2.2) node {\scalebox{0.8}{$(3,4)$}};

    \draw (0.5, -0.5) node {1};
    \draw (1.5, -0.5) node {1};
    \draw (2.5, -0.5) node {1};
    \draw (0.5, -1.5) node {0};
    \draw (1.5, -1.5) node {1};
    \draw (0.5, -2.5) node {0};

    \draw (3.25, -1.25) node {2};
    \draw (2.25, -2.25) node {1};
    \draw (1.25, -3.25) node {1};
    
    \draw (0, -1) -- (2, -1);
    \draw (0, -2) -- (1, -2);
    \draw (1, 0) -- (1, -2);
    \draw (2, 0) -- (2, -1);

    \draw[thick] (0, -1) -- (2, -1);
    \draw[thick] (0, -2) -- (1, -2);

    \draw[thick] (0, 0) -- (3, 0) -- (3, -1) -- (2, -1) -- (2, -2) -- (1, -2) -- (1, -3) -- (0, -3) -- (0, 0);
\end{tikzpicture}

\caption{$\Newton(\mathfrak{D}^{4213})$ has vertices $(3,1,0), (1,3,0), (1,2,1), (2,1,1)$.}
       \label{fig:partition-tiling}
   \end{figure}


\acknowledgements{We thank the UMN Combinatorics and Algebra REU, Ayah Almousa, Casey Appleton, Grant Barkley, Shiliang Gao, Yibo Gao, June Huh, Jonas Iskander, Meagan Kenney, Mitchell Lee, Pavlo Pylyavskyy, Victor Reiner, Andrew Sack, Shiyun Wang, and Lauren Williams for their support.}
 
 
%% 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}
