The minimum number of chains in a noncrossing partition of a poset

被引:0
作者
Chen, Ricky X. F. [1 ]
机构
[1] Hefei Univ Technol, Sch Math, Hefei 230601, Anhui, Peoples R China
关键词
partially ordered set; chain decomposition; noncrossing partition; linear extension; 132-avoiding; descent;
D O I
10.2298/FIL2408915C
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The notion of noncrossing partitions of a partially ordered set (poset) is introduced here. When the poset in question is [n] = {1, 2, ... , n} with the complete order of natural numbers, conventional noncrossing partitions arise. The minimum possible number of chains contained in a noncrossing partition of a poset clearly reflects the structural complexity of the poset. For the poset [n], this number is just one. However, for a generic poset, it is a challenging task to determine the minimum number. Our main result in the paper is some characterization of this quantity.
引用
收藏
页码:2915 / 2922
页数:8
相关论文
共 9 条
[1]  
[Anonymous], 1997, Enumerative Combinatorics
[3]  
Bai ZW, 2023, Arxiv, DOI arXiv:2209.01961
[4]   Linear sequential dynamical systems, incidence algebras, and Mobius functions [J].
Chen, Ricky X. F. ;
Reidys, Christian M. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2018, 553 :270-291
[5]   A DECOMPOSITION THEOREM FOR PARTIALLY ORDERED SETS [J].
DILWORTH, RP .
ANNALS OF MATHEMATICS, 1950, 51 (01) :161-166
[6]   STRONG VERSIONS OF SPERNERS THEOREM [J].
GREENE, C ;
KLEITMAN, DJ .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1976, 20 (01) :80-88
[7]   Partitioning the Boolean lattice into chains of large minimum size [J].
Hsu, T ;
Logan, MJ ;
Shahriari, S ;
Towse, C .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2002, 97 (01) :62-84
[8]  
Jani M., 2000, Electron. J. Combin., V7, p#R45
[9]   Noncrossing partitions [J].
Simion, R .
DISCRETE MATHEMATICS, 2000, 217 (1-3) :367-409