Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Theses and dissertations
Ad Astra association
Press releases
Funding opportunities
>> Românã

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

Keywords: heapable sequence, Young tableaux


Posted by Gabriel Istrate


© Ad Astra 2001-2013