A. Ehrenfeucht, T. Harju and G. Rozenberg

Theory of 2-Structures

Contents

• Preface vii

1. Preliminaries

   • 1.1 Notations 1
   • 1.1.1 Sets and functions 1
   • 1.1.2 Closure operators 3
   • 1.1.3 Relations 4
   • 1.1.4 Equivalence relations 6
   • 1.2 Partial orders 8
   • 1.2.1 Downsets 8
   • 1.2.2 Order embeddings 9
   • 1.2.3 Linear orders 10
   • 1.3 Semigroups and groups 11
   • 1.3.1 Notations for semigroups and monoids 11
   • 1.3.2 Free monoids (with involution) 12
   • 1.3.3 Preliminaries on groups 14
   • 1.3.4 Group actions 16
   • 1.3.5 Free groups, commutators and verbal identities 17

2. Graph Theoretical Preliminaries

   • 2.1 Directed and Undirected Graphs 21
   • 2.1.1 Basic notions 21
   • 2.1.2 Connectivity of graphs 24
   • 2.1.3 Some special graphs 25
   • 2.2 Comparability graphs 27
   • 2.2.1 Transitively oriented graphs 27
   • 2.2.2 Permutation graphs and cographs 29
   • 2.2.3 Construction trees of cographs 31

3. 2-Structures and Their Clans

   • 3.1 Introduction and representations 35
   • 3.1.1 Definition of a 2-structure 35
   • 3.1.2 Isomorphic 2-structures 37
   • 3.1.3 Reversibility 38
   • 3.2 Substructures and clans 39
   • 3.2.1 Substructures, clans and factors 39
   • 3.2.2 Refinements and similarity 41
   • 3.2.3 Reversible version 42
   • 3.2.4 Graphs and packed components 43
   • 3.2.5 Some special 2-structures 46
   • 3.3 Closure properties of clans 47
   • 3.3.1 Basic closures 47
   • 3.3.2 Sibas: set theoretic closure properties 49
   • 3.3.3 Clans of factors 51
   • 3.4 Prime clans 52
   • 3.4.1 Prime members in sibas 52
   • 3.4.2 Minimal overlapping clans 53

4. Quotients and Homomorphisms

   • 4.1 Quotients 57
   • 4.1.1 Factorizations and quotients 57
   • 4.1.2 Homomorphisms 59
   • 4.1.3 Natural epimorphisms and decompositions 61
   • 4.2 Clans and epimorphisms 63
   • 4.2.1 Homomorphism theorem 63
   • 4.2.2 Prime clans in quotients 66
   • 4.2.3 Primitive quotients 68
   • 4.3 Other operations 70
   • 4.3.1 Premorphisms 70
   • 4.3.2 Extensions 71

5. Clan Decomposition

   • 5.1 The clan decomposition theorem 75
   • 5.1.1 Maximal prime clans 75
   • 5.1.2 Special sibas and 2-structures 77
   • 5.1.3 The clan decomposition theorem 79
   • 5.1.4 The relationship of sibas to 2-structures 81
   • 5.2 The shape of a 2-structure 83
   • 5.2.1 The shape and its representation as a tree 83
   • 5.2.2 Same shapes 84
   • 5.3 A construction of prime clans 87
   • 5.3.1 A construction of clans 87
   • 5.3.2 A construction of prime clans 88

6. Primitive 2-Structures

   • 6.1 Small primitive substructures 91
   • 6.1.1 Uniformly imprimitive 2-structures 91
   • 6.1.2 Primitive substructures of 3 or 4 nodes 93
   • 6.2 Hereditary properties 96
   • 6.2.1 Local and global nodes 96
   • 6.2.2 Hereditary properties 98
   • 6.3 Critically primitive 2-structures 99
   • 6.3.1 The parity theorem 99
   • 6.3.2 The list of critically primitive 2-structures 102

7. Angular 2-Structures

   • 7.1 Angularity 109
   • 7.1.1 All-connectivity 109
   • 7.1.2 All-connected skew angular 2-structures 113
   • 7.2 T-structures 116
   • 7.2.1 T-structures and partial orders 116
   • 7.2.2 $T_2$-structures 118
   • 7.3 Linear orders and Schr\" o der numbers 121
   • 7.3.1 Bi-orders and linear orders 121
   • 7.3.2 Uniformly imprimitive linear orders 122
   • 7.3.3 Parenthesis words and Schr\" o der numbers 124

8. Labelled 2-Structures

   • 8.1 Introduction to $\ell $2-structures 129
   • 8.1.1 Definitions 129
   • 8.1.2 Substructures, clans and quotients 132
   • 8.2 Clan decomposition of $\ell $2-structures 135
   • 8.2.1 Uniqueness of decompositions 135
   • 8.2.2 The shape of an $\ell $2-structure 138
   • 8.2.3 Extensions 139
   • 8.3 Graphs and their representations 142
   • 8.3.1 Graphs as $\ell $2-structures 142
   • 8.3.2 On comparability graphs 143

9. Unstable Labelled 2-Structures

   • 9.1 Triangle free and unstable $\ell $2-structures 147
   • 9.1.1 Removable edges 147
   • 9.1.2 Internal and external nodes 150
   • 9.1.3 Triangle-free $\ell $2-structures 151
   • 9.2 Heredity in unstable $\ell $2-structures 155
   • 9.2.1 The partition of nodes 155
   • 9.2.2 Alternating structures 156
   • 9.2.3 Degrees of nodes 157
   • 9.3 A composition of unstable $\ell $2-structures 159
   • 9.3.1 A constructive reduction of primitive $\ell $2-structures 159
   • 9.3.2 Pendant components 161

10. Automorphisms of Labelled 2-Structures

    • 10.1 Label preserving automorphisms 165
    • 10.1.1 The $\ell $-automorphism groups 165
    • 10.1.2 Transitivity 167
    • 10.1.3 Automorphic actions on factors 169
    • 10.1.4 Universality of $\ell $-automorphism groups 172
    • 10.2 Nonpreserving automorphisms 175
    • 10.2.1 Connections to $\ell $-automorphisms 175
    • 10.2.2 Transitivity and associated permutations 176
    • 10.2.3 Representing labels by automorphisms 178

11. Switching of Graphs

    • 11.1 Introduction to switching 181
    • 11.1.1 Definitions 181
    • 11.1.2 The group of graphs 183
    • 11.1.3 Switching classes 185
    • 11.2 Structural properties of switching classes 188
    • 11.2.1 A local characterization 188
    • 11.2.2 Automorphisms 190
    • 11.3 Special problems on undirected graphs 193
    • 11.3.1 Two-graphs 193
    • 11.3.2 Eulerian graphs 194
    • 11.3.3 Pancyclic graphs 195
    • 11.3.4 Trees 197

12. Labelled Structures over Groups

    • 12.1 Introduction 203
    • 12.1.1 Groups and involutions 203
    • 12.1.2 Selectors and switching classes 205
    • 12.2 An interpretation in networks 207
    • 12.2.1 Concurrent behaviour in networks 207
    • 12.2.2 Reducing the actions to groups 208
    • 12.2.3 Introducing reversibility 210
    • 12.3 Examples for some special groups 211
    • 12.3.1 The cyclic groups $\@mathbb Z_3$ and $\@mathbb Z_4$ 211
    • 12.3.2 The symmetric group $S_3$ 213

13. Clans of Switching Classes

    • 13.1 Associated groups 215
    • 13.1.1 The group of selectors 215
    • 13.1.2 The group of abelian switching classes 217
    • 13.2 Clans and horizons 219
    • 13.2.1 Spanning trees 219
    • 13.2.2 Horizons and constant selectors 220
    • 13.2.3 Clans 222
    • 13.3 Cardinalities of switching classes 224
    • 13.3.1 Some special cases 224
    • 13.3.2 Centralizers 224
    • 13.3.3 Some improvements 228

14. Quotients and Plane Trees

    • 14.1 Quotients of switching classes 231
    • 14.1.1 Closure properties of clans 231
    • 14.1.2 Quotients 233
    • 14.2 Planes and plane trees 234
    • 14.2.1 Planes 234
    • 14.2.2 Plane trees 237
    • 14.2.3 Bijective correspondence of plane trees 239
    • 14.2.4 Forms 243

15. Invariants

    • 15.1 Free invariants 245
    • 15.1.1 General invariants 245
    • 15.1.2 Edge monoids 246
    • 15.1.3 Variable functions and free invariants 247
    • 15.2 Group properties of free invariants 250
    • 15.2.1 Abelian property 250
    • 15.2.2 Graphs of words 252
    • 15.2.3 Verbal identities 255
    • 15.3 Invariants on abelian groups 258
    • 15.3.1 Independency of free invariants 258
    • 15.3.2 Complete sets of invariants 259
    • 15.4 Invariants on nonabelian groups 261
    • 15.4.1 General observations 261
    • 15.4.2 Central characters 262
    • 15.4.3 A characterization theorem 265

• Bibliography 269
• Notations 279
• Index 283