Constructing explicit Sperner chain decompositions for $L(3,n)$ and $L(4,n)$ via Greedy Algorithms and chain tableaux
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914545493082112 |
|---|---|
| author | Xin, Guoce Zhong, Yueming |
| author_facet | Xin, Guoce Zhong, Yueming |
| contents | Let $L(m,n)$ denote Young's lattice, consisting of all partitions whose Young diagrams are contained within an $m\times n$ rectangle. It is a classical result that the partially ordered set $L(m,n)$ is rank-symmetric, rank-unimodal, and Sperner; however, finding a direct combinatorial proof via an explicit order matching remains a prominent open problem in the field. In this paper, we address this challenge by constructing explicit order matchings for $L(3,n)$ and extending our methods to comprehensively cover $L(4,n)$. To achieve this, we introduce a novel ``chain tableau" representation, which serves as a powerful tool for identifying and characterizing complex combinatorial patterns. Notably, we demonstrate that the same order matchings can be independently derived using both a greedy algorithm and a recursive kneading process. This work not only resolves the explicit matching problem for $m=3$ and $m=4$ but also establishes robust structural tools that may offer valuable insights into the general $L(m,n)$ case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_11003 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Constructing explicit Sperner chain decompositions for $L(3,n)$ and $L(4,n)$ via Greedy Algorithms and chain tableaux Xin, Guoce Zhong, Yueming Combinatorics Let $L(m,n)$ denote Young's lattice, consisting of all partitions whose Young diagrams are contained within an $m\times n$ rectangle. It is a classical result that the partially ordered set $L(m,n)$ is rank-symmetric, rank-unimodal, and Sperner; however, finding a direct combinatorial proof via an explicit order matching remains a prominent open problem in the field. In this paper, we address this challenge by constructing explicit order matchings for $L(3,n)$ and extending our methods to comprehensively cover $L(4,n)$. To achieve this, we introduce a novel ``chain tableau" representation, which serves as a powerful tool for identifying and characterizing complex combinatorial patterns. Notably, we demonstrate that the same order matchings can be independently derived using both a greedy algorithm and a recursive kneading process. This work not only resolves the explicit matching problem for $m=3$ and $m=4$ but also establishes robust structural tools that may offer valuable insights into the general $L(m,n)$ case. |
| title | Constructing explicit Sperner chain decompositions for $L(3,n)$ and $L(4,n)$ via Greedy Algorithms and chain tableaux |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2104.11003 |