Autori: Gabriel Istrate, Cosmin Bonchis

Editorial: Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM'2015), Lecture Notes in Computer Science vol. 9133, p.261-271, Springer Verlag, 2015.

Rezumat:

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 heap-based extension of Young tableaux, prove a hook inequality and an extension of the Robinson-Schensted correpondence.

Cuvinte cheie: heapable sequence, Young tableaux

URL: http://link.springer.com/chapter/10.1007/978-3-319-19929-0_22#page-1