Re: Functionally complete/universal basis for graph homomorphisms?

[Gershom B <gershomb@gmail.com>]

Dear Mike,

I don't have an answer for this precise question, but, assuming I
understand your question, I do have a reference for a general approach
that can provide a potential lower bound on the number of such
operations.

Take a look at "Homological Computations for Term Rewriting Systems"
by Philippe Malbos and Samuel Mimram:
http://math.univ-lyon1.fr/~malbos/Art/hcTRS.pdf

It uses some rather heavyweight abstract homology theory but produces
a purely mechanical procedure for obtaining results (though the
authors to my knowledge haven't yet implemented a computer program to
perform this automatically).

Cheers,
Gershom


On Tue, Sep 26, 2017 at 12:17 AM, 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
>
>
> [For admin and other information see: http://www.mta.ca/~cat-dist/ ]


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