these
137 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

these

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
137 Pages
English

Description

Universit´e Libre de Bruxelles Ann´ee acad´emique: 2001 - 2002Facult´e des SciencesD´epartement de Math´ematiquesClassification of some homogeneousand ultrahomogeneous structuresAlice DevillersTh`ese pr´esent´ee en vue de l’obtentiondu grade de Docteur en Sciences(orientation: math´ematiques) Promoteur: Jean DoyenRemerciementsJ’aimerais avant tout remercier mon promoteur Jean Doyen, pour sa gentillesseet sa disponibilit´e, pour avoir pass´e beaucoup de temps a` m’aider, a` me guider eta` 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 deloin dans ma recherche: tout particuli`erement Jonathan Hall et Hendrik VanMaldeghem, pour leurs nombreuses suggestions constructives, ainsi que FrancisBuekenhout, 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´ematiquesqui 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. Jepense en particulier `a Davy, Michel, Laurent, Benoˆıt, ainsi qu’aux informaticiensde la pause-th´e.Enfin, je voudrais remercier mes parents, ainsi que toute ...

Subjects

Informations

Published by
Reads 44
Language English

Exrait

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 binary
0adjacency relation ((v ;v ) 2 ‰ () v and v are adjacent in the graph). If V1 2 1 2
0is a subset of V, the induced structure on V is just the usual induced subgraph
0on V . An isomorphism between two graphs is a bijection between their vertex
sets mapping adjacent vertices onto adjacent vertices and non-adjacent vertices
onto non-adjacent vertices, and so it is an isomorphism in the usual sense. The
automorphism group of a graph has also the usual sense.
Nowwehavealltheingredientstodefined-ultrahomogeneousandd-homogeneous
relational structures.
Given a positive integer d, a relational structure S = (S;R) is said to be d-
ultrahomogeneous if each isomorphism between the induced structures on two
subsets of S of cardinality at most d can be extended into an automorphism ofS.
A relational structure S = (S;R) is said to be d-homogeneous if, whenever the
structures induced on two subsets S and S of S of cardinality at most d are1 2
isomorphic, there is at least one automorphism of S mapping S onto S . Note1 2
that if we call i¡orbit of S any orbit of the automorphism group of S on the
i-subsets of S, an equivalent way of defining the d-homogeneity of S is as follows:
if S and S are in different i-orbits of S (for any i• d), then the substructures1 2
induced byS on S and S are non-isomorphic.1 2
S is called ultrahomogeneous (resp. homogeneous) if it is d-ultrahomogeneous
(resp. d-homogeneous) for all positive integers d.
We will also consider later the following generalization of these definitions. Let
S be a relational structure and let G be a subgroup of its automorphism group.
If d is a given positive integer, the pair (S;G) is said to be d-ultrahomogeneous
if each isomorphism between the substructures induced on two subsets of S of
cardinality at most d can be extended into an element of G. The pair (S;G) is
called ultrahomogeneous if (S;G) is d-ultrahomogeneous for all positive integers
d. Thenotionsofd-homogeneity andhomogeneity forapair(S;G)aredefinedin
a similar way. Oviously, with these definitions, S is called d-(ultra)homogeneous
whenever (S;AutS) is d-(ultra)homogeneous.