Re: DAG/POSET "consultancy fee" conjecture: sole thread here for all future postings

From: Stas Busygin (busygin_at_a-teleport.com)
Date: 08/01/04 

Date: Sun, 01 Aug 2004 12:46:41 -0400

Hi All,

Sterten wrote:
>
> we still have the task/problem to generate (all) dim2-posets by some operations
> like
> cloning, "." , etc. starting from trivial ones...
>

Since we can identify dim-2 posets with permutations, we may
consider instead generating permutations element-by-element.
Adding a new element J to a permutation i_0,i_1,...,i_{N-1}
over 0...N-1 can be done as follows:

1. Choose the position for J (a number from 0 to N).
2. Choose the value of J (another number from 0 to N).
3. The new permutation is j_0,j_1,...,J,...,j_N, where J is on
the chosen position and j_k=i_k if i_k<J, j_k=i_k+1 if i_k>=J.

 From the viewpoint of DAGs, step 1 is choosing what vertices
_might_ be successors of the new vertex, and step 2 is
assigning what are the successors actually.

Obviously, such operations as adding a successor of all
existing vertices, adding a new predecessor of all existing
vertices, vertex cloning, etc. are particular cases of the
permutation update scheme described above.

Regards,
Stas