A "fall-back" rewording of the "consultancy fee" conjecture (to avoid Stas' example, if necessary)

From: David Halitsky (dhalitsky_at_cumulativeinquiry.com)
Date: 07/23/04 

Date: 23 Jul 2004 08:44:28 -0700

Stas wrote:

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

If this is in fact a counterexample (see my previous reply to
Stas), then it can be avoided by a minor fallback modification
to the original conjecture as follows (note that added text
is CAPTIALIZED):

***************************************************************
Let o(dag) be any ordered DAG (directed acyclic graph)
ON JUST N+1 VERTICES 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)v(N+1)
of all such o(dag)'s ON JUST N+1 VERTICES into
(not onto) the set of all dim 2 posets for which
one chain is 0,1,...,n (including the trivial
dim 2 poset in which both chains are 0,1,...,n)
*********************************************************

This will avoid Stas' case and still leave the force
of the conjecture intact, i.e. to establish that
ordered trees, ordered forests, and certain other
orderable DAGs have unique representations as
dim 2 posets.

I have asked/encouraged Stas to accept an honorarium
for forcing this issue, if he will not accept the
consultancy itself.

Relevant Pages