A Heyting Algebra on Dyck Paths of Type A and B

作者：Muhle Henri^*

来源：Order, 2017, 34(2): 327-348.

DOI：10.1007/s11083-016-9403-2

• Dyck path
• Dominance order
• Heyting algebra
• Distributive lattice
• Symmetric group
• Hyperoctahedral group
• Catalan numbers

In this article we investigate the lattices of Dyck paths of type A and B under dominance order, and explicitly describe their Heyting algebra structure. This means that each Dyck path of either type has a relative pseudocomplement with respect to some other Dyck path of the same type. While the proof that this lattice forms a Heyting algebra is quite straightforward, the explicit computation of the relative pseudocomplements using the lattice-theoretic definition is quite tedious. We give a combinatorial description of the Heyting algebra operations join, meet, and relative pseudocomplement in terms of height sequences, and we use these results to derive formulas for pseudocomplements and to characterize the regular elements in these lattices.

• 出版日期2017-7