Re: a little nasty problem?

*To*: mathgroup at smc.vnet.net*Subject*: [mg108897] Re: a little nasty problem?*From*: Ray Koopman <koopman at sfu.ca>*Date*: Tue, 6 Apr 2010 07:25:25 -0400 (EDT)

I'm still not clear on the rule you're using to eliminate what look to me like chains. For instance, why do you not consider {A,F,D}, {A,C,D}, {A,B,D}, {A,F,C,D}, {A,F,B,D}, and {A,C,B,D} to be chains? ----- Francisco Gutierrez <fgutiers2002 at yahoo.com> wrote: > Thanks Ray for the question, because it helps me clarify the point > --I should have been much more clear. > > In effect. In the original example there are two chains: > {A,F,C,B,D} and {A,G}. > The program should report them both.--in general, it should list > all the chains that appear in the partially ordered set. > And yes, new points can form new chains, if they are incomparable > with other points. For example, in the above list, G is only > comparable to A, not to any other point. > The comparability criterion is that for 2 intervals x and y, x and > y are comparable if x[[1]]<=y[[1]] and x[[2]]<=y[[2]] or viceversa. > Incomparability occurs only when x[[1]]<=y[[1]] AND x[[2]]>y[[2]] > OR x[[1]]>y[[1]] AND x[[2]]<=y[[2]]. > Fg > --- On Thu, 4/1/10, Ray Koopman <koopman at sfu.ca> wrote: > >> 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? >> >> 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