Arxiv Paper: Heapable Sequences and Subsequences

I haven't been blogging much;  consider me on extended vacation.  It's helping me prepare for giving up the blog soonish. 

But I thought I'd mention our newly posted arxiv paper Heapable Sequences and Subsequences.  I mentioned some time back I was looking at an Aldous/Diaconis survey on Longest Increasing Subsequences.  That was for this paper, where we look at a variation on this theme.  Say that a sequence is heapable if you can sequentially place the items into a (binary, increasing) heap, so each new item is the child of some item already in the heap.  So, for example, 1 4 2 3 5 is heapable, but 1 5 3 4 2 is not.  Then, just as you might consider increasing sequences and subsequences, you can consider heapable sequences and subsequences.  We (as far as I know) introduce this problem and provide some first results, as well as a lot of interesting open problems.  We give a simple (greedy) algorithm for determining if a sequence is heapable, but show that determining if a sequence is perfectly heapable (so the heap is a perfect binary tree) is NP-hard.  We show that the longest heapable subsequence of random permutation of [1,n] has length (1-o(1))n.  And we show some other thing as well.

The paper ends up being essentially combinatorial in nature, but we were actually thinking of a more economic motivation when we started the problem.  It's meant to be a variation of in the space of hiring problems (like the secretary problem);  here you are hiring for an organization with an org chart -- say in the shape of a perfect binary tree -- and your hiring restriction is that each node is the boss of its children nodes, and therefore must have a higher ranking than those nodes.  (One would, naturally, argue whether in practice a boss is always higher-ranked than the employees directly reporting to them, but one can always consider noisy variations in a future paper.)  Now this is like a multi-hire secretary problem, but with restrictions. 

Given the large number of papers related to longest increasing subsequences, it seems like there might be a lot of interesting things to find in looking at this variation on the them.