Re: a little nasty problem?
- To: mathgroup at smc.vnet.net
- Subject: [mg108891] Re: a little nasty problem?
- From: Francisco Gutierrez <fgutiers2002 at yahoo.com>
- Date: Tue, 6 Apr 2010 07:24:15 -0400 (EDT)
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:
From: Ray Koopman <koopman at sfu.ca>
Subject: [mg108891] [mg108800] Re: a little nasty problem?
To: mathgroup at smc.vnet.net
Date: Thursday, April 1, 2010, 5:59 AM
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 inc=
omparable.
> This relation violates [weakly] transitivity.
> Now, I have a set of intervals, and I want to create the lattice that thi=
s 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} a=
nd {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 a=
n efficient code to make the job? I am trying to do something that is unfea=
sible?
>
> 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?