# Andy's Math/CS page

## Monday, May 14, 2007

### Feed Me

A note to readers: I now have an RSS feed, accessible on the right toolbar ('Atom'). When used with appropriate software/sites (I have feeds on my homepage at My Yahoo), this will let you know when I've put up a new post--useful for a blog like this, where posts come strictly at random intervals. As always, I encourage feedback, which will bring more-frequent and more closely-tailored posts.

I try not to do throwaway posts, so how can I salvage this one? Hmm... a puzzle suggests itself:

Modern undergraduate that you are, you're watching bootleg 'Scrubs' episodes on your laptop. This goes on for three hours or so. Meanwhile, your site-feeds page occasionally updates to display someone's new blog post. When your favored blogs post, the content hits your feed within 10 minutes, but the precise delay is nondeterministic--could be 0, 10, or anything in between.

You register the order in which the feed updates come in. Now: is there an efficient method to calculate the number of 'true orders' in which the bloggers could have made their updates?

For example: say updates A, B, C came at 12:30, 12:35, and 12:41 respectively. Then this is consistent with the true-orders ABC, BAC, ACB, but not with, e.g. CAB. Thus the answer here is 3 ways.

Good luck! Does your method work if each individual blogger has their own (known) interval of possible delays?

Clarification: I haven't solved this problem. It might be #P-complete, and the proof of this might be very technical. It seems related to work on counting linear extensions of posets (which is #P-complete in general), discussed by Suresh here.

Labels:

• What do you mean by 'true orders'? Would you perhaps explicate your example.

By  Anonymous, at 3:55 AM

• There are two orders: the 'visible order' in which the updates hit your feed (with additional, precise time information), and the 'true order' in which the bloggers upload their new post.

E.g. in the example, the true order could have been BAC, since the true upload times could have been

A: 12:29 (post A took 1 minute to show up)

B: 12:26 (B took 9 minutes to show up)

C: 12:37 (C took 4 minutes).

But the true order couldn't have been CAB, since even if post C took 10 minutes to show up on your feed and post A showed up immediately, still post A would have been made at 12:30, while post C would have been made at 12:31, after A.

By  Andy D, at 5:26 PM

• I think the kinds of partial orders defined by your situation (in which a is necessarily earlier than b if a is at least ten minutes earlier than b) are called "semiorders". There has been a little work on counting the number of linear extensions of semiorders, though maybe it doesn't solve your problem: see http://dx.doi.org/10.1016/0012-365X(92)90036-F or http://dx.doi.org/10.1023/A:1006466932096

By  Anonymous, at 6:30 PM

• Thanks! I can't find a good online reference for semiorders (your refs are gated and a book, respectively), but are they synonymous with interval orders?

An interval order is a partial order realizable as a collection of line intervals, where A is declared <= B exactly if A's interval is disjoint from B's and comes before it. In the problem I gave, any 'true order' certainly has to respect the associated interval order.

It's not immediate that any total order respecting the interval order can be realized as the ordering on a sequence of points that fall within the indicated intervals. But, I believe I know how to prove this by induction. Thus our problem does reduce to a special case of counting completions of a partial order.

A slideshow I found at
http://dimacs.rutgers.edu/Workshops/RandomUtility/slides/BALOFDIMACS.pdf

gives a very simple structure theory for interval orders: they are exactly the partial orders that exclude "2 + 2", the configuration consisting of two chains of length 2, with no comparabilities between the two chains. Nice theorem!

For 'unit interval orders', where all intervals are the same length, the same ref also gives a characterization: they're exactly the partial orders excluding "3 + 1": a chain of length 3, all incomparable with a fourth element.

So maybe the counting problem for these is computationally simpler.

By  Andy D, at 8:49 PM

• Oh, and the slideshow also says 'semiorder' means the same as 'unit interval order'.

By  Andy D, at 8:51 PM

• You could just go to those posts in the blogs and read their timestamps.

- Anonymous,
being a spoilsport

By  Anonymous, at 7:55 AM

• And interrupt the 'Scrubs' marathon? Out of the question. :)

By  Anonymous, at 3:27 PM

• Wait, sanity check--unit interval orders ARE interval orders, so the characterization must be that

P is a u.i.order <==>

P excludes the '1 + 3' AND '2 + 2' configs.

By  Andy D, at 4:06 PM

• Andy---Indeed, the relevant slide from the DIMACS workshop said "An interval order that excludes 3+1 is a unit interval order." So it's already granted that it excludes 2+2.

Idle speculation here: An interval graph is the undirected complement of the graph of an interval order relation. (I.e., u---v iff the intervals u and v overlap.) Interval graphs are perfect, as (hence) are their complements. For perfect graphs several NP-complete problems become polynomial-time solvable via ellipsoid methods---this is a notable paper by GrÃ¶tschel, Lovasz, and Schrijver from the early 1980s. I wonder if similar considerations might get your problem into P.

Interval orders are not mentioned in Brightwell-Winkler's general-case paper, and the problem is said to be open on this 1995 page. Moreover, from Graham Brightwell's research page on posets, it seems ideas like my speculation above have been considered. Hmm...I'll ask around.

By  KWRegan, at 5:47 PM

• Thanks, Professor Regan! (Oh, and I was checking MY sanity, not that of the slides I skimmed.)

I'm curious the extent to which assuming excluded configurations in posets has powerful consequences, as with excluded minors in graph theory. Forbidding long chains or antichains seems to yield a lot of info, via tools like Dilworth's Thm; but what interval orders forbid involves specifying both comparabilities and incomparabilities, so I don't see an analogy of closure under minors for the poset family.

By  Andy D, at 6:35 PM

• JZWljo Your blog is great. Articles is interesting!

By  Anonymous, at 5:57 AM

• xv8u5g Thanks to author.

By  Anonymous, at 2:09 PM

• Wonderful blog.

By  Anonymous, at 3:21 PM

• actually, that's brilliant. Thank you. I'm going to pass that on to a couple of people.

By  Anonymous, at 3:46 PM

• Hello all!

By  Anonymous, at 3:23 PM