TY - JOUR
T1 - Maximal Chains in Bond Lattices
AU - Ahirwar, Shreya
AU - Fishel, Susanna
AU - Gya, Parikshita
AU - Harris, Pamela E.
AU - Pham, Nguyen
AU - Vindas-Meléndez, Andrés R.
AU - Vo, Dan Khanh
N1 - Funding Information:
∗S. Fishel is partially supported by Simons Collaboration Grants 359602 and 709671. †P. E. Harris was supported by a Karen Uhlenbeck EDGE Fellowship. ‡A. R. Vindas-Meléndez was supported by the NSF under Award DMS-2102921.
Publisher Copyright:
© The authors.
PY - 2022
Y1 - 2022
N2 - Let G be a graph with vertex set {1, 2, …, n}. Its bond lattice, BL(G), is a sublattice of the set partition lattice. The elements of BL(G) are the set partitions whose blocks induce connected subgraphs of G. In this article, we consider graphs G whose bond lattice consists only of non-crossing partitions. We define a family of graphs, called triangulation graphs, with this property and show that any two produce isomorphic bond lattices. We then look at the enumeration of the maximal chains in the bond lattices of triangulation graphs. Stanley’s map from maximal chains in the noncrossing partition lattice to parking functions was our motivation. We find the restriction of his map to the bond lattice of certain subgraphs of triangulation graphs. Finally, we show the number of maximal chains in the bond lattice of a triangulation graph is the number of ordered cycle decompositions.
AB - Let G be a graph with vertex set {1, 2, …, n}. Its bond lattice, BL(G), is a sublattice of the set partition lattice. The elements of BL(G) are the set partitions whose blocks induce connected subgraphs of G. In this article, we consider graphs G whose bond lattice consists only of non-crossing partitions. We define a family of graphs, called triangulation graphs, with this property and show that any two produce isomorphic bond lattices. We then look at the enumeration of the maximal chains in the bond lattices of triangulation graphs. Stanley’s map from maximal chains in the noncrossing partition lattice to parking functions was our motivation. We find the restriction of his map to the bond lattice of certain subgraphs of triangulation graphs. Finally, we show the number of maximal chains in the bond lattice of a triangulation graph is the number of ordered cycle decompositions.
UR - http://www.scopus.com/inward/record.url?scp=85134500471&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134500471&partnerID=8YFLogxK
U2 - 10.37236/10983
DO - 10.37236/10983
M3 - Article
AN - SCOPUS:85134500471
SN - 1077-8926
VL - 29
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 3
M1 - #P3.11
ER -