Re: Consultancy available ($1K - $5K US) for work on dim 2 partial orders and (ordered) DAGs

From: Stas Busygin (busygin_at_a-teleport.com)
Date: 07/23/04 

Date: Thu, 22 Jul 2004 20:35:51 -0400

Dear David,

Your conjecture may be wrong. It seems you assume that the
following holds:

[Claim] Let G be the comparability graph of a poset P of
dimension 2. Then the transitive reduction (i.e., removal of
all arcs u->v such that there is a vertex w such that u->w and
w->v are arcs) gives a DAG such that any two vertices in it
share either all or none of their immediate descendants.
Coversely, the transitive closure of a DAG having the mentioned
property given a poset of dimensionality 2.

I have a counterexample to the first part:

Chain 1: 5->1->4->2->3
Chain 2: 2->1->5->3->4

Then in the transitive reduction of the poset (which is, BTW,
the comparability graph of the poset itself in this case)
vertices 1 and 2 have 3 as a common immediate descendant, but 4
is an immediate descendant of 1 and not of 3.

Best regards,

Stas
http://www.busygin.dp.ua

David Halitsky wrote:
> !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
> Note: this is a corrected version of the posting
> to sci.math.research (which had several confusing
> typos in the statement of the relevant directed
> edge definition in the two DAG examples. It also
> has references to the relevant article by
> Dushnik and Miller, the relevant section of Trotter,
> and the relevant link at Eric Weisstein's
> MathWorld. Cumulative Inquiry apologizes for
> the typos in the previous posting to sci.math.research.
> !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
>
> Cumulative Inquiry, Inc, a start-up R&D firm
> chartered in Huntsville AL (USA), will pay a
> consultancy fee of $1K - $5K in order to obtain
> a proof of the following conjecture.
>
> ***********************************************
> Let o(dag) be any ordered DAG (directed acyclic
> graph) in which any two vertices share either all
> or none of their immediate descendants (note:
> pre-ordered trees and forests pre-ordered in the
> obvious way belong to the "none" leg of this
> condition.)
>
> There is then a 1:1 mapping from the set O(DAG)
> of all such o(dag)'s INTO (not ONTO) the set of
> all dim 2 partial orders (including the trivial
> dim 1 partial order or chain.)
>
> See two examples below for a tree and non-tree case
>
> Also, see this link at Eric Weisstein's MathWorld:
>
> http://mathworld.wolfram.com/PosetDimension.html
>
> and section of Trotter and article by Dushnik and
> Miller referenced in this link.
> ***********************************************
>
> Fiduciary references for prompt payment of
> consultancy fees by Cumulative Inquiry Inc
> can be obtained from William F. Mann at
> wfmann@alum.mit.edu.
>
> If a proof is obtained and the author thinks
> it worth submitting to any peer-reviewed journal,
> then rights will belong to the author of the proof.
>
> Further, if the fee is not exhausted by proof of
> the above, then the remainder can be applied to
> a precise definition of those ordered DAGs which
> are not in O(DAG) but are uniquely representable
> by dim 2 partial orders (this is tricky and not
> immediately obvious.)
>
> Finally, if the proof is so trivial as not to be
> worth even the min of the fee, could someone please
> sketch out its beginning in a posting to this group ?
>
> If the consultancy is desired, please respond to David
> Halitsky
>
> dhalitsky@cumulativeinquiry.com
>
> David Halitsky
> 2928 Stewart Campbell Pte
> Thompsons Station TN 37179 USA
> Cell: 256-426-6243 (USA)
>
> Thanks for any time anyone can afford to spend thinking
> on this matter.
>
> *************************************************
>
> Example of a "tree case"
>
> partial order 1: 0 1 2 3 4 5 6
> partial order 2: 0 6 1 5 2 4 3
>
> vertices: (0,0), (1,6), (2,1), (3,5), (4,2), (5,4), (6,3)
> edges: ((xi,yi),(xj,yj)) such that xi < xj and yi < yj
> and no (xk,yk) such that (xi < xk < xj) and
> (yi < yk < yj)
>
> Adjacency matrix giving just the DIRECTED edges for first (tree)
> example (trivial edges from vertex (xi,yi) to itself are omitted)
>
> (0,0) (1,6) (2,1) (3,5) (4,2) (5,4) (6,3)
>
> (0,0) 1 1
> (1,6)
> (2,1) 1 1
> (3,5)
> (4,2) 1 1
> (5,4)
> (6,3)
>
> ********************************************************
>
> Example of a "non-tree" case
>
> partial order 1: 0 1 2 3 4 5 6
> partial order 2: 0 2 1 6 5 4 3
>
> vertices: (0,0), (1,2), (2,1), (3,6), (4,5), (5,4), (3,3)
> edges: ((xi,yi),(xj,yj)) such that xi < xj and yi < yj
> and no (xk,yk) such that (xi < xk < xj) and
> (yi < yk < yj)
>
> Adjacency matrix giving directed edges for second (non-tree) example
> (trivial edges from vertex (xi,yi) to itself are omitted)
>
> (0,0) (1,2) (2,1) (3,6) (4,5) (5,4) (3,3)
>
> (0,0) 1 1
> (1,2) 1 1 1 1
> (2,1) 1 1 1 1
> (3,6)
> (4,5)
> (5,4)
> (6,3)

Relevant Pages