%% otherwise options taken by the article class will be accepted
\documentclass[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{62}
\addbibresource{62.bib}

\usepackage{tikz}

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newcommand{\NC}{\mathcal{NC}}
\newcommand{\NBB}{\mathcal{NBB}}
\newcommand{\NBC}{\mathcal{NBC}}
\newcommand{\NCNBC}{\mathcal{NCNBC}}
\newcommand{\cover}{\lessdot}
\renewcommand{\c}{\mathbf{c}}
\usepackage{lipsum}

%% define your title in the usual way
\title[Noncrossing Bond Poset]{The Noncrossing Bond Poset of a Graph}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{C. Matthew Farmer\addressmark{1}\thanks{\href{mailto:cmfarmer@uncg.edu}{cmfarmer@uncg.edu}} \and Joshua Hallam\addressmark{2}\thanks{\href{mailto:joshua.hallam@lmu.edu}{joshua.hallam@lmu.edu}}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, The University of North Carolina at Greensboro \\ \addressmark{2}Department of Mathematics, Loyola Marymount University}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
\revised{\today}

%% 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$ with vertices labeled by $\{1,2\dots, n\}$, the bonds of $G$ are in natural bijection with the set partitions of $n$.     We say a bond is \emph{noncrossing} if its associated partition is noncrossing.  Ordering the noncrossing bonds of $G$ by inclusion, one gets a noncrossing analogue of the bond lattice of $G$ called the \emph{noncrossing bond poset}.   In this extended abstract we study this poset showing that several  properties of the bond lattice have analogues in the noncrossing bond poset. 
}

%% 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{posets, graphs, noncrossing partitions, M\"obius function, bond lattice}

%% 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{NonCrossingBondPosetFPSAC2019.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}
The \emph{partition lattice}, $\Pi_n$, consists of set partitions of $[n]:=\{1,2,\dots, n\}$ ordered by refinement.  It has several nice combinatorial properties including being supersolvable and shellable.  By removing the crossing partitions from the partition lattice, one gets another lattice called the \emph{noncrossing partition lattice}.  It too has many nice combinatorial properties. For example, it is supersolvable, rank symmetric, has a Catalan number of elements, and its M\"obius value  is a Catalan number.  See Simion's survey article~\cite{s:np} for more information about the noncrossing partition lattice.

Now suppose that $G$ is a graph on $[n]$.  We can think of the bond lattice of $G$ as a subposet of $\Pi_n$.  We do this by restricting to the set of partitions in $\Pi_n$ such that for each block $B$ in the partition, the induced subgraph of $G$ with vertex set $B$ is connected.  For example, if  $G$ is the path $1-2-3$, the partition $12/3$ is in the bond lattice, but $13/2$ is not since there is no edge between $1$ and $3$. Using this idea, one can see that $\Pi_n$ is the bond lattice for the complete graph.  In general, the bond lattice of $G$ carries important combinatorial  information about the graph.   For example, it encodes exactly the same information as the cycle matroid associated to the graph.  Moreover, its characteristic polynomial is (essentially) the chromatic polynomial of the graph.  See~\cite[\S 2]{s:iha} for background on bond lattices.    Since the partition lattice is the bond lattice of the complete graph, one can consider the noncrossing partition lattice as a noncrossing version of a bond lattice.  It is this idea that is the starting point for our work. 




In the next section, we  explicitly define the noncrossing bond poset of a graph and describe some of its structural properties including necessary and sufficient conditions on the graph which guarantee that its noncrossing bond poset is a lattice.  \cref{perfectlyLabeledSec} is focused on the family of perfectly labeled graphs.  We show that in this setting, the noncrossing bond poset is shellable and when it is a lattice, it is supersolvable.  This is done using edge labelings.  In \cref{MobSec}, we use Blass and Sagan's work~\cite{bs:mfl} on NBB sets to give a combinatorial interpretation for the M\"obius function and the characteristic polynomial of the noncrossing bond poset of a  family of graphs.    We finish with a brief discussion of an  action of the dihedral group.






\section{The Structure of the  Noncrossing Bond Poset}\label{structOfPosetSec}
  We assume the reader is familiar with some basic graph theory concepts (see~\cite[Graph Theory Appendix]{s:EC1} for any undefined terms) as well as basic concepts related to posets (see~\cite[\S 3]{s:EC1} for background and notation).   Let $G$ be a graph. For the remainder of this paper, unless otherwise noted, we will assume that the vertex set of $G$ is $[n]$. We will use the notation $V(G)$ for the vertex set of $G$ and $E(G)$ for the edge set of $G$.   When we write out edges, we will write them in the form $ij$ where $i<j$.   Moreover, we will always draw our graphs so that the vertices lie on a circle with vertex $1$ at the top and the remaining vertices appearing in clockwise order around the circle. Edges will always be drawn so that they are  the line segments between their endpoints. We will refer to this as the \emph{graphical representation of $G$}.   We say that two edges of $G$ \emph{cross} if their respective line segments intersect in the graphical representation.  See \cref{graphFig} for several  examples of  graphical representations.




\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=.7]
\coordinate (v1) at (0,1);
\coordinate (v2) at (.87,.5);
\coordinate (v3) at (.87,-.5);
\coordinate (v4) at (0,-1);
\coordinate (v5) at (-.87,-.5);
\coordinate (v6) at (-.87,.5);


\draw[thick] (v6)--(v1) -- (v2) -- (v3)--(v5);
\draw[thick] (v5)--(v6);
\draw[thick] (v1) -- (v4);

\foreach \v in {v1,v2,v3,v4, v5,v6} \fill(\v) circle (.1);
\draw(0,1.4) node{\footnotesize 1};
\draw (.87+.4,.5+.4) node{\footnotesize 2};
\draw(0,-1.4) node{\footnotesize 4};
\draw (.87+.4,-.5-.4) node{\footnotesize 3};
\draw (-.87-.4,-.5-.4) node{\footnotesize 5};
\draw (-.87-.4,.5+.4) node{\footnotesize 6};
\draw(0,-2.2) node {\large $G$};


\begin{scope}[shift = {(4, 0)}]

\coordinate (v1) at (0,1);
\coordinate (v2) at (.87,.5);
\coordinate (v3) at (.87,-.5);
\coordinate (v4) at (0,-1);
\coordinate (v5) at (-.87,-.5);
\coordinate (v6) at (-.87,.5);


\draw[thick] (v1) -- (v2) -- (v3) --(v5);
\draw[thick] (v1) -- (v4);

\foreach \v in {v1,v2,v3,v4, v5,v6} \fill(\v) circle (.1);
\draw(0,1.4) node{\footnotesize 1};
\draw (.87+.4,.5+.4) node{\footnotesize 2};
\draw(0,-1.4) node{\footnotesize 4};
\draw (.87+.4,-.5-.4) node{\footnotesize 3};
\draw (-.87-.4,-.5-.4) node{\footnotesize 5};
\draw (-.87-.4,.5+.4) node{\footnotesize 6};
\draw(0,-2.2) node {\large $H$};


\end{scope}




\begin{scope}[shift = {(8, 0)}]

\coordinate (v1) at (0,1);
\coordinate (v2) at (.87,.5);
\coordinate (v3) at (.87,-.5);
\coordinate (v4) at (0,-1);
\coordinate (v5) at (-.87,-.5);
\coordinate (v6) at (-.87,.5);


\draw[thick] (v3) --(v5)--(v6);
\draw[thick] (v1) -- (v4);
\draw[thick] (v3) -- (v5);
\draw[thick] (v1) -- (v6)--(v5);

\foreach \v in {v1,v2,v3,v4, v5,v6} \fill(\v) circle (.1);
\draw(0,1.4) node{\footnotesize 1};
\draw (.87+.4,.5+.4) node{\footnotesize 2};
\draw(0,-1.4) node{\footnotesize 4};
\draw (.87+.4,-.5-.4) node{\footnotesize 3};
\draw (-.87-.4,-.5-.4) node{\footnotesize 5};
\draw (-.87-.4,.5+.4) node{\footnotesize 6};
\draw(0,-2.2) node {\large $H'$};


\end{scope}

\begin{scope}[shift = {(12, 0)}]

\coordinate (v1) at (0,1);
\coordinate (v2) at (.87,.5);
\coordinate (v3) at (.87,-.5);
\coordinate (v4) at (0,-1);
\coordinate (v5) at (-.87,-.5);
\coordinate (v6) at (-.87,.5);


\draw[thick] (v1) -- (v2) -- (v3)--(v5)--(v6);
\draw[thick] (v1) -- (v4);

\foreach \v in {v1,v2,v3,v4, v5,v6} \fill(\v) circle (.1);
\draw(0,1.4) node{\footnotesize 1};
\draw (.87+.4,.5+.4) node{\footnotesize 2};
\draw(0,-1.4) node{\footnotesize 4};
\draw (.87+.4,-.5-.4) node{\footnotesize 3};
\draw (-.87-.4,-.5-.4) node{\footnotesize 5};
\draw (-.87-.4,.5+.4) node{\footnotesize 6};
\draw(0,-2.2) node {\large $H''$};


\end{scope}



\end{tikzpicture}
\end{center}
\caption{A graph and several subgraphs \label{graphFig} }
\end{figure}




A subgraph of a graph $G$ is called \emph{spanning} if it contains all the vertices of $G$. Note that when considering spanning subgraphs of $G$, it is enough to just know the edges which appear in the subgraph.  Because of this, we will often make no distinction between subsets of $E(G)$ and spanning subgraphs of $G$.    A subgraph $H$ of a graph $G$ is called \emph{induced} if whenever $u$ and $v$ are vertices in $H$ and $uv$ is an edge of $G$, $uv$ is an edge of $H$.  We say a spanning subgraph of  $G$ is a \emph{bond} if every connected component of the subgraph is induced.  As an example, consider the graph $G$ in \cref{graphFig}. The subgraphs $H$ and $H'$ are bonds, but $H''$ is not since it is missing the edge $16$.  To each bond $H$, one can associate a set partition, $\pi(H)$, so that $i$ and $j$ are in the same block of $\pi(H)$ if and only if $i$ and $j$ are in the same connected component of $H$.  For example,  for the bond $H$ in \cref{graphFig}, we have that $\pi(H)=12345/6$.    A partition $\pi = B_1/B_2/\cdots/ B_k$  is called \emph{crossing} if there exists $a,c \in B_i$ and $b,d \in B_j$ with $i\neq j$ and $a<b<c<d$.  For example, the partition  $1248/ 56/37$ is crossing since   we can pick $2, 4\in 1248$ and $3,7 \in 37$.  A partition is \emph{noncrossing} if it is not crossing.  We say the bond $H$ is  \emph{crossing} (resp.~\emph{noncrossing}) if $\pi(H)$ is crossing (resp.~noncrossing).   It is not hard to verify the following lemma.

\begin{lem}
A bond $H$ is crossing if and only if there exists edges in $H$ in different connected components which cross in the graphical representation of $H$.
\end{lem}

Note that this lemma implies that it is possible for edges to cross in the graphical representation of a noncrossing bond as long as these edges are in the same connected component.    For example, the bond $H$ in \cref{graphFig} is noncrossing since it corresponds to $12345/6$, but it has crossing edges, namely $14$ and $35$.


The \emph{bond lattice} of $G$, denoted by $L_G$, is the collection of bonds of $G$ ordered by inclusion.  Removing all the bonds in $L_G$ which are crossing gives us  our main object of study.

\begin{definition}
Let $G$ be a graph.   The \emph{noncrossing bond poset}, denoted by $\NC_G$, is the collection of noncrossing  bonds of $G$ ordered by inclusion. 
\end{definition}
See \cref{SnLabelFig} for an example of a graph and its noncrossing bond poset.  We wish to emphasize that $\NC_G$ need not be a lattice.   For example, let $G$ be the graph with vertex set $[4]$ and edges $13$ and $24$.  It is easy to see that $\NC_G$ has no maximum element.  The issue is that the graph itself is a crossing bond and so does not appear in $\NC_G$.  From this example, one might conjecture that we always get a meet semi-lattice.  Unfortunately, this is not the case.  For example, consider the graph $G$ in \cref{graphFig}.  The bonds $H$ and $H'$ are noncrossing and so appear in $\NC_G$.  Since  the bonds are ordered by containment, if $X\leq H, H'$ then $X\subseteq H\cap H'$.  However, $H\cap H' = \{14, 35\}$, which is crossing and thus not in $\NC_G$.   Since $\{14\}$ and $\{35\}$ are noncrossing bonds, $H$ and $H'$ do not have a meet in $\NC_G$.     

\begin{definition}
Let $G$ be a graph.  We say $G$ is \emph{crossing closed} if whenever $a,b,c,d\in V(G)$ with  $a<b<c<d$ and $ac,bd \in E(G)$,  there exists a unique minimum (with respect to inclusion) induced connected component containing $a,b,c,d$.
\end{definition}   

 
 Note that the graph $G$ in \cref{graphFig} is not crossing closed since $14$ and $35$ are both contained in the minimal induced connected components with  vertices  $1,2,3,4,5$ and with vertices $1,3,4,5,6$.  On the other hand, any tree is crossing closed. It turns out that not being crossing closed is the only obstruction to $\NC_G$ being a lattice.


\begin{thm}
Let $G$ be a graph.  Then $\NC_G$ is a lattice if and only if $G$ is crossing closed.  Moreover, if $G$ is crossing closed and $H, H' \in \NC_G$, then $H\wedge H' = H \cap H'$.
\end{thm}



\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=.9]
\coordinate (v1) at (0,1);
\coordinate (v2) at (.87,.5);
\coordinate (v3) at (.87,-.5);
\coordinate (v4) at (0,-1);
\coordinate (v5) at (-.87,-.5);
\coordinate (v6) at (-.87,.5);


\draw[thick] (v1)--(v5)--(v3);
\draw[thick] (v1) -- (v4)--(v2)--(v6);

\foreach \v in {v1,v2,v3,v4, v5,v6} \fill(\v) circle (.1);
\draw(0,1.4) node{\footnotesize 1};
\draw (.87+.4,.5+.4) node{\footnotesize 2};
\draw(0,-1.4) node{\footnotesize 4};
\draw (.87+.4,-.5-.4) node{\footnotesize 3};
\draw (-.87-.4,-.5-.4) node{\footnotesize 5};
\draw (-.87-.4,.5+.4) node{\footnotesize 6};
\draw(0,-2.2) node {\large $G$};


\end{tikzpicture}
\end{center}
\caption{A graph whose noncrossing bond poset is not graded. \label{nonGradedFig} }
\end{figure}


In addition to $\NC_G$ not necessarily being a lattice, $NC_G$ need not be graded. Consider the graph in \cref{nonGradedFig}.  The bond corresponding to the partition $1/26/35/4$  is noncrossing,  but the only element of $\NC_G$ which covers $1/26/35/4$ is $123456$.   It follows that $1/2/3/4/5/6 \cover 1/26/3/4/5 \cover 1/26/35/4 \cover  123456$ is a maximal chain in $\NC_G$. However, there is another maximal chain  $1/2/3/4/5/6 \cover 14/2/3/5/6 \cover 124/3/5/6 \cover 1246/3/5 \cover 12456/3 \cover 123456$ and so $\NC_G$ is not graded.







\section{Perfectly Labeled Graphs}\label{perfectlyLabeledSec}

\begin{definition}
Let $G$ be a graph.  We say $G$ is \emph{perfectly labeled} if whenever $ik, jk \in E(G)$ with $i<j<k$, $ij \in E(G)$.  
\end{definition}





It is well-known that a graph can be perfectly labeled if and only if it is chordal (see, for example, \cite[Corollary 4.10]{s:iha}).  However, not every labeling of a chordal graph gives rise to a perfectly labeled graph.  The distinction between perfectly labeled and chordal is immaterial to the structure of the bond lattice since the lattice does not depend on the labeling of the vertex set.  However, in the case for the noncrossing bond poset, the structure of the poset does  depend on the labeling of the graph.  Because of this, we focus on perfectly labeled graphs as opposed to just chordal graphs.   The next lemma will be useful in this section.

\begin{lem}\label{perfLabLem}
Let $G$ be a perfectly labeled graph. Suppose that $H\leq H'$ in $\NC_G$.  Moreover, suppose that $B_1,B_2,\dots, B_k$ where $\min B_1<\min B_2<\cdots < \min B_k$ are the connected components of $H$ that are merged together to get $H'$.  Then merging $B_1$ and $B_2$ in $H$ creates a noncrossing bond of $G$.
\end{lem}
\begin{proof}
Let $3\leq i \leq k$.  If merging $B_1$ and $B_2$ crossed with some  $B_i$, then there exists $a,c \in B_1 \cup B_2$ and $b,d \in B_i$ or $a,c \in B_i$ and $b,d \in B_1\cup B_2$ with $a<b<c<d$.  If $a,c \in B_1 \cup B_2$ and $b,d \in B_i$, then $\min B_1< \min B_2 <b < c<d$ which implies either $B_1$ and $B_i$ cross or $B_2$ and $B_i$ cross.  Neither is possible since $H$ is noncrossing.  A similar argument shows that it is not possible that there exists $a,c \in B_i$ and $b,d \in B_1\cup B_2$ with $a<b<c<d$.  Moreover, merging $B_1$ and $B_2$ cannot cross any other connected components of $G$ since that would mean that $H'$ was crossing.  Thus, it suffices to show that merging $B_1$ and $B_2$ in $H$ forms a bond of $G$.   In~\cite{hsm:isf}, Hallam, Martin, and Sagan showed that every connected graph which is perfectly labeled contains an increasing spanning tree (i.e. a spanning tree where the labels of the vertices along  any path from the smallest vertex to any other vertex are increasing).    It follows that in $H'$ there is an increasing path from $\min B_1$ to $\min B_2$.  Except for $\min B_2$, this path must only contain vertices from $B_1$ and so there is an edge between $B_1$ and $B_2$.  It follows that merging $B_1$ and $B_2$ gives a bond of $G$.
\end{proof}

As we saw earlier, the noncrossing bond poset may not be graded. However, if $G$ is perfectly labeled and $G$ is a noncrossing bond of itself (for example if $G$ is connected), then one can use the previous lemma to show that $\NC_G$ is graded.    Throughout the rest of the abstract, we will use $cc(G)$ to denote the number of connected components of $G$.

\begin{prop}\label{coverProp}
Let $G$  be a perfectly labeled graph.  If $H, H'\in \NC_G$ and $H\cover H'$ then exactly  two connected components of $H$ merge together to get $H'$ and thus
$cc(H) = cc(H')+1$. Additionally, if $G$ is a noncrossing bond of itself, then  $\NC_G$ is  graded and for $H\in \NC_G$, the rank of $H$ is given by $\rho(H) = n -cc(H)$.
\end{prop}




It is well-known that a graph $G$ is chordal if and only if the bond lattice of $G$ is supersolvable (see~\cite[\S 4]{s:iha} for details).  We will now show an analogue of this result for the noncrossing bond poset.  To do this, we give an $S_n$ EL-labeling of the noncrossing bond poset of perfectly labeled graphs.  We briefly review some material about edge labelings of posets.  For more information about edge labelings and their implications see~\cite{s:EC1} and~\cite{w:pt}.


Let $P$ be a graded poset.  An \emph{edge labeling} of $P$ is a function $\lambda: \mathcal{E}(P) \rightarrow \Lambda $ where $\mathcal{E}(P)$ is the set of edges of the Hasse diagram of $P$ and $\Lambda$ is a set of labels which is partially ordered.    We note here that although the labels are allowed to be partially ordered, in this extended abstract they will always be totally ordered.  Now suppose that $P$ is a graded poset with edge labeling $\lambda$.   Let $\c: x_0\cover x_1 \cover \cdots \cover x_k$ be a saturated chain in $P$.  We say $\c$ is \emph{increasing} if 
$$
\lambda(x_0\cover x_1)<\lambda(x_1\cover x_2)<\cdots< \lambda(x_{k-1}\cover  x_k).
$$
  Moreover, we say $\c$ is \emph{decreasing} if 
$$
\lambda(x_0 \cover  x_1) \geq \lambda(x_1 \cover x_2) \geq \cdots\geq  \lambda(x_{k-1}\cover x_k).
$$



Let $\lambda$ be an edge labeling of $P$. We say $\lambda$ is an \emph{EL-labeling} if every interval has a unique  increasing maximal chain and this chain precedes every other maximal chain in the interval in lexicographic order.  The edge labeling in \cref{SnLabelFig} is an EL-labeling.   It also has the property that every maximal chain is labeled by a permutation of $[3]$. Such labelings have a special name.  We say an EL-labeling of $P$ is an \emph{$S_n$ EL-labeling} if every maximal chain of $P$ is labeled by a permutation of $[n]$ where $n$ is the rank of $P$. We note  that the condition that the unique maximal chain in each interval is lexicographically first is automatically implied if the maximal chains are labeled by permutations and thus, we  only need to check  that each interval has a unique    increasing maximal chain.




\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=.7]
\coordinate (v1) at (0,1);
\coordinate (v2) at (1,0);
\coordinate (v3) at (0,-1);
\coordinate (v4) at (-1,0);
\draw[thick] (v3)--(v1) -- (v2) -- (v4);
\foreach \v in {v1,v2,v3,v4} \fill(\v) circle (.1);
\draw(0,1.4) node{\footnotesize 1};
\draw(0,-1.4) node{\footnotesize 3};
\draw(1.4,0) node{\footnotesize 2};
\draw(-1.4,0) node{\footnotesize 4};
\draw(0,-3.2) node {\large $G$};


\begin{scope}[shift = {(8,-2)}]

\node (1/2/3/4) at (0,0)  {$1/2/3/4$};

\node (12/3/4) at (0,2)  {$12/3/4$};
\node (13/2/4) at (-5,2)  {$13/2/4$};
\node (1/24/3) at (5,2)  {$1/24/3$};

\draw[thick] (1/2/3/4)--(12/3/4);
\draw[thick] (1/2/3/4)--(13/2/4);
\draw[thick] (1/2/3/4)--(1/24/3);

\node (123/4) at (-5,4)  {$123/4$};
\draw[thick] (12/3/4)--(123/4)--(13/2/4);
\node (124/3) at (5,4)  {$124/3$};
\draw[thick] (12/3/4)--(124/3)--(1/24/3);




\node (1234) at (0,6)  {$1234$};
\draw[thick] (123/4)--(1234)--(124/3);
\draw(0,-1.2) node {\large $\NC_G$};
\tikzstyle{every node}=[blue, scale=1.1]
\node at (-2.5, 1.25) {$2$};
\node at (0.2, 1.2) {$1$};
\node at (2.5, 1.25) {$3$};
\node at (-2.5, 3.25) {$2$};
\node at (2.5, 3.25) {$3$};
\node at (5.5, 3.25) {$1$};
\node at (-5.5, 3.25) {$1$};
\node at (-2.5, 5.25) {$3$};
\node at (2.5, 5.25) {$2$};
\end{scope}
\end{tikzpicture}
\end{center}
\caption{A graph and its noncrossing bond poset with its edges labeled in blue.\label{SnLabelFig} }
\end{figure}




Bj\"orner~\cite{b:scmpos} and  Bj\"orner and Wachs~\cite{bw:lsp} showed that there are several nice topological consequences of a poset having an EL-labeling.  For example, they showed that given a poset with an EL-labeling, the order complex of $P$ is shellable and has the homotopy type of a wedge of spheres.   In addition to these properties,  there are special properties that a lattice with an $S_n$ EL-labeling possesses.   In particular, McNamara~\cite{m:els} showed that if $L$ is a graded lattice then $L$ is supersolvable if and only if it has an $S_n$ EL-labeling.  We will show that if $G$ is perfectly labeled  and connected, then it has an $S_n$ EL-labeling.   



By \cref{coverProp} if $H \cover H'$ in $\NC_G$, then two connected components of $H$ merge together in $H'$.  Suppose that $B$ and $B'$ are the connected components which merge while going from $H$ to $H'$.  We define an edge labeling $\lambda$ on $\NC_G$ by
$$
\lambda(H\cover H') = \max\{\min B, \min B'\} -1.
$$
See the poset in \cref{SnLabelFig} for an example of this labeling.  Bj\"orner and Edelman~\cite{b:scmpos} showed that $\lambda$ gives an EL-labeling of the noncrossing partition lattice (which is also the noncrossing bond poset of the complete graph).  As McNamara points out in~\cite{m:els}, this labeling is in fact an $S_n$ EL-labeling.  It turns out that if $G$ is perfectly labeled, then $\lambda$ is also an $S_n$ EL-labeling of $\NC_G$.   Note that in the hypothesis of the following theorem, we assume $G$ has $n+1$ vertices and is connected.  This guarantees that $\NC_G$ has  rank $n$ and a $\hat{1}$.


\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=.9]
\coordinate (v1) at (0,1);
\coordinate (v2) at (.78,.62);
\coordinate (v3) at (.97,-0.22);
\coordinate (v4) at (0.43,-0.9);
\coordinate (v5) at (-0.43,-0.9) ;
\coordinate (v6) at (-.97,-0.22);
\coordinate (v7) at (-.78,.62);


\draw[thick] (v1) -- (v2)--(v3)--(v1)--(v6);
\draw[thick] (v3)--(v4)--(v5)--(v3);
\draw[thick] (v5)--(v7);
\draw[thick] (v2)--(v4);

\foreach \v in {v1,v2,v3,v4, v5,v6, v7} \fill(\v) circle (.1);

\draw(0,1.4) node{\footnotesize 1};
\draw(.78+.4,.62+.4) node{\footnotesize 2};
\draw(.97+.4,-0.22) node{\footnotesize 3};
\draw (0.43+.4,-0.9-.4) node{\footnotesize 4};
\draw (-0.43-.4,-0.9-.4) node{\footnotesize 5};
\draw (-.97-.4,-0.22) node{\footnotesize 6};
\draw (-.78-.4,.62+.4) node{\footnotesize 7};

\end{tikzpicture}
\end{center}
\caption{A perfectly labeled graph which is not crossing closed\label{peoNotCCFig} }
\end{figure}

\begin{thm}
Let $G$ be a  perfectly labeled graph on $[n+1]$ which is connected.  Then $\NC_G$ has an $S_n$ EL-labeling.
\end{thm}
\begin{proof}[(Proof Sketch)]
First, it is clear that the maximal chains are labeled by permutations of $[n]$.  Thus  it suffices to show that  each interval in $\NC_G$ has a unique   increasing maximal chain.   Since  $G$ has $n+1$ vertices, it is a subgraph of the complete graph $K_{n+1}$.  It follows that $\NC_G$ is a subposet of $\NC_{K_{n+1}}$ which is isomorphic to the noncrossing partition lattice.  Since  it is known that $\lambda$ is an EL-labeling of the noncrossing partition lattice, it is enough to show that each interval in $\NC_G$ has an   increasing  maximal chain.

Suppose that $[X,Y]$ is an interval in $\NC_G$ and suppose that $B_1,B_2,\dots, B_k$ are the connected components of $X$ that will merge together to get $Y$. Moreover, assume that $\min B_1<\min B_2<\cdots < \min B_k$.  It is not hard to see that if there is an  increasing maximal chain  in $[X,Y]$, the first step must be to merge $B_1$ and $B_2$.   Let $Z$ be obtained by merging $B_1$ and $B_2$ in $X$. We can apply \cref{perfLabLem} to see that $Z \in \NC_G$.   Now we can use induction to prove that $[Z,Y]$ has an   increasing  maximal chain which can be concatenated with the label from $X$ to $Z$ to give an   increasing maximal chain in $[X,Y]$.
\end{proof}



\begin{cor}\label{cor:PerLabel}
Let $G$ be a connected graph which is perfectly labeled.  Then we have the following.
\begin{enumerate}
\item[(a)] $\NC_G$ is shellable.
\item [(b)] If $G$ is crossing closed, then $\NC_G$ is supersolvable.
\end{enumerate}
\end{cor}


We mention here that not every connected perfectly labeled graph is crossing closed (hence the necessity of the hypothesis in part (b) of \cref{cor:PerLabel}).  The graph  in \cref{peoNotCCFig} is perfectly labeled, but not crossing closed.  This is because there are two minimal induced connected components containing $16$ and $57$, namely  the one containing the vertices $1,3,5,6,7$ and the one containing $1,2,4,5, 6,7$.

The reader may be wondering if $\NC_G$ being supersolvable implies that $G$ is chordal since this is the case for the bond lattice of a graph.  The graph in \cref{twistedC4Fig} shows this is not true.  It is a 4-cycle and thus is not chordal.  Nevertheless, the noncrossing bond poset is a supersolvable lattice with modular chain $1/2/3/4 \cover 12/3/4\cover 12/34\cover 1234$.  

\begin{figure}
\begin{center}
\resizebox{\textwidth}{!}{
\begin{tikzpicture}
\coordinate (v1) at (0,1);
\coordinate (v2) at (1,0);
\coordinate (v3) at (0,-1);
\coordinate (v4) at (-1,0);
\draw[thick] (v1) -- (v2) -- (v4) --  (v3)--cycle;
\foreach \v in {v1,v2,v3,v4} \fill(\v) circle (.1);
\draw(0,1.4) node{\footnotesize 1};
\draw(0,-1.4) node{\footnotesize 3};
\draw(1.4,0) node{\footnotesize 2};
\draw(-1.4,0) node{\footnotesize 4};
\draw(0,-3.2) node {\large $G$};


\begin{scope}[shift = {(9,-2)}]

\node (1/2/3/4) at (0,0)  {$1/2/3/4$};

\node (12/3/4) at (-5,2)  {$12/3/4$};
\node (13/2/4) at (-2,2)  {$13/2/4$};
\node (1/24/3) at (2,2)  {$1/24/3$};
\node (1/2/34) at (5,2)  {$1/2/34$};

\draw[thick] (1/2/3/4)--(12/3/4);
\draw[thick] (1/2/3/4)--(13/2/4);
\draw[thick] (1/2/3/4)--(1/24/3);
\draw[thick] (1/2/3/4)--(1/2/34);

\node (123/4) at (-5,4)  {$123/4$};
\draw[thick] (12/3/4)--(123/4)--(13/2/4);
\node (124/3) at (-2.5,4)  {$124/3$};
\draw[thick] (12/3/4)--(124/3)--(1/24/3);

\node (12/34) at (0,4)  {$12/34$};
\draw[thick] (12/3/4)--(12/34)--(1/2/34);

\node (134/2) at (2.5,4)  {$134/ 2$};
\draw[thick] (13/2/4)--(134/2)--(1/2/34);

\node (1/234) at (5,4)  {$1/ 234$};
\draw[thick] (1/24/3)--(1/234)--(1/2/34);


\node (1234) at (0,6)  {$1234$};
\draw[thick] (123/4)--(1234)--(124/3);
\draw[thick] (12/34)--(1234)--(134/2);
\draw[thick] (1/234)--(1234);



\draw(0,-1.2) node {\large $\NC_G$};

%Mobius Values
\tikzstyle{every node}=[red, inner sep=0.4pt, scale=1, minimum width=4pt]

\draw (1.25, 0) node {$+1$};

\draw (-3.75, 2) node {$-1$};
\draw (-.75, 2) node {$-1$};
\draw (3.25, 2) node {$-1$};
\draw (6, 2) node {$-1$};


\draw (-4, 4) node {$+1$};
\draw (-1.5, 4) node {$+1$};
\draw (1, 4) node {$+1$};
\draw (3.5, 4) node {$+1$};
\draw (6, 4) node {$+1$};

\draw (1.25, 6) node {$-2$};

\end{scope}
\end{tikzpicture}
}
\end{center}
\caption{Twisted 4-cycle and its noncrossing bond poset. M\"obius values are in red. \label{twistedC4Fig} }
\end{figure}




\section{The M\"obius Function and the Characteristic Polynomial} \label{MobSec}
In this section we provide a combinatorial interpretation for the M\"obius function and characteristic polynomial of the noncrossing bond poset for a  family of graphs.   Given a poset $P$, the (one-variable) M\"obius function is recursively defined by
$$
\mu(x) =
\begin{cases}
1 & \mbox{ if } x=\hat{0,}\\
-\displaystyle \sum_{y<x}\mu(y)  & \mbox{ otherwise.}
\end{cases}
$$
Moreover, if $P$ is graded, then  the \emph{characteristic polynomial} of $P$ is given by
$$
\chi(P,t)  = \sum_{x\in P} \mu(x) t^{\rho(P)-\rho(x)}.
$$
 See~\cite{s:EC1} for background on the M\"obius function and characteristic polynomial.  It is well-known that for a graph $G$,  $\chi(L_G,t)$ is (up to a factor of $t$) the chromatic polynomial of $G$ (see~\cite{s:iha}).   In~\cite{whi:lem}, Whitney gave a combinatorial interpretation for the coefficients of the chromatic polynomial in terms of NBC sets.  We briefly recall some facts about NBC sets.  

Let $G$ be a graph.  Put a total order on the edges of $G$.  A \emph{broken circuit} of $G$ is a collection of edges of $G$ obtained by removing the smallest edge of a cycle of $G$.  We say a subset $S$ of $E(G)$ is an \emph{NBC (non-broken circuit) set} if $S$ contains no subsets which are broken circuits.      Whitney~\cite{whi:lem} showed that if 
$$
\chi(L_G,t)=\sum_{k\geq 0} (-1)^{k}c_k t^{\rho(L_G)-k} 
$$
then $c_k$ is the number of NBC sets of $G$ with $k$ edges. 

As an example, let $G$ be the 4-cycle given in \cref{twistedC4Fig}. Order the edges  lexicographically.   Since the graph is a cycle, every subset of the edge set is an NBC set except for  $\{13, 24, 34\}$ and $\{12,13,24,34\}$.  It follows that the characteristic polynomial of $L_G$ is given by
$$
\chi(L_G, t)  = t^3 -4t^2+ 6t -3.
$$
Now lets compare this with the characteristic polynomial of $\NC_G$.  From the M\"obius values shown in  \cref{twistedC4Fig}, we see that 
$$
\chi(\NC_G,t ) = t^3- 4t^2 +5t -2.
$$
Since the absolute value of the coefficients of  $\chi(\NC_G,t)$ are less than the corresponding values in $\chi(L_G,t)$, it is at least plausible that the coefficients of $\chi(\NC_G,t)$ count a subset of the NBC sets of $G$.  It turns out this is the case as we see next.

Let $S$ be an NBC set of $G$. We say that $S$ is a \emph{noncrossing NBC set} if $S$ contains no edges which cross.  Returning to our example of the 4-cycle given in \cref{twistedC4Fig}, we can see that the only NBC sets which have crossing edges are $\{13, 24\}$ and $\{12, 13, 24\}$.  Note that this means that for this particular graph the coefficients of $\chi(\NC_G,t)$ are counted by noncrossing NBC sets of $G$.  While this  combinatorial interpretation need not  hold  for all graphs, it does hold for a  family of graphs.

\begin{definition}
Let $G$ be a graph with a total ordering, $\unlhd$, on the edge set of $G$.  We say that a graph $G$ is \emph{upper crossing closed} with respect to $\unlhd$ if it is crossing closed and whenever  $ac, bd$ are crossing edges, then the unique minimum induced connected component containing $a,b,c,d$ contains an edge $e$  such that $e \lhd ac, bd$.
\end{definition}

The 4-cycle in \cref{twistedC4Fig} with edges ordered lexicographically is upper crossing closed.  To see why, note that the unique minimum induced connected component containing the crossing edges $13, 24$ is the entire graph which contains the edge $12$ and $12$ is lexicographically smaller than $13$.  For an example of a graph which is not upper crossing closed, consider the graph obtained by removing the edge $12$ from the 4-cycle in \cref{twistedC4Fig} while keeping the lexicographic ordering on the edge set.



\begin{thm}\label{NCNBCThm}
Let $G$ be a graph  on $[n]$ with total ordering $\unlhd$ on $E(G)$.  Suppose $G$ is  upper crossing closed  with respect to $\unlhd$. 
Then for $H \in \NC_G$, 
$$
\mu(H) = (-1)^{n-cc(H) } (\# \mbox{ of noncrossing NBC sets of $G$ whose join is $H$}).
$$
Moreover, if $\NC_G$ is graded  with rank function $\rho(H) = n- cc(H)$ and
$$
\chi(\NC_G, t) =\sum_{k\geq 0} (-1)^kc_k t^{n-k},
$$
then  $c_k$ is the number of noncrossing NBC sets of $G$ with $k$ edges, where the NBC sets are with respect to $\unlhd$.
\end{thm}


In order to prove this theorem, we make use of  NBB sets introduced by Blass and Sagan~\cite{bs:mfl}.  We briefly discuss their results.  

\begin{definition} [\cite{bs:mfl}]
Let $L$ be a lattice and let $\unlhd$ be a partial order on the atoms of $L$.   A subset $S$ of the atoms of $L$ is \emph{bounded below} if there exists an atom $a$ such that
\begin{enumerate}
\item[(a)]  $a \lhd s$  for all $s\in S$
\item[(b)] $a < \bigvee S$
\end{enumerate}
We say subset, $S$, of the atoms of $L$ is an NBB set for $x$ if $S$ contains no bounded below sets and $\bigvee S = x$.  
\end{definition}

\begin{thm}[\cite{bs:mfl}]
Let $L$ be a lattice and let  $\unlhd$ be a partial order on the atoms of $L$. Then for all $x\in L$, 
$$
\mu(x) = \sum_{B} (-1)^{|B|}  
$$
where the sum is over NBB sets for $x$.
\end{thm}


We are now in a position to  sketch a proof of \cref{NCNBCThm}.  



\begin{proof}[(Proof Sketch of \cref{NCNBCThm})]  First note that the atoms of $\NC_G$ are the edges of $G$.  Order the atoms of $L$ by $\unlhd$.   Using the fact that $G$ is upper crossing closed, we can show that a subset of atoms of $\NC_G$ is NBB if and only if it is a noncrossing NBC set of $G$.  Then using Blass and Sagan's result, we have that for each $H \in \NC_G$,
$$
\mu(H) =  \sum_{B} (-1)^{|B|} 
$$
where the sum is over all the noncrossing NBC sets $B$ such that $\bigvee B = H$.  Since $B$ is noncrossing, $\bigvee B$ is the same in $L_G$ and $\NC_G$.  For a fixed $H$, all the NBC sets whose join is $H$ in $L_G$ have the same size, namely $n-cc(H)$.  It follows that 
\begin{align*}
\mu(H)& =  \sum_{B} (-1)^{|B|}\\
  &= \sum_{B} (-1)^{n-cc(H) }\\
&=  (-1)^{n-cc(H) } (\# \mbox{ of noncrossing NBC sets of $G$ whose join is $H$})
\end{align*}
The result now follows.
\end{proof}

 
In~\cite{hsm:isf}, the authors showed that if $G$ is perfectly labeled, then the NBC sets corresponding to the lexicographic order on the edges are exactly the increasing spanning forests of $G$.   Moreover, if $G$ is perfectly labeled and crossing closed, then it is upper crossing closed with respect to the lexicographic order.    Finally, by \cref{coverProp}, if $G$ is perfectly labeled $\NC_G$ is graded. Thus, we get the following.


\begin{thm}\label{NCISFThm}
Let $G$ be a graph which is perfectly labeled. Suppose $G$ is   crossing closed and that
$$
\chi(\NC_G, t) =\sum_{k\geq 0} (-1)^kc_k t^{\rho(\NC_G)-k}.
$$
Then $c_k$ is the number of noncrossing increasing spanning forests of $G$ with $k$ edges.
\end{thm}


We note that in~\cite{bs:mfl}, Blass and Sagan used NBB sets to show that the  M\"obius function of  the noncrossing partition lattice counts noncrossing increasing trees and hence is a Catalan number.  The previous theorem generalizes this result since the noncrossing partition lattice is the noncrossing bond poset of the complete graph.

\section{An Action of the Dihedral  Group}


We finish this extended abstract with a brief discussion of an action by the dihedral group.  Recall that the bond lattice does not depend on the labeling of the vertices.  Thus if $G$ is a graph on $[n]$ and $\sigma$ is an element of  $S_n$, the symmetric group, then $L_G \cong L_{\sigma(G)}$ where $\sigma(G)$ is the graph obtained by permuting the vertices by $\sigma$.  However, this is not the case for the noncrossing bond poset.  For example, if we apply the permutation $(123)(4)$ to the twisted 4-cycle in \cref{twistedC4Fig}, we get an untwisted 4-cycle with edges $12, 23,34, 14$ and the noncrossing bond posets  of the two graphs are not isomorphic.  Nevertheless, we can apply certain permutations to the graph without changing  the structure of the noncrossing bond poset.  

Since the graphs we are interested in appear on a circle, we can assume that the vertices all lie on a regular polygon.  Thus, if $G$ has $n$ vertices, the dihedral group, $D_{2n}$ acts on the graph.  To define this action, we apply the standard geometric action keeping the labels $1,2,\dots, n$ in the same position. This  action preserves the structure of the noncrossing bond poset.

\begin{prop}\label{DnProp}
Let $G$ be a graph on $[n]$.  If $\sigma \in D_{2n}$, then 
$$
\NC_G \cong \NC_{\sigma(G)}.
$$
\end{prop}




\acknowledgements   The results in this extended abstract had their genesis in the first author's master thesis.  We would like to thank Ed Allen, Hugh Howards, and Sarah Mason who made helpful suggestions and comments on that thesis.  We would also like to thank the anonymous referees for their  helpful comments and suggestions.


\sloppy
\printbibliography
\fussy

\end{document}








