Rigid and strongly rigid relations on small domains

Abstract

Les relations fortement rigides jouent un rôle important dans l’étude de la complexité des problèmes de satisfaction de contraintes (CSPs) (Feder et Vardi [22], Schaefer [9], Jeavons [23], Bulatov, Jeavons et Krokhin [24], Larose et Tesson [34], Larose [31], Barto et Kozik [36], et Bulatov, Jeavons et Krokhin [27]) qui font l’objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle (Russell et Norvig [19]). Une relation n-aire r sur un ensemble U est rigide si elle n’admet aucun automorphisme non-trivial ; elle est fortement rigide si elle n’est préservée que par les projections. De plus r est dite projective si les seules opérations idempotentes qui la préservent sont les projections.

Rosenberg (1973) a caracterisé toutes les relations fortement rigides sur un ensemble à deux éléments, et a construit une relation binaire fortement rigide sur tout ensemble de plus de deux éléments. Larose et Tardif (2001) ont étudié les graphes projectifs et fortement rigides, et ont construit de grandes familles de graphes fortement rigides. Łuczak et Nešetˇril (2004) ont démontré une conjecture de Larose and Tardif qui prévoyait que la plupart des graphes avec suffisamment de sommets sont projectifs, et ont caractérisé tous les graphes homogènes qui sont projectifs. Łuczak et Nešetˇril (2006) ont ensuite confirmé une conjecture de Rosenberg qui prédisait que la plupart des relations sur un ensemble suffisamment grand sont fortement rigides.

Le premier résultat principal de cette thése est une caractérisation des relations fortement rigides sur un ensemble d’au moins 3 éléments, résolvant ainsi un problème ouvert de Rosenberg (Rosenberg [7], Problème 6 de [13]). Ensuite nous montrons qu’à isomorphisme près, il n’existe que 4 relations binaires rigides sur un ensemble à trois éléments, parmi lesquelles deux seulement sont fortement rigides. De plus, nous déterminons, à isomorphisme près, les 40 relations binaires rigides sur un univers à quatre éléments, et montrons que 25 d’entre elles sont fortement rigides (Exemple 5.4 et Exemple 6.1 dans Sun [41]). Nous généralisons une de ces relations pour construire une nouvelle relation binaire fortement rigide sur tout ensemble d’au moins 4 éléments (Sun [43]), et décrivons de plus une relation ternaire fortement rigide sur tout ensemble fini avec au moins 2 éléments et conjecturons une relation k-aire fortement rigide sur tout domaine fini (Sun [42]).

Strongly rigid relations play an important role in the study of the complexity of Constraint Satisfaction Problems (CSPs) (Feder and Vardi [22], Schaefer [9], Jeavons [23], Bulatov, Jeavons and Krokhin [24], Larose and Tesson [34], Larose [31], Barto and Kozik [36], and Bulatov, Jeavons and Krokhin [27]) which are the subject of intense research in both artificial intelligence and operations research (Russell and Norvig [19]). An n-ary relation r on a set U is strongly rigid if it is preserved only by trivial operations. It is projective if the only idempotent operations in Polr are projections.

Rosenberg (1973) characterized all strongly rigid relations on a set with two elements and found a strongly rigid binary relation on every domain U of at least 3 elements. Larose and Tardif (2001) studied the projective and strongly rigid graphs, and constructed large families of strongly rigid graphs. Łuczak and Nešetˇril (2004) settled in the affirmative a conjecture of Larose and Tardif that most graphs on a large set are projective, and characterized all homogenous graphs that are projective. Łuczak and Nešetˇril (2006) confirmed a conjecture of Rosenberg that most relations on a big set are strongly rigid.

In this thesis we characterize all strongly rigid relations on a set with at least three elements to answer an open question by Rosenberg (1973) (Rosenberg [7], Problem 6 in Rosenberg [13]). We classify the binary relations on the 3-element domain and demonstrate that there are merely 4 pairwise nonisomorphic rigid binary relations on the same domain (among them 2 are pairwise nonisomorphic strongly rigid), and we classify the binary relations on the 4-element domain and show that there are merely 40 pairwise nonisomorphic rigid binary relations on the same domain (among them 25 are pairwise nonisomorphic strongly rigid) (Example 5.4 and Example 6.1 in Sun [41]). We extend a strongly rigid relation on a 4-element domain to any finite domain (Sun [43]). Finally, we give a strongly rigid ternary relation on any finite domain and conjecture a strongly rigid k-ary relation on any finite domain (Sun [42]).