No description available.

The purpose of this thesis is to add to the structure theory of Aronszajn orderings. We shall focus essentially in four topics. The first topic of discussion is about the relation between Lipschitz and coherent trees. I will demonstrate that the tree $T(\rho_0)$ is coherent without any extra set theoretic hypothesis. The second topic presents an application of Todorcevic's $\rho$ functions to provide some partial answers to an old question of Juhaz asking whether a standard weakening of Jensen's diamond principle implies the existence of Suslin trees. In the third topic we focus on providing a satisfactory rough classification result of the class of Aronszajn lines. Our main result is that, assuming PFA, the class of Aronszajn lines is well-quasi-ordered by embeddability. The last topic is an investigation of the gap structure of the class of coherent Aronszajn trees. I will show that, assuming PFA, the class of coherent Aronszajn trees quasi-ordered by embeddability is the unique saturated linear order of cardinality $\aleph_2$.

The purpose of this thesis is to add to the structure theory of Aronszajn orderings. We shall focus essentially in four topics. The first topic of discussion is about the relation between Lipschitz and coherent trees. I will demonstrate that the tree $T(\rho_0)$ is coherent without any extra set theoretic hypothesis. The second topic presents an application of Todorcevic's $\rho$ functions to provide some partial answers to an old question of Juhaz asking whether a standard weakening of Jensen's diamond principle implies the existence of Suslin trees. In the third topic we focus on providing a satisfactory rough classification result of the class of Aronszajn lines. Our main result is that, assuming PFA, the class of Aronszajn lines is well-quasi-ordered by embeddability. The last topic is an investigation of the gap structure of the class of coherent Aronszajn trees. I will show that, assuming PFA, the class of coherent Aronszajn trees quasi-ordered by embeddability is the unique saturated linear order of cardinality $\aleph_2$.

No description available.

This paper will be concerned with some fundamental properties of a line. In particular, fundamental ordering properties of a line segment are covered.

A crease pattern is an embedded planar graph on a piece of paper. An m × n map is a rectangular piece of paper with a crease pattern that partitions the paper into an m × n regular grid of unit squares. If a map has a configuration such that all the faces of the map are stacked on a unit square and the paper does not self-intersect, then it is flat foldable, and the linear ordering of the faces is called a valid linear ordering. Otherwise, the map is unfoldable. In this thesis, we show that, given a linear ordering of the faces of an m × n map, we can decide in linear time whether it is a valid linear ordering or not. We also define a class of unfoldable 2 × n crease patterns for every n ≥ 5. / Graduate / 0984

No description available.

Le cadre général de cette thèse est celui de la propriété d’indépendance en théorie des modèles. Les théories sans cette propriété sont appelées NIP ou dépendantes. L’objectif principal est de trouver de nouveaux exemples de théories appartenant à cette classe. Nous montrons d’abord un résultat isolé qui répond une question de Pillay : dans un groupe NIP possédant une partie infinie de classe de nilpotence finie, on y trouve un sous-groupe définissable de même classe de nilpotence et contenant cette partie infinie. Le reste de la thèse est motivé par deux cadres extrêmement proches : les groupes abéliens munis d’une chaîne de sous-groupes uniformément définissables, et les groupes abéliens valués. Dans le premier cas nous identifions une certaine théorie et nous étudions plusieurs extensions de cette théorie. Nous prouvons une élimination des quantificateurs dans chacune des ses extensions, grâce à laquelle la NIP en découle facilement. Le dernier résultat est le plus substantiel. Nous montrons qu’une théorie naturelle de chaîne colorée munie quasi-automorphismes n’a pas la propriété d’indépendance. Nous appliquons ensuite ce résultat à une certaine théorie de groupes valués, étudiée par Simonetta dans le contexte des groupes C-minimaux, pour en conclure qu’elle est NIP. Nous montrons aussi d’une façon assez directe (en utilisant des résultats de Rubin et Poizat) qu’une chaîne colorée munie d’automorphismes est NIP. / This PhD thesis is in the general area of the independence property in model theory.Theories without this property are called NIP or dependent. The main objective of this thesis is to find new examples belonging to this class. Firstly, we prove an isolated result that answers a question stated by Pillay : if a NIP group contains an infinite set of finite nilpotency class, then there exists a definable subgroup of the same nilpotency class containing this set. The rest of this thesis is motivated by two extremely closed related contexts : abelian groups equipped with an uniformly definable chain of subgroups, and valued groups. In the first case we identify a theory and study several extensions of it. We prove quantifier elimination in each of these extensions, and use it to easily conclude that they are NIP. The last result is the most significant one. We prove that a natural theory of linear orderings equipped with quasi-automorphisms doesn’t have the independence property. Then we apply this result to a particular theory of valued abelian groups, which has been studied by Simonetta in the context of C-minimal groups, to conclude that it is NIP. We also prove in a rather straightforward way (using results by Rubin and Poizat) that a linear ordering equipped with automorphisms is NIP

Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité (défini comme la plus grande taille d'un stable), et les stables se classent certainement parmi les structures les plus simples et fondamentales en théorie des graphes.<p><p>La thèse est divisée en deux parties, toutes deux liées à la notion de stables dans un graphe. Dans la première partie, nous étudions un problème de coloration de graphes, c'est à dire de partition en stables, où le but est de minimiser l'entropie de la partition. C'est une variante du problème classique de minimiser le nombre de couleurs utilisées. Nous considérons aussi une généralisation du problème aux couvertures d'ensembles. Ces deux problèmes sont appelés respectivement minimum entropy coloring et minimum entropy set cover, et sont motivés par diverses applications en théorie de l'information et en bioinformatique. Nous obtenons entre autres une caractérisation précise de la complexité de minimum entropy set cover :le problème peut être approximé à une constante lg e (environ 1.44) près, et il est NP-difficile de faire strictement mieux. Des résultats analogues sont prouvés concernant la complexité de minimum entropy coloring.<p><p>Dans la deuxième partie de la thèse, nous considérons les graphes dont le nombre de stabilité augmente dès qu'une arête est enlevée. Ces graphes sont dit être "alpha-critiques", et jouent un rôle important dans de nombreux domaines, comme la théorie extrémale des graphes ou la combinatoire polyédrique. Nous revisitons d'une part la théorie des graphes alpha-critiques, donnant à cette occasion de nouvelles démonstrations plus simples pour certains théorèmes centraux. D'autre part, nous étudions certaines facettes du polytope des ordres totaux qui peuvent être vues comme une généralisation de la notion de graphe alpha-critique. Nous étendons de nombreux résultats de la théorie des graphes alpha-critiques à cette famille de facettes.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished