Decomposition tree of a lexicographic product of binary structures

Given a set S and a positive integer k, a binary structure is a function B:(S×S)∖{(x,x);x∈S}⟶{1,…,k}. The set S is denoted by V(B) and the integer k is denoted by rk(B). With each subset X of V(B) associate the binary substructure B[X] of B induced by X defined by B[X](x,y)=B(x,y) for any x≠y∈X. A subset X of V(B) is a clan of B if for any x,y∈X and v∈V(B)∖X, B(x,v)=B(y,v) and B(v,x)=B(v,y). A subset X of V(B) is a hyperclan of B if X is a clan of B satisfying: for every clan Y of B, if X∩Y≠0̸, then X⊆Y or Y⊆X. With each binary structure B associate the family Π(B) of the maximal proper and nonempty hyperclans under inclusion of B. The decomposition tree of a binary structure B is constituted by the hyperclans X of B such that Π(B[X])≠0̸ and by the elements of Π(B[X]). Given binary structures B and C such that rk(B)=rk(C), the lexicographic product B⌊C⌋ of C by B is defined on V(B)×V(C) as follows. For any (x,y)≠(x′,y′)∈V(B)×V(C), B⌊C⌋((x,x′),(y,y′))=B(x,y) if x≠y and B⌊C⌋((x,x′),(y,y′))=C(x′,y′) if x=y. The decomposition tree of the lexicographic product B⌊C⌋ is described from the decomposition trees of B and C.

► We describe the decomposition tree of a lexicographic product. ► We characterize the clans whose second projection is not a clan. ► We characterize the hyperclans whose first projection is a singleton. ► We study the hyperclans which are not limits. ► We provide a simple expression of the labeling function.