Gabriel Istrate, Cosmin Bonchis. Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley’s process. In Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM' 2015), Lecture Notes in Computer Science 9133, pp. 261271. Springer Verlag, 2015.
Abstract:
We investigate partitioning of integer sequences into heapable subsequences (previously defined and studied by Byers et al. We show that an extension of patience sorting computes the decomposition into a minimal number of heapable subsequences (MHS). We connect this parameter to an interactive particle system, a multiset extension of Hammersley’s process, and investigate its expected value on a random permutation. In contrast with the (well studied) case of the longest increasing subsequence, we bring experimental evidence that the correct asymptotic scaling is $frac{1+sqrt{5}}{2} · ln(n)$. Finally we give a heapbased extension of Young tableaux, prove a hook inequality and an extension of the RobinsonSchensted correpondence.
Keywords:
heapable sequence, Young tableaux
URL:
http://link.springer.com/chapter/10.1007/9783319199290_22#page1
Posted by
Gabriel Istrate
Back
