RSK-Complete Cycle Decompositions
CSEF · 2023 Mathematical Sciences Second Award
Overview
The Robinson-Schensted-Knuth (RSK) Correspondence is a mathematical mapping that takes a permutation and uniquely maps it to a pair of Young tableaux. This correspondence has been the subject of much study since it behaves well under operations like inversion and reversal, and the shapes of the resulting tableaux directly describe increasing subsequences within the permutation. This project aims to deepen our understanding of the RSK correspondence by examining the connection between the graphical representation of a permutation and the shapes of its corresponding Young tableaux. It is well known that every shape can be generated by exactly one involution (permutations with cycles of length at most two). We complement this classical result by examining the connection between permutations with large cycles and their resultant shapes. Last year, we showed that cyclic permutations can generate all RSK shapes (other than the two trivial shapes consisting of a single row or column) for a given n, a property that we call RSK-completeness. While this was a good first step, it offered no insight into the RSK-completeness of any other cycle decomposition. This year, we fully characterize the property of RSK-completeness across all cycle decompositions. This involves two significant new results. On the constructive side, we show that almost cyclic permutations (with one element mapping to itself and the rest of the permutation forming a cycle) are RSK-compete for odd n. And most interestingly, we show that no other cycle decomposition can be RSK-complete, completing our investigation of this important problem.
Source coverage
This record comes from a published award list, not a complete project archive. Its abstract comes from CSEF's public project showcase as archived by the Internet Archive before judging (https://web.archive.org/web/20230401224130/https://ca-csef.zfairs.com/showcase/ShowcaseInfo?f=838e60b7-ea75-46e8-865c-fde4864244b3); the version presented may differ.
Awards (1)
Competition history
- CSEF 2023
Resources
Related projects
ISEF · 2015
Cylindric Young Tableaux and Their Properties
ISEF · 2021
Robinson-Schensted Correspondence and Standard Young Tableaux
ISEF · 2014
Creating Permutations for Actions on Young Tableaux
ISEF · 2026
Digraphs From a New Josephus Transformation
ISEF · 2018
Monodromy Groups of Indecomposable Rational Functions
CSEF · 2010
Crank 0 Partitions and the Parity of the Partition Function
CSEF · 2023
Cycle Spaces of Friends-and-Strangers Graphs
CSEF · 2015
Arrangements of Minors in the Totally Positive Grassmannian and Sturmfels' Triangulation
Closest projects by meaning, across every fair and year in the corpus.
Browse more like this
Source: California Science & Engineering Fair public projects