Re: a little nasty problem?

*To*: mathgroup at smc.vnet.net*Subject*: [mg108800] Re: a little nasty problem?*From*: Ray Koopman <koopman at sfu.ca>*Date*: Thu, 1 Apr 2010 05:59:33 -0500 (EST)*References*: <hosi3h$o2h$1@smc.vnet.net>

On Mar 30, 3:00 am, Francisco Gutierrez <fgutiers2... at yahoo.com> wrote: > Dear Mathgroup: > Suppose I have a series of intervals, and I create an order relation. E.g., x is a typical interval, x={0.6,0.9}, and x>=y if x[[1]]>=y[[1]] and x[[2]]>=y[[2]]. > If x[[1]]>=y[[1]] and x[[2]]<y[[2]], or viceversa, the intervals are incomparable. > This relation violates [weakly] transitivity. > Now, I have a set of intervals, and I want to create the lattice that this order relation generates (suppose the weak violation of transitivity does not pop up).. > For example,int= {{C,{0.5,0.6}},{D,{0.1,0.2}},{A,{0.8,0.9}},{B,{0.4,0.6}},{F,{0.6,0.65}},{G,{0,0.7}}} > > I would like my code to put A at the top, with two chains: {A,F,C,B, D} and {A,G}. Of course, it ought to flag any antichain if it exists. > Now, there are several ways to do this. But what I have been able to cook up is TERRIBLY inefficient. With 10 intervals it works no more. Is there an efficient code to make the job? I am trying to do something that is unfeasible? > > Perhaps I am naively attacking a problem that has no solution. Or perhaps I am naively suggesting an easy problem is solvable. Some help out there? > Francisco It's not clear to me what the general rule is for which chains to keep. Taking the ends of the intervals as {x,y} coordinates and plotting the points, suppose we add a point E midway between D and G. Now are there three chains: {A,G}, {A,F,C,B,E}, and {A,F,C,B,D}? And suppose we add another point, H, midway between F and G. Do we now have {A,H,E} and {A,H,D}, in addition to the previous three chains?