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?