Rigid and strongly rigid relations on small domains
Thesis or Dissertation
Abstract(s)
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]).
This document disseminated on Papyrus is the exclusive property of the copyright holders and is protected by the Copyright Act (R.S.C. 1985, c. C-42). It may be used for fair dealing and non-commercial purposes, for private study or research, criticism and review as provided by law. For any other use, written authorization from the copyright holders is required.