Binary Search Tree insertion, the Hypoplactic insertion, and Dual Graded Graphs
Abstract
Description
Fomin (1994) introduced a notion of duality between two graded graphs on the same set of vertices. He also introduced a generalization to dual graded graphs of the classical Robinson-Schensted-Knuth algorithm. We show how Fomin's approach applies to the binary search tree insertion algorithm also known as sylvester insertion, and to the hypoplactic insertion algorithm.
11 pages, submitted to the Electronic Journal of Combinatorics on February 2007
11 pages, submitted to the Electronic Journal of Combinatorics on February 2007