\documentclass[finalversion]{FPSAC2020}
\articlenumber{45}
\addbibresource{fpsac.bib}


\usepackage{fancyhdr} 
\usepackage{url,  mathrsfs}
\usepackage{amsmath}
\usepackage{graphicx,  epstopdf}
\usepackage{subfig}
\usepackage{color}
\usepackage{bbm}
\usepackage{subfloat}
\usepackage[draft]{fixme}
\usepackage{bm} 
\usepackage{bbm} 
\usepackage{epigraph}
\usepackage{endnotes}
\usepackage{ifpdf}
\usepackage{array}

\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{tikz}

\usepackage{xcolor}


%\newcommand{\Q}{\mathbb{Q}}
%\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
%\newcommand{\F}{\mathbb{F}}
%\newcommand{\C}{\mathbb{C}}
\newcommand{\ones}{\mathbbm{1}}
\newcommand{\hole}{	\includegraphics[width=0.5 \textwidth]{hole}}

\newcommand{\facets}{\operatorname{facets}}
\newcommand{\faces}{\mathcal{L}}
\newcommand{\N}{\mathcal{N}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\p}{\mathcal{P}}
%\newcommand{\nest}[2]{N(#1,#2)}
\newcommand{\nest}[2]{\mathcal{K}_{#1} #2} % args P, B


\newcommand{\danger}[1]{{\large\textcolor{red}{#1}}}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{definition}
\newtheorem{prob}[theorem]{Problem}
\newtheorem{sol}[theorem]{Solution}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

\received{\today}

\abstract{
	The graph associahedron is a simple polytope defined by associating a graph on $n+1$ vertices with the $n+1$ facets of a simplex in $n$ dimensions, and truncating the faces of the simplex corresponding to connected subgraphs. The faces of this new polytope correspond to a lattice of tubings of the graph.
	
	In this paper we generalize the graph associahedron by associating the vertices of graphs with the facets of simple polytopes, and truncating faces of the polytope based on connected subgraphs with restrictions. In the special case where the initial polytope is a hypercube, we examine connected subgraphs of graphs with positive and negative vertices. Certain graphs give us the permutahedron, the associahedron, the type $B_n$ permutahedron, and polytopes conjectured to be of bi-Catalan combinatorial type.
}

\keywords{polytopes, graph associahedra, nestohedra}


\begin{document}
	
	\title{Generalizing Nestohedra and Graph Associahedra for Simple Polytopes}
	\author{Jordan Almeter\thanks{\href{mailto:jgalmete@ncsu.edu}{jgalmete@ncsu.edu}.}\addressmark{1}}
	\address{\addressmark{1} Department of Mathematics, North Carolina State University, Raleigh, NC, USA}

	\maketitle
	
	\section{Introduction}
	
	The \emph{graph associahedron} ${\mathcal K}G$ for a graph $G$ on vertices $[n+1]$ is a polytope obtained by associating subsets of $[n+1]$ with faces of a simplex in $n$ dimensions, and truncating the faces associated with induced connected subgraphs. The lattice of faces of the graph associahedron is dual to the simplicial complex of tubings for $G$, where a tube is a connected proper subgraph of $G$ and a tubing is a collection of pairwise-compatible tubes [in a certain sense]. This polytope is well-studied, and is a generalization of the associahedron. The \emph{nestohedron} is a polytope generalizing the associahedron and graph associahedra. A \emph{building set} as defined by \cite{postnikov} is a set of subsets of $[n+1]$ with certain properties, and truncation of faces of the simplex in a certain order according to sets in the building set give nestohedra, as proven in the graph associahedron case by \cite{carrdevadoss}.
	
	This paper generalizes the notions of nestohedron and graph associahedron; instead of truncating faces of a simplex, we truncate the faces of any simple polytope~$\p$. We define \emph{$\p$-building sets} which generalize building sets, and define the \emph{$\p$-nestohedron} as the simple polytope resulting from truncating faces of $\p$ in the $\p$-building set.
Define a $\p$-graph as a graph obtained by removing edges from the facet adjacency graph of $\p$. For a $\p$-graph $G$, define the \emph{$\p$-graph associahedron} as the nestohedron obtained by truncating nonempty faces of $\p$ associated with connected induced subgraphs of $G$.
	
	In this paper we focus on the case where $\p$ is an $n$-dimensional hypercube. A hypercube-graph is a graph on vertices $\pm[n]$ without $(i,-i)$ edges. Tubes are subgraphs of $\pm[n]$ which induce connected subgraphs and which do not contain $\{i,-i\}$ as a subset; tubings are collections of tubes which satisfy pairwise-compatibility conditions. We consider several examples of hypercube-graph associahedra, which are isomorphic to the permutahedron, the associahedron, the type $B_n$ permutahedron, and a polytope conjectured to be related to bi-Catalan combinatorics, among others.

	During the final production of this extended abstract, the author found a paper containing an equivalent definition to the $\p$-nestohedron, in \cite{intervalstretching}. We are working to incorporate this research in our coming paper.
		
	
	\section{$\p$-Building Sets and $\p$-Nestohedra}
	
	Consider a simple, convex, full-dimensional polytope $\p$ in the vector space $\R^n$. The face lattice denoted by $\faces(\p)$ is the poset generated by faces of $\p$, ordered by inclusion. The set of facets is notated $\facets(\p)$. If $I$ is a subset of $\facets(\p)$, define $F_I$ to be the intersection $\bigcap_{F \in I} F$.
	
	\begin{definition} \label{buildingsetdefinition}
		A \emph{building set} $\B$ for the polytope $\p$ is a subset $\mathcal B \subseteq 2^{\facets(\p)}$ such that
		\begin{enumerate}
			\item For each $I \in \mathcal B$, the face $F_I$ is nonempty
			\item For two sets $I, J \in \mathcal B$ where $I \cap J \ne \emptyset$, if $F_I \cap F_J = F_{I\cup J}$ is nonempty, then $I \cup J \in \mathcal B$.
			\item For every facet $F \in \facets(\p)$, the singleton set $\{F\}$ is contained in $\mathcal B$.
		\end{enumerate}
	\end{definition}
	
	We may refer to a building set for a polytope $\p$ as a $\p$-building set for brevity.

	\begin{definition}
		A subset $N$ of a building set $\mathcal B$ is called nested or a nested set if:
		\begin{enumerate}
			\item The intersection $\bigcap_{I \in N} F_I$ is nonempty
			\item For any collection of sets $S_1, \ldots, S_k \in N$ such that for any $S_i, S_j$, $S_i \not\subseteq S_j$ and $k \ge 2$, their union $\bigcup_{i=1}^k S_i$ is not contained in $\B$.
		\end{enumerate}
	\end{definition}
	
	

	Sets $S_1, \ldots, S_k\in\B$ are called \emph{compatible} if $\{S_1,\ldots,S_k\}$ is a nested set.
	
	\begin{example}\label{runningexample}
		Consider a cube in three dimensions with pairs of opposing faces $\{-1,1\}$, $\{2,-2\}$, and $\{3,-3\}$. 
		The set $\B =\{\{1,2,3\},\{2,3,-1\},\{1,2\},\{2,3\},\{1\},\{2\},\{3\},\{-1\},\linebreak[0]\{-2\},\{-3\}\}$ is a valid building set. 	
		Some examples of nested sets in $\N(\B)$ are the set $\{\{1,2,3\},\{1\},\{3\}\}$, $\{\{1\},\{3\},\{-2\}\}$, and the empty set. The set $\{\{1\},\{3,-1\}\}$ is not nested because the face $F_{\{1,-1,3\}}$ is empty, and the set $\{\{1\},\{2\},\{-3\}\}$ is not nested because $\{1\} \cup \{2\} =\{1,2\} \in \B$.
	\end{example}

		
	\begin{definition}
		Given a $\p$-building set $\B$, let $\N(\B)$ be the poset of nested sets ordered by reverse inclusion. Let $\overline{\N}(\B)$ be the poset, $\N(\B)\cup \{\B\}$, again ordered by reverse inclusion. Because $\B$ is not a nested set, but contains every other nested set as a subset, $\overline{\N}(\B)$ is obtained by adding an element $\hat{0}$ to $\N(\B)$.
	\end{definition}
	
	
	\begin{definition}
	    Given a polytope $Q$ with a proper nonempty face $F$, there exists a hyperplane $H=\{x:ax = c\}$ defining a halfspace $H^-=\{x:ax \le c\}$ such that $F \subset \R^n \backslash H^-$, and all vertices of $Q \backslash F$ lie in $H^-$. The hyperplane $H$ is the truncating hyperplane, and the polytope $H^- \cap Q$ is the polytope obtained by \emph{truncating} $Q$ by the face $F$.
	\end{definition}

	\begin{definition} \label{nestohedrondefinition}
	    Consider a building set $\B$ for a simple polytope $\p$ and a linear ordering $S_1, \ldots, S_k$ of $\B$, such that $S_i \supset S_j$ implies $i \le j$.
		The \emph{nestohedron of $\B$ on $\p$} is the polytope \\${Trunc((S_1,\ldots,S_k),\p)}$. We denote this polytope $\nest{\p}{\B}$.
	\end{definition}

	\begin{example}
		\cref{truncationexample} shows the construction of a cube-nestohedron, or the nestohedron defined by a building set on the cube.
	\end{example}

		The following theorem validates the notation $\nest{\p}{\B}$ by showing that any choice of ordering of $\B$ satisfying conditions given in \cref{nestohedrondefinition} gives us the same polytope up to combinatorial isomorphism.
		


	\begin{figure}%[h]
		\centering
		\includegraphics[width=0.75\textwidth]{runningexample.pdf}
		\caption{An example of a nestohedron generated from a cube by the building set $\B$ from \cref{runningexample}. First the corners $F_{1,2,3}$ and $F_{2,3,-1}$ are truncated, and then the edges $F_{1,2},F_{2,3},F_{3,-1}$ are truncated. Truncating a facet does not change the face lattice.}
		\label{truncationexample}
	\end{figure}
	

	
	\begin{theorem}
		\label{maintheorem}
		The face lattice of $\nest{\p}{\B}$ is isomorphic to the poset $\overline{\mathcal N}(\mathcal B)$.
	\end{theorem}

		The notion of a $\p$-building set defined in this paper is a special case of the definition of a building set for lattices, defined in \cite{feichtner2003} and here called a lattice building set. We use results from \cite{feichtner2003} to prove \cref{maintheorem}.



	\begin{definition}[{\cite[Definition 2.2]{feichtner2003}}]
		A \emph{lattice building set} for a lattice $L$ is a set $G \subseteq L\backslash \hat{0}$ such that, for any element $x \in L\backslash \hat{0}$, the set $\max \{g \in G: g \le x\}=\{g_1,\ldots,g_k\}$ has the property that the interval $[\hat 0,x]$ is isomorphic to the product of intervals $\prod_{i=1}^k[\hat 0,g_i]$ by the lattice isomorphism mapping $(0,\ldots,g_i,\ldots,0)$ to $g_i$.
	\end{definition}

	\begin{proposition}
		Given a simple polytope $\p$, if a set $\B$ is a $\p$-building set, then $\B \cup \hat{1}$ is a lattice building set of the dual face lattice of $\p$.
	\end{proposition}

	\begin{proof}
		If $L$ is the dual face lattice of $\p$ and $\B$ is a building set, then for any set $S$ corresponding to a nonempty face $F_S$, the set $\B_{max \le F_S}$ is the set of faces $F_{S_1},F_{S_2},\ldots, F_{S_k}$ where $S_1, \ldots, S_k$ is a partition of $S$. Because $L$ is simplicial, $[0,F_{S}]=\prod_{i=1}^k[0,F_{S_i}]$. As a result, $\B \cup \{\hat{1}\}$ is a lattice building set.
	\end{proof}

	\begin{definition}[{\cite[Definition 2.7]{feichtner2003}}]
		A \emph{lattice-nested set} is a subset of a building set $N\subset G$ such that, for any antichain $\{x_1, \ldots, x_n\} \subset N$, the join $x_1 \vee \cdots \vee x_n$ is not in $G$.
	\end{definition}
		
	If an intersection of faces is empty, then their join in the dual face lattice is $\hat{1}$. The following proposition is then trivial:

	\begin{proposition}
		For a building set $\B$ of a simple polytope $\p$, every set $N\subset \B$ is nested under $N \subset \B$ if and only if it is a lattice-nested set of the dual face lattice of $\p$ under lattice-building set $\B \cup\{\hat{1}\}$.
	\end{proposition}

	The following proposition describes a \emph{combinatorial blow-up} $\textrm{Bl}_xL$; it is a generalization of stellar subdivision. When $L$ is dual to the face lattice of a simple polytope $\p$, the combinatorial blowup of a face $F$ is dual to the face lattice of the truncation of $\p$ at face $F$ \cite{intervalstretching}. The following result proves \cref{maintheorem}.

	\begin{theorem}[{\cite[Theorem 3.4]{feichtner2003}}]
		Given a lattice $L$ with building set $G$, and some linear extension $G=\{G_1,\ldots, G_t\}$ with $G_i > G_j$ implying $i < j$,  the simplicial complex of lattice nested sets under $G$ is isomorphic to the combinatorial blow-up $\textrm{Bl}_{G_t}(\textrm{Bl}_{G_{t-1}}(\cdots\textrm{Bl}_{G_1}L))$.
	\end{theorem}

	
	In the case where $\p$ is a simplex, we recover the definition of building sets for simplices as described in \cite[Section 7]{postnikov}.
	
	\begin{proposition} \label{generalizenestohedron}
		For a simplex $\Delta$, a set $\B\subseteq 2^{\facets{\Delta}}$ with $\facets{\Delta} \notin \B$ is a building set if and only if it is a $\Delta$-building set. A $\Delta$-nestohedron is a nestohedron as defined in \cite{postnikov}.
	\end{proposition}

	
	\subsection{Graphical $\p$-Building Sets and $\p$-Graph Associahedra}
	
	In this section, we provide the definition of the graph associahedron on the simplex, which has been explored before, and then define its generalization, the $\p$-graph associahedron. We then prove the graph associahedron on the simplex is in fact a special case of the $\p$-graph associahedron.
	
	Given a graph $G_\Delta$ on $n+1$ vertices, we can define the graphical building set $\B_{G_\Delta}$ as the set of proper subsets $S \subset [n+1]$ such that the induced graph $G_\Delta|_S$ is connected. The nestohedron of the simplex generated by $\B_{G_\Delta}$ is the \emph{graph associahedron}. This definition is in line with \cite{postnikov} and \cite{carrdevadoss}.
	
	In graph associahedron terminology, \emph{tubes} of $G_\Delta$ are defined as sets in $\B_{G_\Delta}$, and \emph{tubings} are defined as nested sets of $G_\Delta$. Compatibility is defined such that $t_1, t_2 \in \B_G$ are compatible if and only if $t_1 \subset t_2, t_2 \subset t_1$, or $t_1, t_2$ are disjoint and $t_1 \cup t_2$ is neither a tube nor the set $[n+1]$. A set is nested if and only if its support is a proper subgraph and all tubes are pairwise compatible.
	
	While the vertices of a graph in a graph associahedron can be easily associated with facets of a simplex, we need to define a special type of graph to associate the facets of a polytope $\p$ with vertices of a graph.
	
	\begin{definition}
		The \emph{facet adjacency graph} is a graph whose vertices are facets of $\p$, with an edge between two facets $i,j$ if and only if $i, j$ intersect. Any graph $G$ which can be obtained by deleting edges from the adjacency graph of a polytope $\p$ is called a \emph{$\p$-graph}, or a \emph{graph on $\p$}.
	\end{definition}
	
	For any $\p$-graph we can define the following building set:
	
	\begin{proposition}
		The set $\B_G$ for a graph $G$ on a simple polytope $\p$ is the set of subsets $S \subset \facets(\p)$ such that $F_S$ is nonempty and $G|_S$ is a connected graph. This set is a $\p$-building set, called the \emph{graphical $\p$-building set}.
	\end{proposition}

	\begin{proof}
		The set $\B_G$ satisfies parts 1 and 3 of \cref{buildingsetdefinition}. When two sets $I_1, I_2 \in \B_G$ intersect, the set $I_1 \cup I_2$ induces a connected graph, and if $F_{I_1 \cup I_2}$ is nonempty, then $I_1 \cup I_2 \in \B_G$, satisfying part 2 of the definition.
		\end{proof}
	
	\begin{definition}
		The \emph{graph associahedron} for a graph $G$ on a simple polytope $\p$ is the nestohedron on $\p$ generated by the $\p$-building set $\B_G$. We can call this the $\p$-graph associahedron, and use the notation $\nest{\p}{G}$.
	\end{definition}

	The following is an application of \cref{generalizenestohedron}.
	
	\begin{corollary}
		Consider an $n$-dimensional simplex $\Delta_n$ and a $\Delta_n-$graph $G$. Then the $\Delta_n$-graph associahedron $\nest{\Delta_n}{\B_G}$ is exactly the graph associahedron.
	\end{corollary}

		
	Because nested sets for a graphical $\p$-building set generalize graph tubings, we can use the following terminology for graph associahedra on any polytope:
	
	\begin{definition}
		Given a $\p$-graph $G$, all sets in the graphical $\p$-building set are called \emph{tubes}, and all nested sets are called \emph{tubings}. Two tubes $t_1, t_2$ are \emph{compatible} if $F_{t_1 \cup t_2}$ is nonempty and either $t_1 \subset t_2, t_2 \subset t_1$, or $t_1, t_2$ are disjoint and non-adjacent.
	\end{definition}

			

	\begin{proposition}
		A tubing $T = \{t_1,\ldots, t_k\}$ of a $\p$-graph is valid if and only if all tubes in $T$ are nonempty and, given their support $U=\bigcup_{t \in T} t$, the face $F_U$ is nonempty.
	\end{proposition}

	\section{Hypercube-Graph Associahedra}

	Define the $n$-dimensional hypercube, or $n$-cube, $C_n = \{x\in\R^n|-1 \le x_i \le 1\}$, and label the $2n$ facets with numbers in $\pm[n]$, such that $i$ is associated with the $x_i \le 1$ facet and $-i$ is associated with the $-x_i \le 1$ facet. $C_n$ is a simple polytope. Each facet $i$ intersects with every other facet except for $-i$, and a set of facets $S \subseteq \pm[n]$ has a nonempty intersection if and only if $S$ does not contain a subset of the form $\{i,-i\}$.
	
	As a result, the facet adjacency graph of the hypercube is the graph on $\pm[n]$ where every vertex $i$ is adjacent to every other vertex except for $-i$. A hypercube-graph is then any graph on $\pm[n]$ without any $(i,-i)$ edges. The following propositions are immediate:
	
	\begin{proposition}
		A tube $t$ of a graph $G$ on an $n$-dimensional hypercube is any subset of $\pm[n]$ which induces a connected graph in $G$ and such that $\{i,-i\} \not\subseteq t$ for any $i \in \pm[n]$.
	\end{proposition}

	
	
	\begin{proposition}
		Two tubes $t_1, t_2$ are compatible if $\{i,-i\} \not\subseteq t_1 \cup t_2$ for any $i \in \pm[n]$, and one of the following is true:
		\begin{enumerate}
			\item Either $t_1 \subset t_2$ or $t_2 \subset t_1$,
			\item $t_1, t_2$ are disjoint, and $t_1 \cup t_2$ induces a disconnected graph in $G$.
		\end{enumerate}
	
		In the hypercube case, a set of tubes is a valid tubing if and only if all tubes are pairwise compatible.
	\end{proposition}

	While the choice of truncating hyperplanes in \cref{nestohedrondefinition} does not impact the face lattice of the nestohedron, we choose a standard set of normal vectors to the truncating hyperplanes for the hypercube graph associahedron as follows.
		
	\begin{definition} \label{weightvectors}
		Given a tube $t$, define the \emph{weight vector} $w_t\in \{-1,0,1\}^n$ as the vector in $(\R^n)^*$such that $w_t(i)=1$ if $i \in t$, $w_t(i)=-1$ if $-i \in t$, and $w_t(i)=0$ otherwise.
	\end{definition}

	\begin{remark} 
		This definition of weight vector coincides with a notion of fundamental weights used in root systems. Given a set of simple roots, the fundamental weights are dual to the coroots associated with the simple roots. Up to scaling, the orbit of a set of fundamental weights in the type $B_n$ root system are vectors of the form $\{-1,0,1\}^n$, which are exactly the possible weight vectors of the hypercube-graph.
	\end{remark}

	
	
	\begin{proposition}
		For every tube $t$ in an $n$-cube graph $G$, there exists an inequality of the form $w_t x \le |t|-\epsilon$ which truncates the face $F_t$.
	\end{proposition}
	
	The choice of $\epsilon$ when repeatedly truncating a hypercube must be made such that cuts are not made too deep. The following realization is motivated by the construction provided in \cite{realization}. The proof of \cref{myrealization}, which gives a recursive formula for the coordinates of vertices, is omitted from this abstract due to length.
	
	\begin{theorem}
		A realization of the $n$-cube-graph associahedron $G$ whose vertices are vectors with integer coefficients can be defined by the linear inequalities
		\[\{w_t \cdot x \le |t| 3^{n-1} - \left\lfloor 3^{|t|-2}\right\rfloor : \textrm{$t$ is a tube in $G$}\}.\]\label{myrealization}
	\end{theorem}
	
	The following theorem regarding the facets of the hypercube-graph associahedron is based on work from \cite{carrdevadoss}, and specifically adapts \cite[Theorem 2.9]{carrdevadoss} for the hypercube case. 
		\begin{definition}
		The reconnected complement $G_t^*$ for a hypercube-graph $G$ is the graph obtained by removing the vertices $t\cup -t$ from $G$ and adding an edge between two vertices $a,b$ if either $\{a,b\}$ or $\{a,b\}\cup t$ is connected.
	\end{definition}
	This graph differs from the usual reconnected complement graph for the simplex-graph, as in addition to removing the vertices in $t$, we are removing the vertices in $-t$. The reconnected complement of the hypercube graph is a hypercube graph on an $(n-|t|)$-cube graph, and so the hypercube-associahedron $\nest{}{G_6^*}$ is $(n-|t|)$-dimensional.
	
	Define $G_t$ to be the graph induced by the tube $t$. Treat this graph as a simplex-graph, and the graph associahedron $\nest{}{G_t}$ is $(|t|-1)$-dimensional.

	\begin{theorem}
		Given a $C_n$-cube graph $G$ with tube $t$, the facet of $\nest{C_n}{G}$ associated with the tube $t$ is isomorphic to the product $\nest{\Delta_{|t|-1}}{G_t} \times \nest{C_{n-|t|}}{G_t^*}$. \label{reconnectedcomplement}
	\end{theorem}

	\begin{proof}
		There is a trivial bijection between tubes of $G_t$ and tubes of $G$ contained in $t$.
		
		Consider the map $\rho$ from the set of tubes of $G_t^*$ to the set of tubes compatible with $t$ but not contained in $t$, defined as
		
		\[
			\rho(t') =
			\begin{cases}
				t'\cup t & \textrm{If $t'\cup t$ is connected in $G$} \\
				t' & \textrm{otherwise.}
			\end{cases}
		\]
		
		This map is a bijection. Upon inspection, two tubes $t',t''$ are compatible if and only if $\rho(t'), \rho(t'')$ are compatible. Extending $\rho$ to a mapping on tubings induces a poset isomorphism between tubings of $G_t^*$ and tubings of $G$ not containing any subset of $t$ as an element. Finally, the map $p:\overline\N(\B_{G_t}) \times \overline\N(\B_{G_t^*}) \to \overline\N(\B_{G})$ defined as $p(T,T^*) = \{t\}\cup T \cup \rho(T')$ is an isomorphism, proving \cref{reconnectedcomplement}.
		\end{proof}
	
	\begin{corollary}
		Every face of a hypercube graph associahedron is isomorphic to the product of either a set of simplex-graph associahedra, or a lower-dimensional hypercube graph-associahedron and a set of simplex-graph associahedra.
	\end{corollary}

	\begin{conjecture} \label{minkowskisum}
		Any non-connected $\p$-graph associahedron is combinatorially isomorphic to the Minkowski sum of the graph associahedra of its corresponding subgraphs.
	\end{conjecture}

	
	\section{Special Cases of Hypercube-Graph Associahedra}
	
	\begin{figure}[h]
		\centering
		\includegraphics[width=0.75\textwidth]{diagramsource/FPSAC_Graph_2.pdf}
		\caption{Notable hypercube graphs for the $4$-dimensional hypercube. The top left graph has vertices labeled with members of $\pm[4]$, with dashed lines connecting vertices corresponding to opposing facets; these are not actual edges in the hypercube graph. From top left to bottom right: an empty graph, a full adjacency graph, a $2K_n$ graph, a single path graph, a double path graph, the $G_n$ Pell graph, the $H_n$ companion Pell graph, and a single $K_n$ graph.}
		\label{graphs}
	\end{figure}

	\begin{figure}[h]
		\centering
		\includegraphics[width=0.7\textwidth]{diagramsource/firstfour3d.png}
		\caption{Examples of hypercube-graph associahedra in $3$ dimensions. The graphs here are the full adjacency graph, the $2K_n$ graph, the single path graph, and the double path graph.}
		\label{examples3d}
	\end{figure}
	
	This section details the properties of hypercube graph associahedra for special graphs. \cref{graphs} shows a list of noteworthy graphs for the case $n=4$ for reference, while \cref{examples3d} shows the $3$-dimensional realizations of some of these graphs.
	
	
	
	\subsection{Full Adjacency Graph and the type $B_n$ permutahedron}
	
	Suppose $G$ is the adjacency graph of the facets of a hypercube in $n$ dimensions; this is the graph on vertices $\pm [n]$ with edges between $i,j$ if $i \ne -j$. This is the most edges a hypercube-graph can have.
	
	
	The type $B_n$ permutahedron as the orbit of a generic point under the type $B_n$ reflection group; this is equivalent to the convex hull of all permutations of a point $(\pm p_1, \ldots, \pm p_n)$ for distinct nonzero values $p_1, \ldots, p_n$.
	
	\begin{proposition} \label{typeBPermutahedron}
		The graph associahedron on the hypercube for the full adjacency graph of the hypercube is the type $B_n$ permutahedron.
		\end{proposition}
	
	\begin{proof}
		The construction given in \cref{myrealization} for the full adjacency graph gives the orbit of the point $(3^{n-1}, 3^{n-1}-1,\ldots, 3^{n-1}-3^{n-2})$.
		\end{proof}
	
	\subsection{$2K_n$ Graphs and the type $A_n$ permutahedron}
	
	Define the \emph{$2K_n$ graph} to be the graph on a hypercube consisting of a complete graph on $[n]$ and a complete graph on $[-n]$.
	
	The type $A_n$ permutahedron is the orbit of a generic point under the type $A_n$ reflection group; it is also the graph associahedron of the complete graph $K_{n+1}$ on an $n$-dimensional simplex.
	
	\begin{proposition}
		The hypercube graph associahedron of the $2K_n$ graph is combinatorially isomorphic to the type $A_n$ permutahedron.
	\end{proposition}
	
	\begin{proof}
		
		There exists an isomorphism between the complex of graph tubings on the $2K_n$ hypercube-graph, and the set of graph tubings on the complete $K_{n+1}$ simplex-graph. Consider a tube $t$ in the $2K_n$ graph. This tube is either a subset of $[n]$ or a subset of $-[n]$. If $t\subset [n]$, then define $\phi(t) = t$. If $t \in -[n]$, define $\phi(t) = ([n] \backslash |t|) \cup \{n+1\}$, where $|t|=\{|i|:i\in t\}$. If $t \subset t'$ then $\phi(t)\subset \phi(t')$ or $\phi(t') \subset \phi(t)$. If $t,t'$ are disjoint but compatible, with $t'\subset-[n]$, then $t \subseteq [n] \backslash |t'|$, and we find that $\phi(t) \subset \phi(t')$.
		
		As compatibility is preserved, this is an isomorphism between the nested complex of the $2K_n$ hypercube graph associahedron and the nested complex of the $K_{n+1}$ simplex graph associahedron.
		\end{proof}
	
		As an aside, this particular construction appears independently in another paper:
	
	\begin{proposition}
		The graph associahedron for the $2K_n$ graph on the hypercube is identical to the graph multiplihedron for the complete graph as defined in  \cite{multiplihedron}.
	\end{proposition}
	
	
	
	\subsection{Single Path Graph and the Type $A_n$ associahedron}
	
	Define the \emph{single path graph} to be the hypercube graph consisting of a path on the vertices $1, 2, \ldots, n$. We know that the type $A_n$ associahedron is the simplex graph associahedron for the path graph on $n+1$ vertices, and we find the following result:
	
	\begin{proposition}
		The hypercube graph associahedron of the single path graph is combinatorially isomorphic to the type $A_n$ associahedron.
	\end{proposition}

		\begin{proof}We prove that the normal fan is equal to the type $A_n$ linear cluster fan. The simple roots of the type $A_n$ fan are of the form $\alpha_{1}, \ldots, \alpha_n$, and the almost positive roots are of the form $-\alpha_i$ and $\beta_{j,k}=\sum_{i=j}^k \alpha_k$. Describing the rules found in \cite{marsh2002generalized}, with a linear deformed Coxeter element $\tau=\sigma_1\cdots\sigma_n$, we find that negative root $-\alpha_i$ is compatible with other negative roots, and $-\alpha_i, \beta_{j,k}$ are compatible if and only if $i \notin [j,k]$. In addition, roots $\beta_{i,j}$ and $\beta_{k,l}$ with $i \le k$ are compatible if and only if $i=k$, or $i<k$ and $j \notin [k+1,l+1]$. With a bijection between the roots $\beta_{i,j}$ and tubes $[i,j]$, and $-\alpha_i$ and tubes $\{-i\}$, we find that this compatibility relation is isomorphic to the compatibility relation that $-i$ and $[j,k]$ are compatible if and only if $i \notin [j,k]$, and two intervals $[i,j], [k,l]$ are compatible if and only if they are either nested, or if they are disjoint, and $[i+1,j+1]\cap [k,l]=[i,j]\cap[k+1,l+1]=\emptyset$, which we see is equivalent to not being adjacent.\end{proof}

	
	\subsection{Double Path graph and Coxeter Bi-Catalan Combinatorics}
	
	Define the \emph{double path graph} to be the hypercube graph which consists of a path from $1$ to $n$ and a path from $-1$ to $-n$.
	
	\begin{proposition}\label{doublepathprop}
		There are ${2n \choose n}$ maximal tubings of the double path graph on the hypercube, which are in bijection with north-east lattice paths.
	\end{proposition}

	\begin{proof}
		Given a $k$-vertex path graph, there exists a bijection $\phi_k$ between maximal tubings and Dyck paths above the diagonal from $(0,0)$ to $(k,k)$.
		
		Every maximal tubing of a double path graph on $\pm[n]$ partitions the set $[n]$ into positive and negative vertices. The components of the tubing are paths $P_1, \ldots, P_k$ with sizes $p_1, \ldots, p_k$, alternating between positive and negative vertices, as shown in \cref{dp}.
		
		Define the map $\phi$ from tubings of the double path graph to north-east lattice paths. Define $\phi$ to be the concatenation of paths $\phi'_{p_1} (P_1), \ldots, \phi'_{p_k}(P_k)$, where $\phi'_k (P) = \phi_k(P)$ if $P$ is a tubing on $k$ positive vertices, and if $P$ is a path on negative vertices, then $\phi'_k(P)$ is the mirror image path of $\phi_k(P)$ obtained by replacing north steps with east steps and vice-versa. This map is a bijection, as every lattice path can be decomposed into a series of Dyck paths depending on where the path crosses the diagonal.
		\end{proof}

	
	\begin{figure}[h]
		\centering
		\includegraphics[width=0.75\textwidth]{FPSAC_doublepath.pdf}
		\caption{An example of a tubing of a double path graph on 7 vertices, along with an associated north-east lattice path.}
		\label{dp}
	\end{figure}

	The linear bicluster fan is the bicluster fan of the linear Coxeter element in the type $A_n$ Coxeter group, as defined in \cite{barnard}. It is the common refinement of the linear cluster fan and its antipodal inverse. The following conjecture is a direct result from \cref{minkowskisum}.

	\begin{conjecture}
		The normal fan to the double-path hypercube-graph associahedron is the linear bi-cluster fan of type $A_n$. 
	\end{conjecture}
	
	
	
	\subsection{Single $K_n$ Graph and the Stellohedron}
	
	Define the \emph{single $K_n$ graph} to be the graph on the hypercube consisting of the complete graph $K_n$ on vertices in $[n]$, and vertices in $-[n]$ as isolated vertices. The \emph{stellohedron} is the graph associahedron of the complete bipartite $K_{n,1}$ graph. It is mentioned in \cite{postnikovfaces}.
	
	\begin{proposition}
		The hypercube graph associahedron for the single $K_n$ graph is isomorphic to the stellohedron.
	\end{proposition}
	
	\begin{proof}
		Tubes on positive vertices of this graph must be contained in each other to be compatible, and each tube in a maximal tubing contains exactly one vertex contained in no smaller tube. As a result, a tubing gives an ordering of the positive vertices contained in the tubing. The negative tubes are all singletons. As a result, a tubing partitions $[n]$ into two sets and associates an ordering on one of the subsets. This establishes a bijection between arrangements of $[n]$ and tubings of the single $K_n$ graph.
	\end{proof}


	\subsection{Pell Numbers and Companion Pell Numbers}
	
	Define the graph $G_n$ on $\pm[n]$ containing edges $(i,-(i+1))$ for $1 \le i < n$. Define the graph $H_n$ as the graph $G_n$ with added edge $(-1,n)$. Examples are shown in \cref{pellgraphs}.
	
	\begin{figure}
		\centering
		\includegraphics[width=.8\textwidth]{diagramsource/pell_graphs.pdf}
		\caption{$G_5$ on left and $H_5$ on right.}\label{pellgraphs}
	\end{figure}
	
	\begin{theorem}
		The number of tubings of the $G_n$ graph is the $n$th Pell number \cite[Sequence A002203]{oeis} The number of tubings of the $H_n$ graph is the $(n+1)$th companion Pell number \cite[Sequence A002203]{oeis}.
	\end{theorem}
	
	In \cite{sashes}, there is a lattice of sashes which corresponds to the weak order on Pell permutations. The following conjecture has been confirmed for $n\le 7$:
	
	\begin{conjecture}
		The $1$-skeleton of the graph associahedron for $G_n$, ordered by the functional $(1,\ldots,n)$ on $\R^n$, gives the lattice of Pell permutations under weak order.
	\end{conjecture}
	
	\printbibliography

\end{document}
