Re: Functionally complete/universal basis for graph homomorphisms?

[Mike Stay <metaweta@gmail.com>]

Thanks for all the responses so far.  It's been pointed out to me that
my post used some terms in a vague way, so let me try to be a little
more precise.  Let B = {0,1} and NAND: B^2 -> B be the usual NAND
function.  Then any function B^n -> B can be expressed as the
composition of a finite number of uses of the diagonal function
D:B->B^2, projections, permutations, and NAND.

Let Omega be the subgraph classifier described below.  I'm working
with the topos of reflexive directed multigraphs, that is, graphs
whose vertices are equipped with a chosen self-edge and that allow
multiple parallel directed edges between any pair of vertices.  I
suspect that any graph homomorphism from Omega^n to Omega (where
finite powers are given by the categorical product) can be expressed
as the composition a finite number of uses of the diagonal graph
homomorphism D:Omega -> Omega^2, projections, permutations, and some
finite number of operations with signature Omega^2 -> Omega.

My best guess at a such a set of operations is
     1. Map all vertices of Omega^2 to t and apply NAND to the edges,
treating "in" as true and all the "outs" as false,
     2. NAND together the vertices.  Edges between any of (t,f), (f,t),
and (f,f) map to in and the others map to the appropriate outs, and
     3. (t,t) maps to t; the rest of the vertices map to f.  (in, in)
maps to in; the rest of the edges map to the appropriate outs.

I would like to know if
     a. a single set of operations suffices for all n
     b. if so, what the smallest size of such a set is and an example
of such a minimal set
     c. if not, how the size of the necessary set grows with n.

Thanks!

On Mon, Sep 25, 2017 at 10:17 PM, Mike Stay <metaweta@gmail.com> wrote:
> The Sheffer stroke / NAND gate suffices to implement any function from
> 2^n -> 2.  I'm looking for a similar universal basis for graph
> homomorphisms from Omega^n -> Omega, where Omega is the subgraph
> classifier with two vertices t, f and five edges
>
>    in:t->t, out1:t->t, out2:t->f, out3:f->t, out4:f->f.
>
> There's obviously a finite set of operations that covers all graph
> homomorphisms from Omega^n to Omega, because the set of all operations
> of that form is finite. But how small can that set be? I'd be
> satisfied with a formula parametric in n, but surprised if it actually
> depends on n; I'd expect it to be a finite set of binary operations.
>
> --
> Mike Stay - metaweta@gmail.com
> http://www.cs.auckland.ac.nz/~mike
> http://reperiendi.wordpress.com
>


-- 
Mike Stay - metaweta@gmail.com
http://www.cs.auckland.ac.nz/~mike
http://reperiendi.wordpress.com


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]