[darcs-users] Write-up on "tree repositories" as an alternative to conflictors

[Ben Franksen]

Am 12.12.20 um 11:56 schrieb Ben Franksen:
> Another aspect not covered is that for permutivity to hold, we need not
> only ensure a /minimum/ number of parallel paths, but also a /maximum/
> number of intermediate contexts. The extreme case is the commuting
> hypercube of dimension n with n! different paths of length n (all
> permutations of n), sharing 2^n contexts (the corners of the hypercube).

Indeed, it should be possible to embed (inject) any patch graph into an
N-dimensional hypercube, where N is the set of natural numbers. I find
this view quite illuminating.

(We have to restrict names and contexts to (at most) countable sets,
which is not a serious limitation, since this will be the case in any
practical implementation anyway.)

The contexts correspond to corners i.e. elements of {0,1}^N, and the
patches correspond to edges. Edges representing patches are considered
directed "away from the origin". The names are the (mutually orthogonal)
"directions" in our space: two patches have the same name if and only if
they are /geometrically/ parallel as edges.

We even get a distinguished "empty context" for free (the origin).

Corners can be seen as sequences of bits (with only finitely many 1s),
and a patch p:s->t with name m corresponds to the triple (s,t,m) where
s(m)=0, t(m)=1, and s(i)=t(i) for all names i with i/=m.

Given two arbitrary corners s and t, all paths p:s->t must have the same
length n, which coincides with the size of name(p). In other words, they
lie inside a finite n-dimensional hyperface of the full N-cube.

What does permutivity mean in this picture? Or asked differently, how
can we characterize the valid patch graphs as a subset of the N-cube?

Cheers
Ben