The Theory of 2-Structures

The following sections are included:

• Preface

• Contents

In this chapter we establish basic notions and notations concerning sets, partial orders; and (semi)groups that will be used in this book. We have omitted some of the proofs of the results in this chapter.

As we shall see in the forthcoming chapters, the theory of 2-structures is closely related to graph theory. Indeed, labelled 2-structures that we study from Chapter 8 onwards can be fully represented as edge coloured directed graphs. On the other hand, graphs will be treated as special cases of (labelled) 2-structures, and they will appear in many examples.

In this chapter we introduce the basic notions, and results for 2-structures. The most important notions here are those of a substructure and a clan both of which will play a central role throughout the book. Clans of 2-structures and their induced factors form a basis for the decomposition theorem of 2-structures that we consider in Chapter 5.

In this chapter we study some algebraic notions for 2-structures including quotients and homomorphisms. In universal algebra (and therefore in the theory of groups, rings, etc) homomorphisms and quotients are two different aspects of the same construction of algebras. As we shall see, this is also true for 2-structures, and hence we have two methods of constructing quotients g/X: a direct method using factorizations and an indirect method using homomorphisms. Unlike algebraic structures in general, 2-structures have a rather unusual and restrictive property: a quotient of a 2-structure g is always isomorphic to a substructure of g.

Decompositions are of special interest in mathematics and its applications, since they often provide tools for dividing complex problems into smaller parts, together with a method to link the solutions of the smaller problems into a solution of the original problem. Decompositions are thus special cases of the divide-and-conquer principle. The clan decomposition of 2-structures, also known as the substitution decomposition or the modular decomposition, is an example of such a method. In this decomposition a 2-structure g is divided into its maximal prime factors g₁,…,g_k, and a quotient 2-structure g/X is constructed to indicate the necessary relationships between these factors g_i.

Of the three special classes of 2-structures, linear and complete 2-structures are determined by (an ordering of) their domains, and therefore they need no further consideration. The only interesting special 2-structures are thus the primitive ones. Indeed, there are arbitrarily complex primitive 2-structures.

In an angular 2-structure true primitivity is forbidden at the lowest possible level, i.e., an angular 2-structure has no primitive substructures on three nodes. We shall study the primitivity (or more generally, the all-connectiveness) of these 2-structures. It turns out that the edge classes of a primitive angular 2-structure are limited in number, and this leads us to T-structures that can be considered as generalizations of transitivity of partial orders.

As we remarked in Chapters 4 and 5 the decompositions of 2-structures are not ‘characteristic’ in the sense that two different 2-structures may possess a common decomposition, and hence the same shape. This is due to the abstractness of giving the colouring by an equivalence relation of the edges. In labelled 2-structures, that are studied in this and the following chapters, this ambiguity does not occur, because a labelling of the edges will give each edge a concrete colour (or a label), and in this fashion the substructures and quotients of labelled 2-structures keep their identifications (labels od edges) given to them by their mother 2-structure. In graph theoretic terminology, labelled 2-structures are edge coloured directed complete graphs.

In this chapter we consider primitivity of reversible ℓ2-structures. The results on primitivity from Chapter 6 can easily be modified to labelled 2-structures. So rather than consider these modifications, we will look now at the heredity of primitive 2-structures through unstable ℓ2-structures. In particular, we consider the problem of ‘removing edges’ (in a specific way) from a primitive g so that the remaining ℓ2-structure is still primitive – this leads to the unstable labelled 2-structures.

A homoluorphism is a mapping that preserves some of the structural properties of a given (labelled) 2-structure that is mapped into another. In particular, an isomorphism determines that two labelled 2-structures have the same algebraic properties. In this chapter we consider automorphisms of ℓ2-structures. The mere existence of a nontrivial automorphism means that a given ℓ2-structure g has some inner symmetry – and the larger the automorphism group of g, the more symmetry it has. We shall see that no matter what finite group is chosen, one can always design an ℓ2-structure whose automorphism group is exactly this given group.

In this chapter we give an introduction to the theory of switching of graphs (also known as Seidel switching for undirected graphs), which provides an operation to transform graphs to other graphs. A graph will be represented as an ℓ2-structure g: E₂(D) → ℤ₂, where ℤ₂ is the cyclic group of two elements. The operation of switching defines an action on the graphs that gives a partition of the family of graphs (on a given domain) into equivalence classes that will be called switching classes. In the following chapters we generalize this approach to arbitrary ℓ2-structures with a group of labels. Although in switching of graphs the group of labels is the simplest nontrivial one (ℤ₂), the theory of switching classes contains a wealth of results – only part of them is covered in this book.

Quite often in a valuation of objects of a mathematical structure the values come from a set that is itself structured. Frequently such a set is an algebraic structure, where the elements are bound together by one or more operations. In graph theory the values of objects (the labels of edges or nodes) are often taken from an algebraic structure; e.g., in many optimization problems such as the shortest path problem, the edges are labelled by elements of the field (ℝ, +, ·) of real numbers.

The algebraic structure of the group of labels in ℓ2-structures allows to define groups of selectors as in the case of graphs in Chapter 11. If the group Δ is abelian, then the Δ^δ2-structures on a given domain form a group. In the approach that we take, this is not true in general for nonabelian groups.

Clans played a central role in the decomposition of 2-structures. In this chapter we shall consider the structure of the switching classes with respect to the family of clans of a Δ^δ2-structures. We show that the clans, although they have different (closure) properties for switching classes than for ℓ2-structures, still give a decomposition of the switching classes through quotients and the so-called plane trees that are associated with the Δ^δ2-structures having horizons.

In this chapter we consider the relationship between a Δ2-structure g (with the inversion as its involution) and its image h obtained by applying a selector to g. In particular, we study invariant properties of ℓ2-structures, and show that the invariants are closely related to the verbal identities of the group Δ of labels.

The following sections are included:

• Bibliography

• Notations

• Index