Indecomposable binary structures (09frg149)

Objectives

To begin, we will try to decompose general combinational structures, called binary structures, which are comparable to 2-structures introduced by Ehrenfeucht and Rozenberg in 1990 but whose handling should be easier, for instance, to define a new type of connectivities. These connectivities will allow for a simple proof of a generic decomposition theorem.
As for Gallai's theorem, this result should be false for infinite binary structures. By applying several times such a decomposition theorem, we obtain the decomposition tree. The decomposition tree of a finite binary structure will be examined. In the infinite case, we will use strengthenings of the notion of module, in the same way as for infinite graphs, to describe a more complicated decomposition process. For example, Hahn, Ille and Woodrow (2007) described the family of the modules of Sabidussi graphs. In fact, the family of the modules of a directed graph or of a binary structure share the same properties as the family of the intervals of a total order: for instance, the intersection of two modules is a module, the union of two modules which intersect is a module,... Hence, we may consider, without an underlying binary structure, a family of subsets of a given set which satisfy these properties. Such a family is called a weakly partitive family. Weakly partitive families on infinite sets were first studied by Ille in 1991 and then were well described by Ille and Woodrow (2008). Recently, Villemaire has been interested in monadic theory of such families.

The decomposition theorems emphasize the importance of indecomposability. In fact, almost all combinational structures are indecomposable and the decomposition theorems are ineffective on them. The structural study of indecomposability appears naturally; it constitutes our first research interest. Since almost all structures are indecomposable, the attempted results on indecomposability should be as follows. Given an indecomposable and finite binary structure, for which cardinalities does the structure admit an indecomposable substructure. Intuitively, the more decomposable substructures an indecomposable binary structure possesses, the more we will be able to describe it. The first results on indecomposable and finite binary structures are due to Sumner (1972), Ehrenfeucht and Rozenberg (1990) and Schmerl and Trotter (1993) who characterized the critical indecomposable binary structures, that is, the indecomposable binary structures becoming decomposable after removing every vertex. Then, Ille (1997), Cournier and Ille (1998) and Boudabbous and Ille (2008) also obtained important results on indecomposability.
Concerning the indecomposable and infinite binary structures, we refer to the compactness theorem due to Ille (1994) and to the recent characterization of
the critical indecomposable and infinite binary structures obtained by Boudabbous and Ille (2007).

The following duality theorem is due to Gallai (1967). Given two orders which share the same comparability graph, if one of them is indecomposable, then they are equal up to duality. This theorem was generalized to a wide class of directed graphs including tournaments by Boussa"{i}ri, Ille, Lopez and Thomass'e in 2004 by using the structural results on indecomposability. Duality theorems and structural results on indecomposability are also useful in Fra"{i}ss'e reconstruction. For example, concerning the reconstruction of orders, Ille and Rampon proved in 1998 that two hypomorphic orders which share the same comparability graph are isomorphic. In Ulam reconstruction framework, Ille (1993) proved the recognition of indecomposability. Other types of indecomposability recognition were shown by
Boussa"{i}ri and Ille (2008).

The Ph.D. Thesis of Sayar is supervised by Boudabbous and Ille. He has been working on indecomposability since his Master's in 2006.
This focussed research group will allow him to meet other specialists of the area. Lastly, Ille is writing a book on indecomposable binary structures and he will present some of its chapters during the workshop.