%% 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]{FPSAC2019}

\articlenumber{50}
\addbibresource{50.bib}

%% 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}

\theoremstyle{plain}
\theoremstyle{definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{openprob}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

\usepackage{tabularx,graphicx,float,placeins}
\usepackage{tikz}
\usetikzlibrary[calc,intersections,through,backgrounds,arrows,decorations.pathmorphing]


\def\Sfrak{\mathfrak{S}}

\def\Bbf{\mathbf{B}}


\def\Acal{\mathcal{A}}\def\Bcal{\mathcal{B}}\def\Ccal{\mathcal{C}}\def\Dcal{\mathcal{D}}\def\Fcal{\mathcal{F}}\def\Gcal{\mathcal{G}}\def\Jcal{\mathcal{J}}\def\Hcal{\mathcal{H}}\def\Ical{\mathcal{I}}\def\Lcal{\mathcal{L}}\def\Mcal{\mathcal{M}}\def\Ncal{\mathcal{N}}\def\Ocal{\mathcal{O}}\def\Pcal{\mathcal{P}}\def\Rcal{\mathcal{R}}\def\Scal{\mathcal{S}}\def\Tcal{\mathcal{T}}\def\Wcal{\mathcal{W}}\def\Xcal{\mathcal{X}}\def\Ycal{\mathcal{Y}}\def\Zcal{\mathcal{Z}}


\def\Cbb{\mathbb{C}}\def\Fbb{\mathbb{F}}\def\Kbb{\mathbb{K}}\def\Nbb{\mathbb{N}}\def\Pbb{\mathbb{P}}\def\Rbb{\mathbb{R}}\def\Zbb{\mathbb{Z}}


\def\bsym{\boldsymbol}\def\ds{\displaystyle}\def\hookra{\hookrightarrow}\def\LRa{\Leftrightarrow}\def\longlra{\longleftrightarrow}\def\ov{\overline}\def\pa{\partial}\def\pr{\prime}\def\prpr{\prime\prime}\def\ra{\rightarrow}\def\Ra{\Rightarrow}\def\setm{\setminus}\def\ss{\scriptstyle}\def\thra{\twoheadrightarrow}\def\un{\underline}\def\wtil{\widetilde}

\DeclareMathOperator{\Bic}{Bic}  %Biclosed sets
\DeclareMathOperator{\bij}{bij} %bijection
\DeclareMathOperator{\Camb}{Camb}  %Cambrian lattice
\DeclareMathOperator{\Closed}{Closed}  %Closed sets
\DeclareMathOperator{\CB}{CB}  %cyclic bracketings
\DeclareMathOperator{\Cl}{Cl}  %Closed sets
\DeclareMathOperator{\codim}{codim} %codimension
\DeclareMathOperator{\Comp}{Comp}  %connected components
\DeclareMathOperator{\Con}{Con}  %Set of all lattice congruences
\DeclareMathOperator{\con}{con}  %lattice congruence induced by edge-contraction
\DeclareMathOperator{\Cov}{Cov}  %Covering relations
\DeclareMathOperator{\des}{des}  %descents
\DeclareMathOperator{\Des}{Des}  %descents
\DeclareMathOperator{\id}{id}  %identity
\DeclareMathOperator{\Id}{Id}  %identity
\DeclareMathOperator{\init}{init}  %initial vertex
\DeclareMathOperator{\Int}{Int}  %Intervals
\DeclareMathOperator{\JI}{JI}  %join-irreducibles
\DeclareMathOperator{\lk}{lk}  %link
\DeclareMathOperator{\MI}{MI}  %meet-irreducibles
\DeclareMathOperator{\MTub}{MTub}  %maximal tubings
\DeclareMathOperator{\NC}{NC}  %noncrossing partitions
\DeclareMathOperator{\NCSym}{NCSym}  %noncommutative symmetric functions
\DeclareMathOperator{\NF}{NF}  %generators of transitive set
\DeclareMathOperator{\NN}{NN}  %nonnesting partitions
\DeclareMathOperator{\rk}{rk}  %rank
\DeclareMathOperator{\sdes}{sdes}  %Simple descents
\DeclareMathOperator{\SDes}{SDes}  %Simple descents
\DeclareMathOperator{\Seg}{Seg}  %Segments
\DeclareMathOperator{\spans}{spans}  %span
\DeclareMathOperator{\stars}{star}  %star of face in simplicial complex
\DeclareMathOperator{\std}{std}  %standarization
\DeclareMathOperator{\SYT}{SYT}  %Simple descents
\DeclareMathOperator{\term}{term}  %terminal vertex
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\vol}{vol} %volume
\DeclareMathOperator{\topT}{top} %top
\DeclareMathOperator{\YSym}{YSym} %Loday-Ronco Hopf algebra
%\DeclareMathOperator{\Fbb}{Fbb} %distinguished basis

%Commands EB added
\newcommand{\covdown}{\cov_{\downarrow}}
\newcommand{\covup}{\cov^{\uparrow}}
\newcommand{\down}{\downarrow}
\newcommand{\newword}[1]{\textbf{\emph{#1}}}
\newcommand{\covers}{{\,\,\,\cdot\!\!\!\! >\,\,}}
\newcommand{\covered}{{\,\,<\!\!\!\!\cdot\,\,\,}}
\renewcommand{\top}{\operatorname{top}}
\newcommand{\pidown}{\pi_\downarrow}
\newcommand{\piup}{\pi^\uparrow}
\newcommand{\inv}{\operatorname{inv}}
\newcommand{\meet}{\wedge}
\newcommand{\join}{\vee}
\renewcommand{\Join}{\bigvee}
\newcommand{\Meet}{\bigwedge}
\newcommand{\Poset}{\operatorname{Poset}}
\newcommand{\smax}{\operatorname{smax}}
\newcommand{\dis}{\operatorname{dis}}
\renewcommand{\vert}{\operatorname{vert}}


\usepackage{lipsum}

%% define your title in the usual way
\title{Lattices from graph associahedra}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Emily Barnard\addressmark{1} and Thomas McConville\thanks{Thomas McConville was partially supported by Grant NSF/DMS-1440140.}\addressmark{2}}


%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Northeastern University \\ \addressmark{2}Mathematical Sciences Research Institute}

%% 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{Given a graph G on $n$ vertices, Postnikov defined a graph associahedron $P_G$ as an example of a generalized permutohedron, a polytope whose normal fan coarsens the braid arrangement. 
Motivated by two general constructions of subalgebras of the Malvenuto-Reutenauer algebra, we consider the poset $L_G$ obtained by orienting the one-skeleton of $P_G$.
Because the normal fan of $P_G$ coarsens the normal fan of the standard permutohedron we obtain a surjection $\Psi_G: \Sfrak_n \to L_G$.
We characterize the graphs $G$ for which $\Psi_G$ is a lattice quotient map.
%Combinatorially, each face of $P_G$ corresponds to certain collections of compatible subgraphs of G called tubings.
% Graph associahedra were introduced independently by Carr and Devadoss and by Davis, Januszkiewicz, and Scott. 
 }

\resumetitle{R\'esum\'e}
%% put your French abstract here, or comment this out if you don't have one
\resume{
\`A partir d'un graphe G sur les sommets $n$, Postnikov a d\'efini l'associahedron $ P_G$ du graphe comme un exemple de permutoh\`edre g\'en\'eralis\'e.
Nous d\'efinissons un ordre partiel sur les sommets de $P_G$ et \'etudions sa relation avec l'ordre faible du $\mathfrak{S}_n$.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{graph associahedra, Hopf algebras, lattices}

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

\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

\section{Introduction}

In \cref{coarsening}, we display the weak order on the symmetric group $\Sfrak_3$ and show how to obtain the corresponding Tamari lattice. 
These two posets share three important qualities.
First, the Hasse diagram for each poset is also the 1-skeleton of a simple polytope, the permutohedron and associahedron respectively.
Second, each poset is also a lattice.
(Recall that a poset is a lattice if each pair of elements $x$ and $y$ has a unique smallest upper bound $x\join y$ and a unique largest lower bound $x\meet y$.)
Finally, the normal fan of the associahedron coarsens the normal fan of the standard permutohedron, which is the fan determined by a hyperplane arrangement known as the \emph{braid arrangement}.
(We recall the definition of the normal fan in \cref{sec:normal}.)

%\begin{figure}[h]
%  \centering
%\scalebox{.8}{
%\begin{tikzpicture}
%%\draw [black, thick] (0.1,1.45) -- (.68,2.1);
%\draw [black, thick,->] (0,0) -- (-1,.9);
%\draw [black, thick,->] (0,0) -- (1,.9);
%\draw [black, thick,->] (1,1) -- (1,1.9);
%\draw [black, thick,->] (-1,1) -- (-1,1.9);
%\draw [black, thick,->] (1,2) -- (.1,2.9);
%\draw [black, thick,->] (-1,2) -- (-.1,2.9);
%\node at (0,-.4) {$123$};
%\node at (1.4,1) {$132$};
%\node at (-1.4,1) {$213$};
%\node at (1.4,2) {$312$};
%\node at (-1.4,2) {$231$};
%\node at (0,3.2) {$321$};
%\end{tikzpicture}}
%\qquad  \qquad
%\scalebox{.8}{
%\begin{tikzpicture}
%%\draw [black, thick] (0.1,1.45) -- (.68,2.1);
%\draw [black, thick,->] (0,0) -- (-1,.9);
%\draw [black, thick,->] (0,0) -- (1,.9);
%\draw [black, thick,->] (1,1) -- (.1,2.9);
%\draw [black, thick,->] (-1,1) -- (-1,1.9);
%%\draw [black, thick,->] (1,2) -- (.1,2.9);
%\draw [black, thick,->] (-1,2) -- (-.1,2.9);
%\node at (0,-.4) {$((x y) z) w$};
%\node at (2,1) {$(x y) (z w)$};
%\node at (-2,1) {$(x (y z)) w$};
%%\node at (1.4,2) {$312$};
%\node at (-2,2) {$x ((y z) w)$};
%\node at (0,3.2) {$x ( y (z))$};
%\end{tikzpicture}}
% \caption{The weak order on the symmetric group $\Sfrak_3$ and a Tamari lattice}
%        \label{fig:motivation}
%\end{figure}

\begin{figure}
  
  \centering
  \resizebox{\textwidth}{!}{
  \includegraphics{psimap}}
  \caption{\label{coarsening}The canonical surjection from the weak order on $\Sfrak_3$ to the Tamari lattice.}
  
\end{figure}

Pictorially, we see that this coarsening induces a canonical surjection $\Psi$ from the vertices of the permutohedron to the vertices of the associahedron.
It is well known that $\Psi$ is a \emph{lattice quotient map}.
That is, $\Psi$ preserves the meet and the join operations: 
\[\Psi(x\join y) = \Psi(x)\join \Psi(y) \text{ and } \Psi(x\meet y) = \Psi(x)\meet \Psi(y).\]
In this paper, we study the relationship between the weak order on $\Sfrak_n$ and a poset~$L_G$ that is analogous to the Tamari Lattice.
 
%We consider a partial ordering on the vertices of a graph associahedron.
Given a graph $G$, Postnikov defined a graph associahedron $P_G$ as an example of a \emph{generalized permutohedron}, a simple polytope that is a Minkowski summand of the permutohedron \cite{postnikov:2009permutohedra}. Graph associahedra were also introduced independently in \cite{carr.devadoss:2006coxeter} and \cite{davis.janus.scott:2003fundamental}. Some significant examples of graph associahedra include the associahedron, the cyclohedron, and the permutohedron. 

Given a linear functional $\lambda$, we partially order the vertices of $P_G$ by taking the transitive and reflexive closure of the relation $\mathbf{x}\le \mathbf{y}$ when $[\mathbf{x}, \mathbf{y}]$ is an edge of $P_G$ and $\lambda(\mathbf{x})\le \lambda(\mathbf{y})$.
We define $L_G$ to be the resulting poset.
It turns out that the edge $[\mathbf{x}, \mathbf{y}]$ in $P_G$ is actually a cover relation $\mathbf{x}\covered \mathbf{y}$ in $L_G$.
Like the Tamari lattice, the Hasse diagram of $L_G$ is the 1-skeleton of a simple polytope, namely $P_G$.
Like the associahedron, the normal fan of $P_G$ coarsens the normal fan of the permutohedron.
Thus we obtain a canonical surjection $\Psi_G: \Sfrak_n\to L_G$.
The following theorem is our main result.
In the statement, a graph $G$ is \emph{filled} if for each edge $\{i,k\}$ in $G$, there are edges $\{i,j\}$ and $\{j,k\}$ in $G$ whenever $i<j<k$.%\margin{changed edges to subsets. EB}

\begin{theorem}\label{thm_main_lattice}
The map $\Psi_G$ is a lattice quotient map if and only if $G$ is filled.
\end{theorem}

A key element of our proof is a combinatorial description of $L_G$ as certain collections of connected subgraphs of $G$ called \emph{tubings}.
We recall these definitions in \cref{sec:tubing}. 
Along the way, we show that each face of the $P_G$ is an interval in the poset $L_G$.
We call this the \emph{non-revisiting chain property}.
See \cref{subsec:NRC}.

The genesis for \cref{thm_main_lattice} came from comparing two different Hopf algebra constructions.
In \cite{ronco:2012tamari}, Ronco defined a binary operation on a vector space generated by the tubings of an ``admissible'' family of graphs $\Gcal$, which gives this space the structure of an associative algebra. We call this algebra a \emph{tubing algebra}.
%See Section~\ref{subsec_hopf_algebra}. 
In particular, when $\Gcal$ is the set of complete graphs $K_n$ or path graphs $P_n$, the tubing algebra is isomorphic to either the Malvenuto-Reutenauer algebra on permutations \cite{malvenuto.reutenauer:1995duality} or the Loday-Ronco algebra on binary trees \cite{loday.ronco:1998hopf}, respectively.
 %The interpretation of these algebras in terms of tubings was given previously in \cite{forcey.springfield:2010geometric}.
%In Section~\ref{subsec_tubing_coalgebra}, we introduce the notion of a ``restriction-compatible'' family of graphs. Such families come with a comultiplication on their maximal tubings. We call the resulting coalgebra a \emph{tubing coalgebra}.
Reading introduced a general technique to construct subalgebras of the Malvenuto-Reutenauer algebra using lattice quotients of the weak order on permutations in \cite{reading:2005lattice}. 
We use \cref{thm_main_lattice} to show that these two constructions substantially overlap.

Most statements in this abstract are made without proofs.
Complete proofs, additional results and examples can be found in \cite{graph_associahedron}.

%In \cite{forcey:2012species}, Forcey posed the problem of determining whether $L_G$ is a lattice for any graph $G$. This turns out to be false in general; cf. Section~\ref{subsec:tubing_lattice}. We say a graph $G$ on $[n]$ is \emph{right-filled} if whenever $\{i,k\}$ is an edge, so is $\{j,k\}$ for $i<j<k$. Dually, we say $G$ is \emph{left-filled} if $\{i,j\}$ is an edge whenever there is an edge $\{i,k\}$ for $i<j<k$. We prove that $L_G$ is a lattice whenever $G$ is either left-filled or right-filled. More precisely, these are the cases when $L_G$ is a semilattice quotient of the weak order. For other graphs, the poset $L_G$ may still be a lattice, even if it is not a semilattice quotient of the weak order. Some additional examples and conjectures are discussed in Section~\ref{sec:other}. %The path graph labeled $4-1-3-2$ is one such example.

\section{Posets of maximal tubings}\label{sec:tubing}
In the following sections we recall the necessary background for our main result.
We begin by defining the simple polytope $P_G$.
Then, we define the poset $L_G$, and we recall the canonical surjection $\Psi_G: \Sfrak_n\to L_G$.
Finally, we describe a combinatorial realization of $L_G$ in terms of certain connected subgraphs of $G$ that will be useful when we discuss the proof of \cref{thm_main_lattice}.
\subsection{The normal fan of a polytope}\label{sec:normal}
Before defining the graph associahedron $P_G$, we recall the definition of the normal fan of a polytope.

A \emph{(polyhedral) fan} $\Ncal$ is a set of cones in $\Rbb^n$ such that for any two elements $C,C^{\pr}\in\Ncal$, their intersection $C\cap C^{\pr}$ is in $\Ncal$ and it is a face of both $C$ and $C^{\pr}$. It is \emph{complete} if $\bigcup_{C\in\Ncal} C=\Rbb^n$ and \emph{pointed} if $\{0\}\in\Ncal$. A pointed fan $\Ncal$ is \emph{simplicial} if the number of extreme rays of each $C\in\Ncal$ is equal to its dimension. We consider a simplicial fan to be a type of ``realization'' of a simplicial complex; more accurately, it is a cone over a geometric realization.

For a polytope $P\subseteq\Rbb^n$ and $f\in(\Rbb^n)^*$ in the dual space, we let $P^f$ be the subset of $P$ at which $f$ achieves its maximum value. We consider an equivalence relation on $(\Rbb^n)^*$ where $f\sim g$ if $P^f=P^g$. It is not hard to show that each equivalence class is a relatively open polyhedral cone. The \emph{normal fan} of $P$ is the set of closures of these cones, which forms a complete polyhedral fan. A polytope is simple if and only if its normal fan is simplicial.

For polytopes $P,Q\subseteq\Rbb^n$, their \emph{Minkowski sum} $P+Q$ is the polytope
$$P+Q=\{\mathbf{x}+\mathbf{y}\ |\ \mathbf{x}\in P,\ \mathbf{y}\in Q\}.$$
Recall that the normal fan of $P+Q$ is the coarsest common refinement of the normal fans of $P$ and $Q$ \cite[Proposition~7.12]{ZieglerGu}.

\subsection{Graph associahedra}\label{subsec:graph_assoc}
Let $G=(V,E)$ be a simple graph with vertex set $V=[n]=\{1,\ldots,n\}$. If $I\subseteq V$, we let $G|_I$ denote the induced subgraph of $G$ with vertex set $I$. A \emph{tube} is a nonempty subset $I$ of vertices such that the induced subgraph $G|_I$ is connected. Any tube not equal to $V$ is called a \emph{proper tube}. We let $\Ical(G)$ be the set of all tubes of $G$.



%
%The set of tubings of a graph forms a flag simplicial complex $\Delta_G$, called the \emph{nested set complex}.
%Proofs that the face lattice of $P_G$ coincides with the nested set complex are given in \cite{feichtner.sturmfels:2005matroid} and \cite{postnikov:2009permutohedra}.

%A set $W$ consisting of the vertices of a connected component of $G$ is a tube that is compatible with every other tube, so it is a cone point in $\Delta_G$. The nested set complex is sometimes defined with these cone points removed since this subcomplex is a simplicial sphere. For our purposes, however, it will be convenient to consider the maximal tubes as part of every maximal tubing of $G$.

\begin{figure}
  
  \centering
  \includegraphics[width=.45\textwidth]{mink} \qquad   \includegraphics[width=.45\textwidth]{tamari}
  \caption{The graph associahedron for the graph with edge set $E=\{\{1,3\},\{3,2\}\}$ and the corresponding poset of maximal tubings $L_G$.}
\label{fig:L_ex}
\end{figure}

%If $\Xcal$ is a maximal tubing, then there is a unique vertex that not contained in any proper tube in $\Xcal$.

Let $\mathbf{e}_1,\ldots,\mathbf{e}_n$ be the standard basis vectors in $\Rbb^n$. Given $I\subseteq[n]$, let $\Delta_I$ be the simplex with vertices $\{\mathbf{e}_i\ |\ i\in I\}$. The \emph{graph associahedron} $P_G$ is the Minkowski sum of simplices $\Delta_I$ over all tubes $I$ of $G$; that is,

$$P_G=\sum\Delta_I=\left\{\sum \mathbf{x}_I\ |\ (\mathbf{x}_I\in\Delta_I:\ I\ \mbox{is a tube})\right\}.$$
On the left-hand of \cref{fig:L_ex}, we depict the Minkowski sum construction for $P_G$ where $G$ is the path graph with edges $\{1,3\}$ and $\{3,2\}$.

Fix $\lambda:\Rbb^n\ra\Rbb$ such that $\lambda(x_1,x_2,\ldots,x_n)=nx_1+(n-1)x_2+\cdots+x_n$.
We define the \emph{poset of maximal tubings}~$L_G$ to be the poset whose partial order is the reflexive and transitive closure of the relation $\mathbf{x}\le \mathbf{y}$ when $[\mathbf{x}, \mathbf{y}]$ is an edge of $P_G$ and $\lambda(\mathbf{x})\le \lambda(\mathbf{y})$.

When $G$ is a complete graph, the polytope $P_G$ is the ``standard'' permutohedron, and its normal fan $\Ncal_G$ is the set of cones defined by the braid arrangement. 
The poset $L_G$ is isomorphic to the weak order on $\Sfrak_n$.
When $G$ is a path graph, $P_G$ is the associahedron, and $L_G$ is the Tamari lattice.
For a general graph $G$, the polytope $P_G$ is a Minkowski summand of the standard permutohedron, so its normal fan is coarser than that defined by the braid arrangement.
Thus, for each graph $G$, we obtain a canonical surjection $\Psi_G: \Sfrak_n \to L_G$ analogous to the canonical surjection depicted in \cref{coarsening}.



\subsection{Tubings and $G$-trees}%\margin{I think the definition of $G$-tree fits well at the end of this subsection, right after the last lemma.}
To describe the proof of \cref{thm_main_lattice}, we will need a combinatorial realization of $L_G$ in terms of maximal tubings and $G$-trees.
%We define the \emph{deletion} $G\setm I$ to be the graph $G|_{V\setm I}$ and the \emph{contraction} (or \emph{reconnected complement}) $G/I$ as the graph with vertex set $V\setm I$ and edges $\{i,j\},\ (i\neq j)$ if either $\{i,j\}\in E(G)$ or there exists a tube $J$ of $G|_I$ such that $\{i,k\}\in E(G)$ and $\{j,l\}\in E(G)$ for some $k,l\in J$.
% Note that we define deletion and contraction on sets of vertices of $G$ rather than on edges as it is done for graphic matroids. Furthermore, the contracted graph $G/I$ is always simple, i.e. it has no loops or parallel edges.
Two tubes $I, J$ are said to be \emph{compatible} if either

\begin{itemize}
\item they are \emph{nested}: $I\subseteq J$ or $J\subseteq I$, or
\item they are \emph{separated}: $I\cup J$ is not a tube.
\end{itemize}

A \emph{tubing} $\Xcal$ of $G$ is any collection of pairwise compatible tubes. 
A collection $\Xcal$ is said to be a \emph{maximal tubing} if it is maximal by inclusion. We let $\MTub(G)$ be the set of maximal tubings of the graph $G$.
%If $\Xcal$ is a tubing of $G$ and $X_1,\ldots,X_r\in\Xcal$ are pairwise disjoint, then the union $I=X_1\cup\cdots\cup X_r$ is called an \emph{ideal} of $\Xcal$. This terminology may be explained by the connection to $G$-trees given later in this section.

%\begin{lemma}
%If $\Xcal$ is a tubing of $G$ with an ideal $I$ then there is a unique collection $X_1,\ldots, X_r$ of pairwise disjoint tubes in $\Xcal$, namely the connected components of $G|_I$, such that $I=X_1\cup\cdots\cup X_r$.
%\end{lemma}
%\begin{proof}
%Assume that $X_1\cup\cdots\cup X_r = I=Y_1\cup \cdots \cup Y_s$.
%For each $j\in [r]$ there is some $i\in [s]$ such that $X_j\cap Y_i \ne \emptyset$.
%%Either $X_j\subseteq Y_i$ or $Y_i\subseteq X_j$.
%By symmetry, assume $X_j\subseteq Y_i$.
%For each $a\in Y_i\setminus X_j$ there is a tube $X_{j_a}\in \{X_1,\ldots, X_r\}$ such that $a\in X_{j_a}$.
%Thus $Y_i \subseteq X_j \cup \left(\bigcup_{a\in Y_i\setminus X_j} X_{j_a}\right)$ which intersects each set in the union.
%Hence, $ X_j \cup \left(\bigcup_{a\in Y_i\setminus X_j} X_{j_a}\right)$ is connected, and that is a contradiction.
%Therefore, if $X_i=Y_j$.
%The statement of the lemma follows.
%\end{proof}

Any maximal tubing $\Xcal$ contains exactly $n$ tubes. 
%Indeed, the map $\top_\Xcal$ defined below is a bijection from the set of tubes in $\Xcal$ to the vertex set $[n]$.
In the next lemma, $\Xcal|_I$ is the set of all tubes $J\in \Xcal$ such that $J\subseteq I$.

\begin{lemma}
  If $\Xcal$ is a maximal tubing, then each tube $I$ contains a unique element $\topT_{\Xcal}(I)\in [n]$ not contained in any proper tube of $\Xcal|_I$. Furthermore, the function $\topT_{\Xcal}$ is a bijection from the tubes in $\Xcal$ to the vertex set $[n]$.
\end{lemma}
%\begin{proof}
%It is straight forward to check that $\topT_\Xcal(I)$ is well-defined for each tube $I\in \Xcal$.
%Let $k\in [n]$ and let $\Ical$ be the set of tubes in $\Xcal$ which contain $k$.
%Observe that $\Ical$ is not empty (because the connected component of $G$ containing $k$ is a tube in $\Xcal$.)
%Because each of the tubes in $\Ical$ are nested, there is a smallest tube $I\in \Ical$ (under containment) which contains $k$.
%For this tube, we have $\topT_\Xcal(I) =k$.
%
%It follows that if $\topT_\Xcal(I)=\topT_\Xcal(J)=k$ then $I=J$.
%Therefore $\topT_\Xcal$ is indeed a bijection.
%\end{proof}

The set of all tubings of $G$ has the structure of a flag simplicial complex called the \emph{nested set complex}, denoted $\Delta_G$.
The nested set complex may be realized as a simplicial fan that is isomorphic to the normal fan of  $P_G$ \cite[Theorem 2.6]{carr.devadoss:2006coxeter}, \cite[Theorem 3.14]{feichtner.sturmfels:2005matroid}, \cite[Theorem 7.4]{postnikov:2009permutohedra}.
Thus the face lattice of $P_G$ is dual to the face lattice of $\Delta_G$.
So, for example, each maximal tubing of $G$ corresponds bijectively to a vertex of $P_G$; see \cite[Proposition~7.9]{postnikov:2009permutohedra}.
In the lemma below, we interpret $i_{\down}$ as the smallest tube in $\Xcal$ that contains the element $i$.
(This notation will be explained by the connection to $G$-trees given later in this section.)

\begin{lemma}\label{polytope_poset}
If $\Xcal$ is any maximal tubing, the point $\mathbf{v}^\Xcal=(v_1,\ldots,v_n)$ is a vertex of $P_G$ where $v_i$ is the number of tubes $I\in \Ical(G)$ (not necessarily contained in $\Xcal$) such that $i\in I$ and $I \subseteq i_{\down}$. Conversely, every vertex of $P_G$ comes from a maximal tubing in this way. 
%% \begin{itemize}
%% \item $i\in I$, and 
%% \item if $J\in\Xcal$ such that $i\in J$, then $I\subseteq J$.\margin{Alternatively, write $e_{i,I}$ for the $i^{th}$ vertex of the simplex $\Delta_I$.
%% Then $v^{\Xcal}= \sum_{I\subseteq i_{\down}} e_{i,I}$, where $i_\down$ is the smallest tube in $\Xcal$ (under containment) such that $i\in I$.
%% In the $G$-tree for $\Xcal$ $i_\down$ is just the principal order ideal generated by $i$.}
%% \end{itemize}

\end{lemma}

We now explain why $L_G$ is called the poset of maximal tubings.
Suppose that $I$ is a non-maximal tube in $\Xcal$.
Because the face lattice of $P_G$ is dual to the face lattice of $\Delta_G$, there exists a unique tube $J$ distinct from $I$ such that $\Ycal=\Xcal\setm\{I\}\cup\{J\}$ is a maximal tubing of $G$. 
Define a \emph{flip} as the relation $\Xcal\ra \Ycal$ if $\topT_\Xcal(I)<\topT_{\Ycal}(J)$. We say $\Xcal\leq \Ycal$ holds if there exists a sequence of flips of maximal tubings of the form $\Xcal\ra\cdots\ra \Ycal$.
The relation $(\MTub(G), \le)$ was independently introduced by Forcey \cite{forcey:2012species} and Ronco \cite{ronco:2012tamari}.

\begin{lemma}\label{lem_poset}
The poset $L_G$ is isomorphic to $(\MTub(G), \le)$.
\end{lemma}

\begin{proof}[Proof sketch]
The edges of the graph associahedron $P_G$ take the following form. Let $\Xcal$ and $\Ycal$ be maximal tubings of $G$ such that $\Ycal=\Xcal\setm\{I\}\cup\{J\}$ for some distinct tubes $I,J$. Set $i=\topT_\Xcal(I)$ and $j=\topT_{\Ycal}(J)$. Then the vertices $\mathbf{v}^{\Xcal}$ and $\mathbf{v}^{\Ycal}$ agree on every coordinate except the $i^{th}$ and $j^{th}$ coordinates. Indeed, $\mathbf{v}^{\Ycal}-\mathbf{v}^{\Xcal}=r(\mathbf{e}_i-\mathbf{e}_j)$ where $r$ is equal to the number of tubes of $G$ contained in $I\cup J$ that contain both $i$ and $j$. %(\textcolor{purple}{PROVE? or CITE?})

Recall that $\lambda$ is the linear functional $\lambda(x_1,\ldots,x_n)=nx_1+(n-1)x_2+\cdots+x_n$. If $\Xcal$ and $\Ycal$ are as above and $i<j$, then $\lambda(\mathbf{v}^{\Ycal}-\mathbf{v}^{\Xcal})>0$. Hence, $\mathbf{v}^{\Ycal}\covers \mathbf{v}^{\Xcal}$.
%the relation~$\Xcal\ra \Ycal$ on maximal tubings is induced by the linear functional $\lambda$. Consequently, the relation is acyclic, so its transitive closure is a partial order.
\end{proof}

An example of the poset $L_G$ is given in \cref{fig:L_ex}, where $G$ is the path graph with edge set $E=\{\{1,3\},\{3,2\}\}$. 
 The figure demonstrates that the relation $(\MTub(G),\le)$ defined above is indeed the transitive and reflexive closure of an orientation of the 1-skeleton of~$P_G$.

\begin{figure}
  
  \centering
  \includegraphics{tubing_tree}
  \caption{\label{fig:tubing_tree}(left) A maximal tubing. (right) Its associated $G$-tree.}
  
\end{figure}

It will be convenient to encode a maximal tubing in terms of a certain poset on $[n]$.
Let $T$ be a forest with vertex set $[n]$.
The \emph{forest poset} associated with $T$ is defined by the relation $i<_T k$ whenever $i$ and $k$ belong to the same connected component of $T$, and the unique path from $i$ to the root of this component passes through $k$.
We usually denote this forest poset by $T$ as well.

Let $i_\down$ denote the principal order ideal generated by $i$ in $T$.
We say that $T$ is a \emph{$G$-forest}, or \emph{$G$-tree} when $T$ is connected, if it satisfies both of the following conditions (see also \cite[Definition~8.1]{postnikov.reiner.williams:2008faces}):
\begin{itemize}
\item for each $i\in [n]$, the set $i_\down$ is a tube of $G$;
\item if $i$ and $k$ are incomparable in $T$, then $i_\down \cup k_\down$ is not tube of $G$.
\end{itemize}

Given a $G$-forest $T$, observe that the collection $\chi(T)=\{i_\down: i\in [n]\}$ is a maximal tubing on $G$.
An example of this correspondence is shown in \cref{fig:tubing_tree}.
%Indeed, consider $I=i_\down$ and $J=k_\down$ for any pair $i$ and $k$ in $[n]$.
%If $i$ and $k$ are not comparable, then it is immediate that $I$ and $J$ are compatible (because $I\cup J$ is not a tube).
%On the other hand, if $i$ and $k$ are comparable, then either $I\subset J$ or $J\subset I$.
The following theorem is essentially a specialization of \cite[Proposition~8.2]{postnikov.reiner.williams:2008faces}. 

%(See also \cite[Proposition~7.8]{} and \cite[Propostion~3.17]{}.)
\begin{theorem}\label{G-trees}
Let $G$ be a graph with vertex set $[n]$.
Then the map $\chi: T\mapsto \{i_\down: i\in [n]\}$ is a bijection from the set of $G$-forests to the set of maximal tubings of $G$.
\end{theorem}


%To conserve space, we will not prove in general that $L_G$ is isomorphic to the poset on $\MTub(G)$ defined above.
%\begin{figure}
%  
%  \centering
%  \includegraphics{tamari}
%  \caption{\label{fig:L_ex}A poset of maximal tubings}
% 
%\end{figure}






\section{Main results}
\subsection{Covering relations of the poset of maximal tubings}
We are now prepared to outline the key steps in the proof of \cref{thm_main_lattice}.
We begin by building some intuition coming from the cover relations in $L_G$.
\begin{figure}
  
  \centering
  \includegraphics{G3102}
  \caption{\label{fig_nl}A poset of maximal tubings that is not a lattice.}
  
\end{figure}
In terms of maximal tubings, recall that $\Xcal \covered \Ycal$ provided that $\Ycal=\Xcal\setm\{I\}\cup\{J\}$ for some distinct tubes $I,J$, and $i=\top_\Xcal(I) < \top_\Ycal(J)=j$.
Because each cover relation ``swaps'' a pair of integers $i$ and $j$, one might na\"ively guess that the size of any maximal chain in $L_G$ is bounded above by $\binom{n}{2}$.
For comparison, each maximal chain in the weak order on $\Sfrak_n$ has size equal to $\binom{n}{2}$.
Surprisingly, this guess is false in general.
The reader can check in \cref{fig_nl} that $L_G$ has a maximal chain of size 7.
Indeed, the poset $L_G$ in this example is not a lattice.
(The two indicated atoms have two minimal upper bounds.)
In this example, there is no hope that the canonical surjection $\Psi_G: \Sfrak_n\to L_G$ is a lattice quotient map.

When $G$ is a filled graph, our na\"ive guess is true.
The size of each maximal chain in $L_G$ is bounded by $\binom{n}{2}$.
To prove one direction of \cref{thm_main_lattice}, assume that $G$ is filled and let $T$ be a $G$-forest.
We say that a permutation $\sigma \in \Sfrak_n$ is a \emph{$G$-permutation} provided that it is the lexicographically minimal linear extension of $T$.
(See \cite{postnikov.reiner.williams:2008faces} for an equivalent definition.)
We note that the fiber $\Psi_G^{-1}(T)$ is precisely the set of all linear extensions of~$T$.

For $G$ connected, the associated $G$-permutation can be constructed recursively as follows. 
First, remove the root $x$ of $T$.
Let $C_1,\ldots,C_r$ be the connected components of $T\setminus \{x\}$.
We index the connected components so that each element of $C_i$ is less than each element of $C_j$ (as integers) whenever $i<j$.
(The components of $T$ can be indexed in this way because $G$ is filled.)
Next, we apply the construction to each component to obtain a word $\sigma(C_i) =v_{{C_i}_1}\ldots v_{{C_i}_s}$ for $i\in [r]$.
Finally, we concatenate the words $\sigma(C_1)\ldots \sigma(C_r)$, ending with the root~$x$.
For example, $G$-permutation for the $G$-tree shown \cref{fig:tubing_tree} is $152634$.
When $G$ is the path graph with vertices labeled $1, 2, \ldots, n$ from left to right, the set of $G$-permutations is equal to the set of 312 -avoiding permutations of $\Sfrak_n$.

There is a natural surjection from the weak order on $\Sfrak_n$ to the subposet of the weak order induced by the set of $G$-permutations of $[n]$.
As a first step in our proof of \cref{thm_main_lattice}, we show that this surjection, which only involves the combinatorics of $\Sfrak_n$, is a lattice quotient map.
The second (and more technical) step of the proof is showing that $L_G$ is isomorphic to this subposet of $G$-permutations.
Recall that the inversion set of a permutation $\sigma$ is the set of pairs $(i,j)$ where $i<j$ and $j$ precedes $i$ in the one-line notation for $\sigma$.
By analogy, define a pair of integers $(i,j)$ to be an \emph{inversion} of a $G$-tree $T$ if $i<j$ and $j<_T i$.
It follows from our recursive construction that the inversion set of $T$ is equal to the inversion set of the $G$-permutation $\sigma(T)$.
In the weak order, $\sigma< \tau$ if and only if $\inv(\sigma)\subset \inv(\tau)$.
To complete the proof, we show that two $G$-trees are ordered $T<T'$ in $L_G$ if and only if $\inv(T)\subset \inv(T')$.
Characterizing the cover relations in $L_G$ was a key element of this argument.
(See \cite[Proposition~2.24 and Lemma~4.12]{graph_associahedron}.)

To prove the remaining direction of \cref{thm_main_lattice}, we reduce the problem to a certain subgraph of $G$.
%If $I$ is a subset of $[n]$, let $\Comp(I)$ be the set of maximal tubes of $G|_I$; i.e., $J\in\Comp(I)$ if $J\subseteq I$ and $G|_J$ is a connected component of $G|_I$. If $\Xcal$ is a tubing of $G$, we set
%$$\Xcal|_I=\bigcup_{J\in\Xcal}\Comp(I\cap J).$$
%
%\begin{lemma}\label{lem:tubing_restriction}
%Let $\Xcal$ is a tubing of $G$ and $I\subseteq [n]$.
%  The collection $\Xcal|_I$ is a tubing of $G|_I$. If $\Xcal$ is maximal then so is $\Xcal|_I$.
%\end{lemma}
%Lemma~\ref{lem:tubing_restriction} can be deduced from a cellular map between different graph associahedra; see \cite[Definition 3.4]{forcey.springfield:2010geometric}. This map is a generalized form of the \emph{Tonks projection}, one of the standard maps from the faces of the permutohedron to the faces of the associahedron.
We show that if $\Psi_G:\Sfrak_n\to L_G$ is a lattice quotient map, then restricting to any subset~$I$ of vertices also produces a lattice quotient map from the weak order to $L_{G|_I}$.
If $G$ is not filled then there exists some edge $\{i,k\}$ in $G$ such that either $\{i,j\}$ or $\{j,k\}$ is not an edge, for some $j\in [i+1,k-1]$.
To complete the proof, it is enough to show that we do not have a lattice quotient map from the weak order to $L_{G|_I}$ where $I=\{i,j,k\}$.

The graph associahedron $P_{G|_I}$ is a face of $P_G$.
In the next section, we show that each face of $P_G$ is actually an interval in the poset $L_G$.
This is equivalent to the statement that for any tubing $\Xcal$, the set of maximal tubings containing $\Xcal$ is an interval of~$L_G$.

\subsection{The non-revisiting chain property}\label{subsec:NRC}

In this section, we prove that graph associahedra have the non-revisiting chain property, defined below. 

Given a polytope $P$, we will say a linear functional $\lambda:\Rbb^n\ra\Rbb$ is \emph{generic} if it is not constant on any edge of $P$. When $\lambda$ is generic, we let $L(P,\lambda)$ be the poset on the vertices of $P$ where $v\leq w$ if there exists a sequence of vertices $v=v_0,v_1,\ldots,v_l=w$ such that $\lambda(v_0)<\lambda(v_1)<\cdots<\lambda(v_l)$ and $[v_{i-1},v_i]$ is an edge for all $i\in\{1,\ldots,l\}$.

The following properties of $L(P,\lambda)$ are immediate.

\begin{proposition}\label{prop:omega_properties}
  Let $P$ be a polytope with a generic linear functional $\lambda$.
  \begin{enumerate}
  \item The dual poset $L(P,\lambda)^*$ is isomorphic to $L(P,-\lambda)$.
  \item If $F$ is a face of $P$, then the inclusion $L(F,\lambda)\hookra L(P,\lambda)$ is order-preserving.
  \item $L(P,\lambda)$ has a unique minimum $v_{\hat{0}}$ and a unique maximum $v_{\hat{1}}$.
  \end{enumerate}
\end{proposition}

The pair $(P,\lambda)$ is said to have the \emph{non-revisiting chain (NRC) property} if whenever $\mathbf{x}<\mathbf{y}<\mathbf{z}$ in $L(P,\lambda)$ such that $\mathbf{x}$ and $\mathbf{z}$ lie in a common face $F$, then $\mathbf{y}$ is also in $F$.
The name comes from the fact that if $P$ has the NRC property, then any sequence of vertices following edges monotonically in the direction of $\lambda$ does not return to a face after leaving it. 
By definition, the NRC property means that faces are \emph{order-convex} subsets of $L(P,\lambda)$.
(Recall that a subset $S$ of a poset is \emph{order-convex} provided that whenever elements $x,z\in S$ satisfy $x<z$ then the entire interval $[x,z]$ belongs to $S$.)
In light of \cref{prop:omega_properties}, this is equivalent to the condition that for any face $F$, the set of vertices of $F$ form an interval of $L(P,\lambda)$ isomorphic to $L(F,\lambda)$.

%\begin{remark}
%  There is also an unoriented version of the NRC property due to Klee and Wolfe called the \emph{non-revisiting path property}, which is the condition that for any two vertices $\mathbf{v}, \mathbf{w}$ of $P$, there exists a path from $\mathbf{v}$ to $\mathbf{w}$ that does not revisit any facet of $P$. 
%It was known that the Hirsch conjecture on the diameter of 1-skeleta of polytopes is equivalent to the conjecture that every polytope has the non-revisiting path property.
%These conjectures were formulated to determine the computational complexity of the simplex method from linear programming in the \emph{worst-case} scenario.
%The Hirsch conjecture was disproved by Santos \cite{santos:2012counterexample}, but many interesting questions remain.
%In particular, the polynomial Hirsch conjecture remains open.
%\end{remark}

In contrast to the non-revisiting path property, many low-dimensional polytopes lack the non-revisiting chain property.
For example, if $P$ is a simplex of dimension at least $2$, then $[\mathbf{v}_{\hat{0}},\mathbf{v}_{\hat{1}}]$ is an edge of $P$ that is not an interval of $L(P,\lambda)$.
However, the property does behave nicely under Minkowski sum.

\begin{proposition}\label{prop:MS_NRF}
  If $(P,\lambda)$ and $(Q,\lambda)$ have the non-revisiting chain property, then so does $(P+Q,\lambda)$.
\end{proposition}

The proof of \cref{prop:MS_NRF} relies on \cref{lem:sum_order_embed}. For polytopes $P$ and $Q$, the normal fan of $P+Q$ is the common refinement of $\Ncal(P)$ and $\Ncal(Q)$; that is,
$$\Ncal(P+Q)=\{C\cap C^{\pr}\ |\ C\in\Ncal(P),\ C^{\pr}\in\Ncal(Q)\}.$$
Let $V(P)$ be the set of vertices of $P$, and let $C_v$ be the normal cone to the vertex $v$ in $P$. From the description of the normal fan of $P+Q$, there is a canonical injection $\iota:V(P+Q)\hookra V(P)\times V(Q)$ that assigns a vertex $\mathbf{v}\in P+Q$ to $(\mathbf{u},\mathbf{w})$ if the normal cones satisfy $C_{\mathbf{v}}=C_\mathbf{u}\cap C_\mathbf{w}$.


\begin{lemma}\label{lem:sum_order_embed}
  The map $\iota:V(P+Q)\hookra V(P)\times V(Q)$ is an order-preserving function from $L(P+Q,\lambda)$ to $L(P,\lambda)\times L(Q,\lambda)$.
\end{lemma}

%\begin{proof}
%  Let $E=[\mathbf{v},\mathbf{w}]$ be an edge of $P+Q$, and suppose $\lambda(\mathbf{v})<\lambda(\mathbf{w})$. It suffices to show that $\iota(\mathbf{v})<\iota(\mathbf{w})$.
%
%  Let $\iota(\mathbf{v})=(\mathbf{v}^{\pr},\mathbf{v}^{\pr\pr})$ and $\iota(\mathbf{w})=(\mathbf{w}^{\pr},\mathbf{w}^{\pr\pr})$. 
% Then the normal cone $C_E$ is the intersection of $C_\mathbf{v}$ and $C_\mathbf{w}$, which themselves are the intersections of $C_{\mathbf{v}^{\pr}},\ C_{\mathbf{v}^{\pr\pr}}$ and $C_{\mathbf{w}^{\pr}},\ C_{\mathbf{w}^{\pr\pr}}$. 
% Since
%  $$C_E=(C_{\mathbf{v}^{\pr}}\cap C_{\mathbf{w}^{\pr}})\cap(C_{\mathbf{v}^{\pr\pr}}\cap C_{\mathbf{w}^{\pr\pr}})$$
%  is a cone of codimension 1, we may deduce that $C_{\mathbf{v}^{\pr}}\cap C_{\mathbf{w}^{\pr}}$ and $C_{\mathbf{v}^{\pr\pr}}\cap C_{\mathbf{w}^{\pr\pr}}$ are both of codimension $\leq 1$. 
%  Hence, the segments $E^{\pr}=[\mathbf{v}^{\pr},\mathbf{w}^{\pr}]$ and $E^{\pr\pr}=[\mathbf{v}^{\pr\pr},\mathbf{w}^{\pr\pr}]$ are either vertices or edges of $P$ and $Q$, respectively. 
%  Moreover, if both $E^{\pr}$ and $E^{\pr\pr}$ are edges, then they must be parallel and $E=E^{\pr}+E^{\pr\pr}$. 
%  In the event one of them is a vertex, say $E^{\pr\pr}$ (so that $\mathbf{v}''=\mathbf{w}''$), then $E^{\pr}$ must be an edge, and
%  $$\lambda(\mathbf{v}^{\pr})=\lambda(\mathbf{v})-\lambda(\mathbf{v}^{\pr\pr})<\lambda(\mathbf{w})-\lambda(\mathbf{v}^{\pr\pr})=\lambda(\mathbf{w})-\lambda(\mathbf{w}^{\pr\pr})=\lambda(\mathbf{w}^{\pr}).$$
%  If both $E^\pr$ and $E^{\pr\pr}$ are edges, then since $\lambda$ achieves its minimum value on $E=E^{\pr}+E^{\pr\pr}$ at $\mathbf{v}=\mathbf{v}^{\pr}+\mathbf{v}^{\pr\pr}$, we have $\lambda(\mathbf{v}^{\pr})<\lambda(\mathbf{w}^{\pr})$ and $\lambda(\mathbf{v}^{\pr\pr})<\lambda(\mathbf{w}^{\pr\pr})$. 
%  In both cases, $\iota(\mathbf{v})<\iota(\mathbf{w})$ holds.
%\end{proof}


\begin{proof}[Proof of \cref{prop:MS_NRF}]
Every face of $P+Q$ is of the form $F+F^{\pr}$ where $F$ is a face of $P$ and $F^{\pr}$ is a face of $Q$. 
Suppose $\mathbf{u},\mathbf{v},\mathbf{w}$ are vertices of $P+Q$ such that $\mathbf{u}<\mathbf{v}<\mathbf{w}$ in $L(P+Q,\lambda)$ and $\mathbf{u},\mathbf{w}\in F+F^{\pr}$. Set $\iota(\mathbf{u})=(\mathbf{u}_P,\mathbf{u}_Q)$, and analogously for $\iota(\mathbf{v})$ and $\iota(\mathbf{w})$. 
Then $\mathbf{u}_P\leq \mathbf{v}_P\leq \mathbf{w}_P$ in $L(P,\lambda)$ and $\mathbf{u}_Q\leq \mathbf{v}_Q\leq \mathbf{w}_Q$ in $L(Q,\lambda)$. 
Since $P$ and $Q$ have the non-revisiting chain property, $\mathbf{v}_P$ is in $F$ and $\mathbf{v}_Q$ is in $F^{\pr}$.
 Hence, $\mathbf{v}=\mathbf{v}_P+\mathbf{v}_Q$ is in $F+F^{\pr}$, as desired.
\end{proof}


\begin{corollary}[Proposition 7.2 \cite{hersh:2018nonrevisiting}]
  Every zonotope has the non-revisiting chain property with respect to any generic linear functional.
\end{corollary}


We now return to graph associahedra.
%Let $G$ be a graph on $[n]$, and let $\lambda$ be the linear functional in the proof of Lemma~\ref{lem_poset}, where $\lambda(\mathbf{x})=nx_1+(n-1)x_2+\cdots+x_n$, so that $L_G\cong L(P_G,\lambda)$. Using the decomposition $P_G=\sum\Delta_I$, Lemma~\ref{lem:sum_order_embed} implies that $\pi_J:L_G\ra L(\Delta_J,\lambda)$ obtained as the composition
%$$L_G\hookra\bigotimes_I L(\Delta_I,\lambda)\thra L(\Delta_J,\lambda)$$
%is order-preserving. We note that the poset $L(\Delta_J,\lambda)$ is a chain where $\mathbf{e}_i>\mathbf{e}_j$ whenever $i,j\in J$ with $i<j$. 
%%The next lemma follows immediately from the proof of Lemma~\ref{polytope_poset}.
%\begin{lemma}\label{NRC helper}
%Suppose that $\Xcal$ is a maximal tubing of $G$ and $J$ is a tube not necessarily in~$\Xcal$.
%Then there exists a unique $k\in J$ such that $J\subseteq k_{\down}$, and for this $k$ we have $\pi_J(\Xcal)=\mathbf{e}_k.$
%%Let ${w=w_1\cdots w_n}$ be a permutation such $\{w_1,\ldots, w_i\}$ is an ideal in $\Xcal$ for each $i\in [n]$.
%%Then $\pi_J(\Xcal)=\mathbf{e}_k$ where $k=w_j$ and $j={\max\{i\ |\ w_i\in J\}}$.
%\end{lemma}
%\begin{proof}
%Recall that $k_\down$ is the smallest tube in $\Xcal$ that contains $k$.
%Hence, there is at most one such element $k\in J$ satisfying $J\subseteq k_\down$.
%(Indeed, if $j\in J$ and $J\subseteq j_\down$ then we have $j\in J\subseteq k_\down$.
%Thus $j_\down\subseteq k_\down$.
%By symmetry, $k_\down\subseteq j_\down$.
%Therefore $j=k$.)
%
%Consider the vertex $\mathbf{v}^\Xcal$ in $P_G$.
%Lemma~\ref{polytope_poset} implies that $\Delta_J$ contributes $\mathbf{e}_k$ to $\mathbf{v}^\Xcal$ if and only if $k\in J$ and $J\subseteq k_\down$.
%Therefore $\pi_J(\Xcal) = \mathbf{e}_k$, as desired.
%
%\end{proof} 

\begin{theorem}\label{thm:NRC}
  The pair $(P_G,\lambda)$ has the non-revisiting chain property.
\end{theorem}

%\begin{proof}
%  Every face of $P_G$ is the intersection of some facets, and the intersection of a family of order-convex sets is again order-convex. Hence, it suffices to prove that if $F$ is any facet of $P_G$ then $V(F)$ is an order-convex subset of $L(P_G,\lambda)$. We argue by way of contradiction that this set is order-convex by selecting an appropriate projection $\pi_J$.
%
%  Under the dictionary between tubings of $G$ and faces of $P_G$, if $F$ is a facet, then there exists a tube $I$ such that
%  $$V(F)=\{\mathbf{v}^{\Xcal}\ |\ \Xcal\in\MTub(G),\ I\in\Xcal\}.$$
%  Suppose that there are maximal tubings $\Xcal<\Ycal<\Zcal$ such that $I\in\Xcal$ and $I\in\Zcal$ but $I$ is not in $\Ycal$. Given that such a triple exists, we are free to assume that $\Xcal\ra\Ycal$ is a flip. Then the flip exchanges $I$ for some tube $I^{\pr}$. Let $a=\topT_{\Xcal}(I)$ and $b=\topT_{\Ycal}(I^{\pr})$. The union $I\cup I^{\pr}$ is a tube in both $\Xcal$ and $\Ycal$ such that $b=\topT_{\Xcal}(I\cup I^{\pr})$ and $a=\topT_{\Ycal}(I\cup I^{\pr})$. 
%Hence, $I$ is maximal a tube in the ideal $(I\cup I^{\pr})\setminus \{b\}$ in $\Xcal$.
%That means $G|_I$ is one of the connected components of $G|_{I\cup I^{\pr}\setm\{b\}}$. Since $I\cup I^{\pr}$ is a tube, this implies $I\cup\{b\}$ is a tube as well.
%
% Set $J=I\cup\{b\}$. 
%We claim that if $\Wcal$ is any maximal tubing containing $I$, then the projection $\pi_J(\Wcal)=\mathbf{e}_b$. 
%If $\pi_J(\Wcal)=\mathbf{e}_k\ne \mathbf{e}_b$ then Lemma~\ref{NRC helper} says that $k\in J$ and $J \subseteq k_\down$.
%Since $k\ne b$, it follows that $k\in I$.
%Since $k_\down$ is the smallest tube in $\Wcal$ that contains $k$, we have $k_\down \subseteq I$.
%But then $I\subsetneq J \subseteq k_\down \subseteq I$, and that is a contradiction.
%Therefore, $\pi_J(\Wcal) = \mathbf{e}_b$.
%
%%\margin{Can you say what is $j$?
%%  I made sense of this in the following way:
%%  $\pi_J(\Xcal)=\mathbf{e}_i$, where $i$ is the unique maximal element of $J$ in the corresponding $G$-tree.
%%  (There is a unique maximal element because $J$ is connected.)
%%  If $\pi_J(\Wcal)$ is not equal to $\mathbf{e}_b$, then $b$ is below some element of $I$ in $G$-tree corresponding to $\Wcal$.
%%  But then $\Wcal$ does not contain $I$.}
%So $\pi_J(\Xcal)=\mathbf{e}_b=\pi_J(\Zcal)$, but $\pi_J(\Ycal)=\mathbf{e}_a$, contradicting the assumption that $\Ycal<\Zcal$.
%\end{proof}

\begin{corollary}\label{faces_are_intervals}
For any tubing $\Ycal$ of $G$, the set of maximal tubings which contain $\Ycal$ is an interval in $L_G$.
\end{corollary}

%We omit the proof Theorem~\ref{thm:NRC} here to conserve space.

\begin{remark}
  Another property that a polytope graph may have is the \emph{non-leaving face property}, which is satisfied if for any two vertices $\mathbf{u},\mathbf{v}$ that lie in a common face $F$ of $P$, every geodesic between $\mathbf{u}$ and $\mathbf{v}$ is completely contained in $F$. This property holds for all zonotopes, but is quite special for general polytopes. Although ordinary associahedra are known to have the non-leaving face property \cite{NLF_Property}, not all graph associahedra do. We note that the example geodesic in \cite[Figure 6]{manneville.pilaud:2015graph} that leaves a particular facet cannot be made into a monotone path, so it does not contradict our \cref{thm:NRC}.
\end{remark}

Recall that the M\"obius function $\mu=\mu_L:\Int(L)\ra\Zbb$ is the unique function on the intervals of a finite poset $L$ such that for $x\leq y$:
$$\sum_{x\leq z\leq y}\mu(x,z)=\begin{cases}1\ \mbox{if }x=y\\0\ \mbox{if }x\neq y\end{cases}.$$

When $L(P,\lambda)$ is a lattice with the non-revisiting chain property, the M\"obius function was determined in \cite{hersh:2018nonrevisiting}. One way to prove this is to show that $L(P,\lambda)$ is a crosscut-simplicial lattice; cf. \cite{mcconville:2017crosscut}. In the case of the poset of maximal tubings, we may express the M\"obius function as follows. For a tubing $\Xcal$, let $|\Xcal|$ be the number of tubes it contains.

\begin{corollary}\label{cor:mobius}
  Let $G$ be a graph with vertex set $[n]$ such that $L_G$ is a lattice. Let $\Xcal$ be a tubing that contains every maximal tube. 
 The set of maximal tubings containing $\Xcal$ is an interval $[\Ycal,\Zcal]$ of $L_G$ such that $\mu(\Ycal,\Zcal)=(-1)^{n-|\Xcal|}$. If $[\Ycal,\Zcal]$ is not an interval of this form, then $\mu(\Ycal,\Zcal)=0$.
\end{corollary}

Based on some small examples, we are inclined to believe that \cref{cor:mobius} is true even without the assumption that $L_G$ is a lattice.

\section{Open problems}\label{sec:other}


%Corollary~\ref{g-perm lattice cong} characterizes graphs $G$ for which $L_G$ is a meet-semilattice quotient of the weak order. 
A fundamental problem is to characterize all graphs such that $L_G$ is a lattice. To this end, we make the simple observation that an interval $L^{\pr}$ of a lattice $L$ is a sublattice of $L$. In particular if $G^{\pr}$ is any graph obtained by contracting or deleting vertices of $G$ such that $L_{\std(G^{\pr})}$ is not a lattice, then $L_G$ is not a lattice either. Continuing to borrow from matroid terminology, we say that $G^{\pr}$ is a \emph{minor} of $G$ if it is the standardization of a sequence of contractions and deletions.

\begin{problem}
  Give an explicit list of minors such that $L_G$ is a lattice whenever $G$ does not contain a minor from the list.
\end{problem}

By exhaustive search, we found that when $G$ is a connected graph with four vertices, the poset $L_G$ is not a lattice if and only if $\{1,3\}$ and $\{2,4\}$ are edges but $\{2,3\}$ is not an edge in $G$. These are the seven graphs shown in \cref{fig_nlex}.

\begin{figure}
  \centering
  \includegraphics{nlex}
  \caption{\label{fig_nlex}Graphs with four vertices such that $L_G$ is not a lattice.}
\end{figure}

%\subsection{Cyclohedra}\label{subsec:cycles}
%
%
%Let $C_n$ be the $n$-cycle graph, with vertices labeled $1,2,\ldots,n$ in cyclic order. The graph associahedron $P_{C_n}$ is known as a \emph{cyclohedron}. The cyclohedron is combinatorially equivalent to the \emph{Type $B_{n-1}$ associahedron} \cite{simion:2003typeB}. Its facial structure is usually described in terms of Type $B_n$ Coxeter-Catalan combinatorial objects, e.g. centrally symmetric triangulations of polygons. The graph associahedron $P_{C_n}$ does not have the same normal fan as the Type $B_{n-1}$ associahedron, however. This geometric distinction is relevant in many of its applications. The graph associahedron $P_{C_n}$ is used to study the self-linking of knots \cite{bott.taubes:1994self} or to tile the moduli space $\ov{Z}^n$ in \cite{devadoss:2002space}, whereas the Type $B_n$ associahedron arises in the theory of cluster algebras \cite{fomin.zelevinsky:2003clusterII}.
%
%From the Coxeter-Catalan point of view, the vertices of the Type $B_n$ associahedron can be partially ordered in several ways, which are called Cambrian lattices; \cite{reading:2006cambrian},\cite{thomas:2006tamari}. A \emph{Cambrian lattice} is a certain lattice quotient of the weak order of a finite Coxeter system. We remark that the poset of maximal tubings $L_{C_n}$ is not isomorphic to a Type $B_{n-1}$ Cambrian lattice for $n\geq 3$, despite the fact that they arise as orientations of the same undirected graph. Indeed, $L_{C_3}=L_{K_3}$ is the weak order of Type $A_2$, which is not isomorphic to any Cambrian lattice of Type $B_2$.
%
%Cambrian lattices have a remarkable structure: they are all semidistributive lattices \cite{reading:2006cambrian}. A lattice is \emph{semidistributive} if it satisfies a certain weakening of the distributive law.
%%for any three elements $x,y,z$, if $x\wedge z=y\wedge z$, then $(x\vee y)\wedge z=x\wedge z$ and the dual statement (where we swap the meet and join).
%%\begin{itemize}
%%\item if $x\wedge z=y\wedge z$, then $(x\vee y)\wedge z=x\wedge z$ and
%%\item if $x\vee z=y\vee z$, then $(x\wedge y)\vee z=x\vee z$.
%%\end{itemize}
%
%The weak order is known to be semidistributive, so when $G$ is filled, the poset $L_G$ inherits semidistributivity as a lattice quotient of the weak order. We do not know of a way to represent $L_{C_n}$ as a lattice quotient of the weak order for $n\geq 4$. In particular, the canonical map $\Psi_{C_n}:\Sfrak_n\ra L_{C_n}$ is not a lattice map as $C_n$ is not filled for $n\geq 4$. However, we have verified by computer calculation that $L_{C_n}$ is a semidistributive lattice for $n\leq 6$. This has led us to the following question.
%
%\begin{question}
%  Is $L_{C_n}$ a semidistributive lattice for each $n\geq 1$?
%\end{question}
%
%%We remark that the poset $L_G$ need not be semidistributive even when it is a lattice. For example, on may check that the star graph $G$ with $E(G)=\{\{1,2\},\{1,3\},\{1,4\}\}$ has a lattice of maximal tubings that is not semidistributive.
%
%%\acknowledgements{\lipsum[20]}
%
%%% 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}
