References of "Nešetřil, Jaroslav"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailMinors of Boolean functions with respect to clique functions and hypergraph homomorphisms
Lehtonen, Erkko UL; Nešetřil, Jaroslav

in European Journal of Combinatorics (2010), 31(8), 1981-1995

Each clone C on a fixed base set A induces a quasi-order on the set of all operations on A by the following rule: f is a C-minor of g if f can be obtained by substituting operations from C for the ... [more ▼]

Each clone C on a fixed base set A induces a quasi-order on the set of all operations on A by the following rule: f is a C-minor of g if f can be obtained by substituting operations from C for the variables of g. By making use of a representation of Boolean functions by hypergraphs and hypergraph homomorphisms, it is shown that a clone C on {0,1} has the property that the corresponding C-minor partial order is universal if and only if C is one of the countably many clones of clique functions or the clone of self-dual monotone functions. Furthermore, the C-minor partial orders are dense when C is a clone of clique functions. [less ▲]

Detailed reference viewed: 44 (0 UL)