Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2501.11073 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913925514133504 |
|---|---|
| author | Jaldevik, Albin Snellman, Jan |
| author_facet | Jaldevik, Albin Snellman, Jan |
| contents | The standard notion of poset probability of a finite poset P involves calculating, for incomparable $α$, $β$ in P, the number of linear extensions of P for which $α$ precedes $β$. The fraction of those linear extensions among all linear extensions of P is the probability that $α< β$. The question of whether there is always a pair $α, β$ such that this probability lies between 1/3 and 2/3, in any poset P (that is not a chain) is the famous "1/3-2/3-conjecture".
A general way of counting linear extensions of P for which $α$ precedes $β$ is to count linear extensions of the poset obtained by adding the relation $(α,β)$, and its transitive consequences.
For chain-products, and more generally for partition posets, lattice-path methods can be used to count the number of those linear extensions.
We present an alternative approach to find the pertinent linear extensions. It relies on finding the "blocking ideals" in $J(P)$, where $J(P)$ is the lattice of order ideals in P. This method works for all finite posets.
We illustrate this method by using blocking ideals to find explicit formulas of poset probabilities in cell posets $P_λ$ of two-row partitions. Well-known formulae such as the hook-length formula for $f^λ$, the number of standard Young tableaux on a partition $λ$, and the corresponding determinental formula by Jacobi-Trudi-Aitken for $f^{λ/ μ}$, the number of standard Young tableaux on a skew partition $λ/ μ$, are used along the way.
We also calculate the limit probabilities when the elements $α,β$ are fixed cells, but the arm-lengths tend to infinity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_11073 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Blocking Ideals: a method for filtering linear extensions of a finite poset Jaldevik, Albin Snellman, Jan Combinatorics 06A07 (Primary), 05A20 (Secondary) The standard notion of poset probability of a finite poset P involves calculating, for incomparable $α$, $β$ in P, the number of linear extensions of P for which $α$ precedes $β$. The fraction of those linear extensions among all linear extensions of P is the probability that $α< β$. The question of whether there is always a pair $α, β$ such that this probability lies between 1/3 and 2/3, in any poset P (that is not a chain) is the famous "1/3-2/3-conjecture". A general way of counting linear extensions of P for which $α$ precedes $β$ is to count linear extensions of the poset obtained by adding the relation $(α,β)$, and its transitive consequences. For chain-products, and more generally for partition posets, lattice-path methods can be used to count the number of those linear extensions. We present an alternative approach to find the pertinent linear extensions. It relies on finding the "blocking ideals" in $J(P)$, where $J(P)$ is the lattice of order ideals in P. This method works for all finite posets. We illustrate this method by using blocking ideals to find explicit formulas of poset probabilities in cell posets $P_λ$ of two-row partitions. Well-known formulae such as the hook-length formula for $f^λ$, the number of standard Young tableaux on a partition $λ$, and the corresponding determinental formula by Jacobi-Trudi-Aitken for $f^{λ/ μ}$, the number of standard Young tableaux on a skew partition $λ/ μ$, are used along the way. We also calculate the limit probabilities when the elements $α,β$ are fixed cells, but the arm-lengths tend to infinity. |
| title | Blocking Ideals: a method for filtering linear extensions of a finite poset |
| topic | Combinatorics 06A07 (Primary), 05A20 (Secondary) |
| url | https://arxiv.org/abs/2501.11073 |