The Robinson–Schensted algorithm

Snapshots of modern mathematics from Oberwolfach

The Robinson–Schensted algorithm

I am going to describe the Robinson–Schensted algorithm which transforms a permutation of the numbers from 1 to n into a pair of combinatorial objects called “standard Young tableaux”. I will then say a little bit about a few of the fascinating properties of this transformation, and how it connects to current research.

If you are interested in translating this Snapshot, please contact us at info@imaginary.org

Mathematical subjects

Algebra and Number Theory
Discrete Mathematics and Foundations

Author(s)

Hugh Thomas

License

DOI (Digital Object Identifier)

10.14760/SNAP-2022-002-EN

Download PDF

snapshot-2022-002.pdf

PDF

snapshots: overview

Sarah Hess, Angélica Torres, Mirte van der Eyden
Voronoi Cells: Or How to Find the Nearest Bakery
Ana Djurdjevac, Henri Elad Altman, Tommaso Rosati
Randomness is natural - an introduction to regularisation by noise
Po-Lam Yung
Waves and incidences
Luca Chiantini, Brian Harbourne
Geproci sets: a new perspective in algebraic geometry
Florian Frick
The geometry of fair division
Giuseppe Negro, Diogo Oliveira e Silva
4 = 2 × 2, or the power of even integers in Fourier analysis
Isabelle Baraquin, Nadia Lafrenière, Katharina Schuh
Cutoff phenomenon: Surprising behaviour in card shuffling and other Markov chains
Vern I. Paulsen
Algebras and quantum games
Ingmar Saberi
Felder und Räume: Symmetrie und Lokalität in Mathematik und theoretischen Wissenschaften
Pieter Belmans
The periodic tables of algebraic geometry
Jason J. Bramburger
Patterns and waves in theory, experiment, and application
Benjamin Dozier
Closed geodesics on surfaces
Kathrin Hellmuth, Christian Klingenberg
Route planning for bacteria
Fabian Mussnig
Characterizations of intrinsic volumes on convex bodies and convex functions
Jennifer S. Balakrishnan
A tale of three curves
Michael Baake, Uwe Grimm, Robert V. Moody
What is Pattern?
Saiteja Utpala, Nina Miolane
Biological Shape Analysis with Geometric Statistics and Learning
Ilya Dumanski, Valentina Kiritchenko
Representations and degenerations
Jonas Latz, Björn Sprungk
Solving inverse problems with Bayes’ theorem
Herbert Gangl
Jewellery from tessellations of hyperbolic space
Chr istina Frederick, Yunan Yang
Seeing through rock with help from optimal transport
David A. Craven
Searching for the Monster in the Trees
Hugh Thomas
The Robinson–Schensted algorithm
Franca Hoffmann, Sara Merino-Aceituno
Emergence in biology and social sciences
Jason D. Lotay
Lagrangian mean curvature flow
Leo Storme
Finite geometries: pure mathematics close to applications
Francesca Arici, Bram Mesland
Describing distance: from the plane to spectral triples
Martijn Caspers
Quantum symmetry
Fadoua Balabdaoui, Yulia Kulagina
The Enigma behind the Good–Turing formula
Anna Haensch
Reflections on hyperbolic space
Isaac Goldbring
Ultrafilter methods in combinatorics
Gandalf Lechner
Zopfgruppen, die Yang–Baxter-Gleichung und Unterfaktoren
Baptiste Rognerud
Invitation to quiver representation and Catalan combinatorics
Po-Ling Loh
Searching for structure in complex data: A modern statistical quest
David Kerr
C∗-algebras: structure and classification
Sara Lamboglia, Martin Ulirsch
From the dollar game to the Riemann-Roch Theorem
Steven Rayan, Laura P. Schaposnik
Higgs bundles without geometry
Behrend Heeren, Martin Rumpf
Shape space - a paradigm for character animation in computer graphics
Joshua Zahl
Rotating needles, vibrating strings, and Fourier summation
Moritz Weber
Quantum symmetry
Christian Berg
Determinacy versus indeterminacy
Jayadev S. Athreya, David Aulicino
Vertex-to-Self Trajectories on the Platonic Solids
Gianluca Finocchio
Random matrix theory: Dyson Brownian motion
Holger Kammeyer, Roman Sauer
From Betti numbers to l2-Betti numbers
Martin J. Gander
Is it possible to predict the far future before the near future is known accurately?
Jan-Bernhard Kordaß
The Interaction of Curvature and Topology
barbara Kaltenbacher, Igor Kukavica, Irena Lasiecka, Roberto Triggianti, Amjad Fuffaha, Justin Weber
The Mathematics of Fluids and Solids
Jake Fillman, Tom van den Boom
A surprising connection between quantum mechanics and shallow water waves
Daniel Zelazo, Shiyu Zhao
Formation Control and Rigidity Theory
Ana Khukhro
Expander graphs and where to find them
Simon Arridge, Maarten de Hoop, Peter Maass, Ozan Öktem, Carola Schönlie, Michael Unser
Deep Learning and Inverse Problems
Jan Martin Nordbotten
Mixed-dimensional models for real-world applications
Pietro Milici
Touching the transcendentals: tractional motion from the birth of calculus to future perspectives
Loïc Petitgirard
Analogue mathematical instruments: Examples from the “theoretical dynamics” group (France, 1948–1964)
Rita Jiménez Rolland, Miguel A. Xicoténcatl
Configuration spaces and braid groups
Tereza Klimošová
Limits of graph sequences
Paulo Oliva
On Logic, Choices and Games
Barbara Kaltenbacher, Rainer Brunnhuber
Nonlinear Acoustics
Volker Betz
Random permutations
Hugo Duminil-Copin
Counting self-avoiding walks on the hexagonal lattice
A. S. Detinko, D. L. Flannery, A. Hulpke
Algebra, matrices, and computers
Jonathan Rosenberg, David Wraith
Positive Scalar Curvature and Applications
Hector Pasten
Diophantine equations and why they are hard
Martin Buhmann, Janin Jäger
On radial basis functions
Ralf Schiffler
Snake graphs, perfect matchings and continued fractions
Nicolai Baldin
Estimating the volume of a convex body
Liran Rotem
Mixed volumes and mixed integrals
Filippo Santambrogio
A short story on optimal transport and its many applications
Sebastian Schönnenbeck
Number theory in quantum computing
Matthias Morzfeld, Sebastian Reich
Data assimilation: mathematics for merging models and data
Claus Hertling
Geometry behind one of the Painlevé III differential equations
Antonio Lerario
The codimension
Marius Tucsnak
The mathematics of aquatic locomotion
Erwan Brugallé, Ilia Itenberg, Kristin Shaw, Oleg Viro
Tropical geometry
Alex Barnett
Fast Solvers for Highly Oscillatory Problems
Greg Lupton, John Oprea, José Gabriel Carrasquel Vera
Topological Complexity, Robotics and Social Choice
Thomas Sauer
Prony’s method: an old trick for new problems
Colva M. Roney-Dougal
Computing with symmetries
Piotr Sułkowski
Topological recursion
Anna Seigal
The Algebraic Statistics of an Oberwolfach Workshop
Jean-Pierre Tignol
Solving quadratic equations in many variables
Chi-Wang Shu
Mathematics plays a key role in scientific computing
Mauricio Bustamante, Jan-Bernhard Kordaß
Spaces of Riemannian metrics
Shaula Fiorelli Vilmart, Gilles Vilmart
Computing the long term evolution of the solar system with geometric numerical integrators
Justin Solomon
Computational Optimal Transport
Justyna Szpond
A few shades of interpolation
George Hagedorn, Caroline Lasser
Molecular quantum dynamics
Marco Radeschi
Closed geodesics on surfaces and Riemannian manifolds
Christian Engwer, Markus Knappitsch
Mathematische Modellierung von Krebswachstum
Michael Baake, David Damanik, Uwe Grimm
Aperiodic Order and Spectral Properties
Lukas Pottmeyer
News on quadratic polynomials
Felix Günther
Winkeltreue zahlt sich aus
Jacob Bedrossian
Towards a Mathematical Theory of Turbulence in Fluids
Laurent Bartholdi
Profinite groups
Dietmar Gallistl
The adaptive finite element method
Steven Klee
Footballs and donuts in four dimensions
Nikolai Nowaczyk
The Willmore Conjecture
Lior Bary-Soroker
Prime Tuples in Function Fields
Rafael Guglielmetti, Matthieu Jacquemet
Polyhedra and commensurability
Manfred Deistler, Andreas Graef
Fokus-Erkennung bei Epilepsiepatienten mithilfe moderner Verfahren der Zeitreihenanalyse
Robert Altmann, Jan Heiland
Wie steuert man einen Kran?
Anthony T Patera, Karsten Urban
High performance computing on smartphones
Eugenio Giannelli, Jay Taylor
Symmetry and characters of finite groups
Maria Dostert, Stefan Krupp, Jan Hendrick Rolfes
Das Problem der Kugelpackung
Tomasz Szemberg
On the containment problem
Éric Fusy
Random sampling of domino and lozenge tilings
Magnus Egerstedt
Swarming robots
Ulrich Krähmer
From computer algorithms to quantum field theory: an introduction to operads
Juanjo Rué
Domino tilings of the Aztec Diamond
Sebastian Funk
The mystery of sleeping sickness – why does it keep waking up?
Antti Knowles
Quantum diffusion
Amanda Swan, Albert Murtha
Modelling the spread of brain tumours
J. Marron
Visual Analysis of Spanish Male Mortality
Christopher Sangwin
Curriculum development in university mathematics: where mathematicians and education collide
Jürg Kramer, Anna-Maria Pippich
Special values of zeta functions and areas of triangles
Victoria Powers
How to choose a winner : the mathematics of social choice
Valentina Kiritchenko, Evgeny Smirnov, Vladlen Timorin
Ideas of Newton-Okounkov bodies
Ben Schweizer
Darcy’s law and groundwater flow modelling
Raluca Eftimie
Modelling communication and movement: from cells to animals and humans
Tom Solomon
Chaos and chaotic fluid mixing
Thorsten Holm
Friezes and tilings
George Willis
Zero-dimensional symmetry
Christine Breiner
Minimizing energy
Diana Davis
Billiards and flat surfaces
Peter Benner, Hermann Mena, René Schneider
Drugs, herbicides, and numerical simulation
Gregory Knese
Operator theory and the singular value decomposition
Alain Valette
The Kadison-Singer problem
Ragnar-Olaf Buchweitz, Eleonore Faber
Swallowtail on the shore
Howell Tong
Statistics and dynamical phenomena
Brian Harbourne, Thomas Szemberg
Arrangements of lines
Bruce Reznick
What does ">" really mean?
Harald Helfgott
The ternary Goldbach Problem
Wolfgang Lerche
Matrixfaktorisierungen
John E. McCarthy
Dirichlet Series

Mathematical subjects

Algebra and Number Theory
Analysis
Didactics and Education
Discrete Mathematics and Foundations
Geometry and Topology
Numerics and Scientific Computing
Probability Theory and Statistics

Connections to other fields

Chemistry and Earth Science
Computer Science
Engineering and Technology
Finance
Humanities and Social Sciences
Life Science
Physics
Reflections on Mathematics

These icons are available under the CC BY-SA 4.0 license. Please feel free to use them to classify your own content.
The vector icons can be downloaded here.