MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: a little nasty problem?

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> 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> 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>
>> 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

  • Prev by Date: Re: a little nasty problem?
  • Next by Date: Re: if using Mathematica to solve an algebraic problem
  • Previous by thread: Re: a little nasty problem?
  • Next by thread: Re: a little nasty problem?