these

Informations

• Publié par: Sosul
• Nombre de lectures: 44
• Langue: English

Extrait

Universit´e Libre de Bruxelles Ann´ee acad´emique: 2001 - 2002
Facult´e des Sciences
D´epartement de Math´ematiques
Classification of some homogeneous
and ultrahomogeneous structures
Alice Devillers
Th`ese pr´esent´ee en vue de l’obtention
du grade de Docteur en Sciences
(orientation: math´ematiques) Promoteur: Jean DoyenRemerciements
J’aimerais avant tout remercier mon promoteur Jean Doyen, pour sa gentillesse
et sa disponibilit´e, pour avoir pass´e beaucoup de temps a` m’aider, a` me guider et
a` lire et critiquer ma prose. Je lui en suis tr`es reconnaissante.
Je voudrais ensuite remercier toutes les personnes qui m’ont aid´e de pr`es ou de
loin dans ma recherche: tout particuli`erement Jonathan Hall et Hendrik Van
Maldeghem, pour leurs nombreuses suggestions constructives, ainsi que Francis
Buekenhout, Peter Cameron, Paul Cohn, Anne Delandtsheer, Paul Van Praag,...
sans oublier Michel Sebille pour ses conseils et pour la premi`ere version du pro-
gramme MAGMA v´erifiant l’homog´en´eit´e.
Je remercie le Fonds National de la Recherche Scientifique, qui m’a support´e fi-
nanci`erementdurantmesann´eesdedoctorat,etleD´epartementdeMath´ematiques
qui m’a accueilli.
Des remerciements vont aussi `a mes coll`egues, des deux couloirs du huiti`eme,
pour l’excellente ambiance de travail (et autre) qui r`egne en nos bureaux. Je
pense en particulier `a Davy, Michel, Laurent, Benoˆıt, ainsi qu’aux informaticiens
de la pause-th´e.
Enfin, je voudrais remercier mes parents, ainsi que toute ma famille, pour leur
support constant (notamment mon p`ere qui m’a r´eguli`erement encourag´e par des
”Alors, cette th`ese, ¸ca avance?”). Je remercie´egalement tous mes amis (je ne vais
pas les citer, de peur d’en oublier), pour leur pr´esence durant ces longs mois de
travail.Contents
1 Introduction 3
1.1 Origins and motivations . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Fra?ıss´e’s theory and recent classification results . . . . . . . . . . 7
1.4 Some rank 2 geometries . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Semilinear spaces . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.2 Linear spaces . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.3 Steiner systems . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Survey of the main results obtained in this thesis . . . . . . . . . 13
2 Linear spaces 17
2.1 Homogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Ultrahomogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Homogeneous pairs (S;G) . . . . . . . . . . . . . . . . . . . . . . 31
3 Semilinear spaces 33
3.1 The non-connected case . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 The connected case . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.1 All antiflags are isomorphic . . . . . . . . . . . . . . . . . 39
12 CONTENTS
3.2.2 There are non-isomorphic antiflags . . . . . . . . . . . . . 62
3.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.4 Homogeneous pairs (S;G) . . . . . . . . . . . . . . . . . . . . . . 99
4 Steiner systems 105
4.1 Homogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.2 Ultrahomogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.3 Homogeneous pairs (S;G) . . . . . . . . . . . . . . . . . . . . . . 119
A Programs in MAGMA 121
A.1 Algorithm testing the homogeneity . . . . . . . . . . . . . . . . . 121
A.2 Algorithm testing the ultrahomogeneity . . . . . . . . . . . . . . . 125Chapter 1
Introduction
34 CHAPTER 1. INTRODUCTION
The aim of this thesis is to classify certain structures which are, from a certain
pointofview,ashomogeneousaspossible,thatiswhichhaveasmanysymmetries
aspossible. Amoreprecisedefinitionwillbegivenbelow,butthebasicideaisthe
following: a structureS is said to be homogeneous if, whenever two (finite) sub-
structuresS andS ofS areisomorphic, there isan automorphism ofS mapping1 2
S ontoS . The notion of ultrahomogeneity is stronger: in an ultrahomogeneous1 2
structureS, anyisomorphism between two (finite) substructures must be induced
by an automorphism ofS.
1.1 Origins and motivations
According to Mielants [68], the notion of homogeneity can be read between the
lines in some papers of Leibniz [60]: [...] all possible things tend toward exis-
tence [...] out of the infinite combinations and series of possible things, one exists
through which the greatest amount of essence or possibility is brought into exis-
tence. [...] perfection is the principle of existence [...]. One interpretation is
the following: Leibniz suggests that among all possible worlds, our world is the
one which realizes the maximum number of possibilities, which has the highest
possible harmony (this is of course a rather vague formulation of the notion of
homogeneity). Note that Leibniz uses these ideas to ”prove” the existence of
God.
An attested historical origin of the notion of ultrahomogeneity is the so-called
Helmoltz-Lie principle (or free mobility principle). Riemann asked in 1854 (in
?Uber die Hypothesen, welche der Geometrie zu Grunde liegen [75]) the following
question: in which (Riemannian) manifolds is it possible to move the shapes
without deformation? Inspired by this question, Helmoltz tried to characterize
Euclidean and non-Euclidean spaces (among all manifolds) by group properties
?(in Uber die Tatsachen, die der Geometrie zum Grunde liegen [50], 1868). One of
hiscrucialaxiomsisthefree-mobilityprinciple: bymotionany(finite)setofpoints
can be carried onto any congruent one. This axiom is inspired by the observation
3thatthispropertyholdsinthe3-dimensionalEuclideanspace E : ifS andS are1 2
3two isometric subsets of the Euclidean space E , then for every bijection ? from
S onto S such that dist(?(x);?(y)) = dist(x;y) for all x;y 2 S , there exists1 2 1
3 3an isometry fi of E extending ?. In other words, E (seen as a metric space) is
ultrahomogeneous. Around 1890, Lie [62] used the free-mobility axiom to attack
the Riemann and Helmoltz problems. See Freudenthal [44] for further historical
details.1.2. BASIC DEFINITIONS 5
Another early emergence of the notion of ultrahomogeneity can be found in the
observation by Georg Cantor in 1895 that the ordered set (Q;•) is ultrahomoge-
neous (he uses this fact in one of the proofs of his paper Beitr age zur Begrundung?
der transfiniten Mengenlehre, Part I [17]). Indeed, whenever x < x <¢¢¢ < x1 2 n
andy <y <¢¢¢<y arerationalnumbers,thereisanautomorphismfiof(Q;•)1 2 n
(that is an order preserving permutation ofQ) such that fi(x ) = y (1• i• n):i i
such an fi is clearly obtained by taking a piecewise linear mapping (linear on each
interval [x;x ] and with appropriate shifts at the two ends). Note that thisi i+1
property is no longer true if we allow infinite subsets ofQ. For example, if A=Z
1 1and B =f¡1+ ;1¡ jn2N g, there is no automorphism of (Q;•) mappingn n 02 2
A onto B because B is bounded and A is not.
In 1953, the French logician Roland Fra?ıss´e used (Q;•) as a prototype to study
ultrahomogeneous countable relational structures [40, 41, 42, 43]. He discovered
necessary and sufficient conditions for a class of finite relational structures to
be the set of finite substructures of an ultrahomogeneous countable relational
structure. We will give later a short account of his theory.
1.2 Basic definitions
Given a positive integer n, a n-ary relation on a non-empty set S is a subset
n‰ of S . We commonly use the terms unary, binary and ternary relations for
the 1-ary, 2-ary and 3-ary relations respectively. A relational structure is a pair
S = (S;R) where S is a non-empty set and R is a family of relations on S. A
relational structure is said to be of type hn i (where Λ is a finite or infinite‚ ‚2Λ
set of indices and the n ’s are positive integers) when R = f‰ g with ‰ an‚ ‚ ‚2Λ ‚
n -ary relation on S. In other words, a relational structure is an L-structure‚
(a model for the language L), where L is a first-order language containing only
relations, no functions and no constants (L is also called a relational language).
0If S is a non-empty subset of S, then the substructure (sometimes called induced
0 0 0(sub)structure) on S is the relational structure U = (S ;R ) having the sameS
0
0type as (S;R) and such that R is the restriction of R to S . More precisely, ifS
0 0 0n‚R=f‰ g , thenR 0 =f‰ g where ‰ =‰ \S .‚ ‚2Λ S ‚2Λ ‚‚ ‚
(1) (2)If S = (S ;f‰ g ) and S = (S ;f‰ g ) are two relational structures of1 1 ‚2Λ 2 2 ‚2Λ‚ ‚
the same type, an isomorphism fromS ontoS is a bijective map ` : S ¡! S1 2 1 2
preserving each relation, i.e. such that
(1) (2)
(fi ;fi ;:::;fi )2‰ ()(`(fi );`(fi );:::;`(fi ))2‰ :1 2 n 1 2 n‚ ‚ ‚ ‚6 CHAPTER 1. INTRODUCTION
IfS =S , such an isomorphism is called an automorphism ofS . The set of all1 2 1
automorphisms of a relational structure (S;R) is a subgroup of Sym(S), called
the automorphism group ofS =(S;R), and denoted by Aut(S;R) or AutS.
For example, an undirected graph is nothing else than a relational structure
(V;f‰g) of type h2i, where V is the vertex set of the graph and ‰ is the