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.