Dissertations / Theses on the topic 'Combinatoire géométrique'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Combinatoire géométrique.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
Sage, Marc. "Combinatoire algébrique et géométrique des nombres de Hurwitz." Phd thesis, Université Paris-Est, 2012. http://tel.archives-ouvertes.fr/tel-00804228.
Siegel, Anne. "Représentations géométrique, combinatoire et arithmétique des systèmes subsitutifs de type Pisot." Aix-Marseille 2, 2000. http://www.theses.fr/2000AIX22075.
Skapin, Xavier. "Utilisation du produit cartésien en modélisation géométrique 4D pour l'animation." Poitiers, 2001. http://www.theses.fr/2001POIT2301.
We work in the scope of 4D (space-time) modelling for animation. Extending 3D modelling methods to dimension 4 is the main advantage of 4D modelling, but interpreting a 4D object as an animation and controlling the construction of this object are the main drawbacks of 4D modelling. Our method uses space-time objects of dimension lesser than 4 as operands of the cartesian product operation to create an object of greater dimension, whose interpretation is deduced from operands'. We made a case study about cartesian product of basic operands defined as point trajectories. This study led to a method for interpreting and controlling 4D objects resulting from cartesian product. We have created a topologically-based 4D geometrical modeler, allowing us to design elaborate animations. We have adapted cartesian product operation to semi-simplicial sets, generalized maps, n-maps and closed chains of maps. Each of these definitions corresponds to an algorithm with an optimal complexity in time
Ledent, Jérémy. "Sémantique géométrique pour la calculabilité asynchrone." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLX099/document.
The field of fault-tolerant protocols studies which concurrent tasks are solvable in various computational models where processes may crash. To answer these questions, powerful mathematical tools based on combinatorial topology have been developed since the 1990’s. In this approach, the task that we want to solve, and the protocol that we use to solve it, are both modeled using chromatic simplicial complexes. By definition, a protocol solves a task when there exists a particular simplicial map between those complexes.In this thesis we study these geometric methods from the point of view of semantics. Our first goal is to ground this abstract definition of task solvability on a more concrete one, based on interleavings of execution traces. We investigate various notions of specification for concurrent objects, in order to define a general setting for solving concurrent tasks using shared objects. We then show how the topological definition of task solvability can be derived from it.In the second part of the thesis, we show that chromatic simplicial complexes can actually be used to interpret epistemic logic formulas. This allows us to understand the topological proofs of task unsolvability in terms of the amount of knowledge that the processes should acquire in order to solve a task.Finally, we present a few preliminary links with the directed space semantics for concurrent programs. We show how chromatic subdivisions of a simplex can be recovered by considering combinatorial notions of directed paths
Philippe, Eva. "Geometric realizations using regular subdivisions : construction of many polytopes, sweep polytopes, s-permutahedra." Electronic Thesis or Diss., Sorbonne université, 2024. http://www.theses.fr/2024SORUS079.
This thesis concerns three problems of geometric realizations of combinatorial structures via polytopes and polyhedral subdivisions. A polytope is the convex hull of a finite set of points in a Euclidean space R^d. It is endowed with a combinatorial structure coming from its faces. A subdivision is a collection of polytopes whose faces intersect properly and such that their union is convex. It is regular if it can be obtained by taking the lower faces of a lifting of its vertices in one dimension higher.We first present a new geometric construction of many combinatorially different polytopes of fixed dimension and number of vertices. This construction relies on showing that certain polytopes admit many regular triangulations. It allows us to improve the best known lower bound on the number of combinatorial types of polytopes.We then study the projections of permutahedra, that we call sweep polytopes because they model the possible orderings of a fixed point configuration by hyperplanes that sweep the space in a constant direction. We also introduce and study a combinatorial abstraction of these structures: the sweep oriented matroids, that generalize Goodman and Pollack's theory of allowable sequences to dimensions higher than 2.Finally, we provide geometric realizations of the s-weak order, a combinatorial structure that generalizes the weak order on permutations, parameterized by a vector s with positive integer coordinates. In particular, we answer Ceballos and Pons conjecture that the s-weak order can be realized as the edge-graph of a polytopal complex that is moreover a subdivision of a permutahedron
Diakité, Abdoulaye Abou. "Application des cartes combinatoires à la modélisation géométrique et sémantique des bâtiments." Thesis, Lyon 1, 2015. http://www.theses.fr/2015LYO10281/document.
3D building models are widely used in the civil engineering industry. While the models are needed by several applications, such as architectural representations and simulation processes, they often lack of information that are of major importance for the consistency of the calculations. The original models are then often rebuilt in the way that fits better to the intended applications. To overcome this drawback, we introduce a framework allowing to enrich a 3D model of a building presenting just a geometry, in a way more interoperable model, by adding to it topological and semantic information. A cellular subdivision of the building space is first performed relying on its geometry, then the topological relationships between the cells are explicitely defined. Semantic labels are then attributed to the identified components based on the topology and defined heuristic rules. A 3D combinatorial map data structure (3-map) is used to handle the reconstructed information. From the enriched model we show how to extract applications-driven information allowing to perform acoustic simulation and indoor ray tracing navigation. The approach stands as a bridge between the modeling approaches and the applications in building analysis using the model. It is fully automatic and present interesting results on several types of building models
Pacheco-Martínez, Ana María. "Extracting cell complexes from 4-dimensional digital images." Thesis, Poitiers, 2012. http://www.theses.fr/2012POIT2262/document.
A digital image can be defined as a set of n-xels on a grid made up by n-cubes. Segmentation consists in computing a partition of an image into regions. The n-xels having similar characteristics (color, intensity, etc.) are regrouped. Schematically, each n-xel is assigned a label, and each region of the image is made up by n-xels with the same label. The methods "type" Marching cubes and Kenmochi et al. construct complexes representing the topology of the region of interest of a 3-dimensional binary digital image. In the first method, the algorithm constructs a simplicial complex, whose 0-cells are points of the edges of the dual grid. Inthe second one, the authors construct a cell complex on a dual grid, i.e. the 0-cells of the complex are vertices of the dual grid. In order to construct the complex, Kenmochi et al. compute (up to rotations) the different configurations of white and black vertices of a cube, and then, they construct the convex hulls of the black points of these configurations. These convex hulls define the cells of the complex, up to rotations. The work developed in this thesis extends Kenmochi et al. method todimension 4. The goal is to construct a cell complex from a binary digital image defined on a dual grid. First, we compute the different configurations of white and black vertices of a 4-cube, up to isometries, and then, we construct the convex hulls defined by these configurations. These convex hulls are constructed by deforming the original 4-cube, and we distinguishseveral basic construction operations (deformation, degeneracy of cells, etc.). Finally, we construct the cell complex corresponding to the dual image by assembling the cells so o
Una imagen digital puede ser definida como un conjunto de n–xeles en un mallado constituido de n–cubos. Los n–xeles pueden ser identificados con: (1) los n–cubos del mallado, o con (2) los puntos centrales de estos n–cubos. En el primer caso, trabajamos con un mallado primal, mientras que en el segundo, trabajamos con un mallado dual construido a partir del mallado primal. La segmentación consiste en calcular una partición de una imagen en regiones. Los n–xeles que tienen características similares (color, intensidad, etc.) son reagrupados. Esquemáticamente, a cada n–xel se le asocia una etiqueta, y cada región de la imagen está constituida de n–xeles con la misma etiqueta. En particular, si las únicas etiquetas permitidas para los n–xeles son “blanca” y “negra”, la segmentación se dice binaria: los n–xeles negros forman el primer plano (foreground) o región de interés en cuestión de análisis de la imagen, y los n–xeles blancos forman el fondo (background). Ciertos modelos, como los Grafos de Adyacencia de Regiones (RAGs), los Grafos Duales (DGs) y la carta topológica, han sido propuestos para representar las particiones en regiones, y en particular para representar la topología de estas regiones, es decir las relaciones de incidencia y/o adyacencia entre las diferentes regiones. El RAG [27] es un precursor de este tipo de modelos, y ha sido una fuente de inspiración de los DGs [18] y de la carta topológica [9, 10]. Un RAG representa una imagen primal etiquetada por un grafo: los vértices del grafo corresponden a regiones de la imagen, y las aristas del grafo representan las relaciones de adyacencia entre la regiones. Los DGs son un modelo que permite resolver ciertos inconvenientes de los RAGs para representar imágenes de dimensión 2. La carta topológica es una extensión de los modelos anteriores definida para manipular imágenes primales de dimensión 2 y 3, representando no solamente las relaciones topológicas, sino también las relaciones geométricas
Dovgal, Sergey. "An interdisciplinary image of Analytic Combinatorics." Thesis, Paris 13, 2019. http://www.theses.fr/2019PA131065.
This thesis is devoted to the development of tools and the use of methods from Analytic Combinatorics, including exact and asymptotic enumeration, statistical properties of random objects, and random generation.The key ingredient is the multidisciplinarity of the domain, which is emphasised by using examples from computational logic, statistical mechanics, biology, mathematical statistics, networks and queueing theory
Janaqi, Stefan. "Quelques éléments de la géométrie des graphes : graphes médians, produits d'arbres, génération convexe des graphes de Polymino." Université Joseph Fourier (Grenoble), 1994. http://www.theses.fr/1995GRE10093.
Jacques, Isabelle. "Aspects combinatoires en modélisation 2D et 3D et application à l'énumération des cartes et des solides." Mulhouse, 1991. http://www.theses.fr/1991MULH0185.
Tallot, Didier. "Quelques propositions pour la mise en oeuvre d'algorithmes combinatoires." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 1985. http://tel.archives-ouvertes.fr/tel-00806984.
Ghazo, Hanna Zeina. "Cycles combinatoires et géométriques." Thesis, Brest, 2020. http://www.theses.fr/2020BRES0006.
The work in this thesis concerns the combinatorial theory of graphs, algebraic combinatorics and discrete geometry. On one side, it is about enumerating Hamiltonian paths and cycles of a given type in a tournament; On the other side, it studies numerical sequences verifying a quadratic difference equation.Concerning the results of the first part, we find: an equality between the number of Hamiltonians paths (resp. cycles) of a given type, in a tournament and its complement; an expression of the number of Hamiltonian oriented paths of a given type in a transitive tournament in terms of a recursive function F called the « path-function »; and the construction of an algorithm to compute F.In the second part of the work, we study cyclic graphs altogether with a solution to a quadratic difference equation.A parameter of this equation distinguishes real and complex sequences. A correspondence between real solutions and a class of polynomials with positive integer coefficients is established. To complete the correspondence, 1-step Eulerian digraphs interfere. A complex solution determines a closed planar walk in the plane, for which at each step we turn either left or right by a constant angle (the turning angle). This time, cyclotomic polynomials play a major role. Characterizing polynomials that determine such a solution is a problem that we study to the end of finding geometric properties of such polygonal cycles.When the walk exploits the sides of a regular polygon with exterior angle 2 π/n, we find unexpected phenomena when n≥ 12
Bienaise, Solène. "Tests combinatoires en analyse géométrique des données - Etude de l'absentéisme dans les industries électriques et gazières de 1995 à 2011 à travers des données de cohorte." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00941220.
Tomasini, Jérôme. "Géométrie combinatoire des fractions rationnelles." Thesis, Angers, 2014. http://www.theses.fr/2014ANGE0032/document.
The main topic of this thesis is to study, thanks to simple combinatorial tools, various geometric structures coming from the action of a complex polynomial or a rational function on the sphere. The first structure concerns separatrix solutions of polynomial or rational vector fields. We will establish several combinatorial models of these planar maps, as well as a closed formula enumerating the different topological structures that arise in the polynomial settings. Then, we will focus on branched coverings of the sphere. We establish a combinatorial coding of these mappings using the concept of balanced maps, following an original idea of W. Thurston. This combinatorics allows us to prove (geometrically) several properties about branched coverings, and gives us a new approach and perspective to address the still open Hurwitz problem. Finally, we discuss a dynamical problem represented by primitive majors. The utility of these objects is to allow us to parameterize dynamical systems generated by the iterations of polynomials. This approach will enable us to construct a bijection between parking functions and Cayley trees, and to establish a closed formula enumerating a certain type of trees related to both primitive majors and polynomial branched coverings
Gay, Joël. "Representation of Monoids and Lattice Structures in the Combinatorics of Weyl Groups." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS209/document.
Algebraic combinatorics is the research field that uses combinatorial methods and algorithms to study algebraic computation, and applies algebraic tools to combinatorial problems. One of the central topics of algebraic combinatorics is the study of permutations, interpreted in many different ways (as bijections, permutation matrices, words over integers, total orders on integers, vertices of the permutahedron…). This rich diversity of perspectives leads to the following generalizations of the symmetric group. On the geometric side, the symmetric group generated by simple transpositions is the canonical example of finite reflection groups, also called Coxeter groups. On the monoidal side, the simple transpositions become bubble sort operators that generate the 0-Hecke monoid, whose algebra is the specialization at q=0 of Iwahori’s q-deformation of the symmetric group. This thesis deals with two further generalizations of permutations. In the first part of this thesis, we first focus on partial permutations matrices, that is placements of pairwise non attacking rooks on a n by n chessboard, simply called rooks. Rooks generate the rook monoid, a generalization of the symmetric group. In this thesis we introduce and study the 0-Rook monoid, a generalization of the 0-Hecke monoid. Its algebra is a proper degeneracy at q = 0 of the q-deformed rook monoid of Solomon. We study fundamental monoidal properties of the 0-rook monoid (Green orders, lattice property of the R-order, J-triviality) which allow us to describe its representation theory (simple and projective modules, projectivity on the 0-Hecke monoid, restriction and induction along an inclusion map).Rook monoids are actually type A instances of the family of Renner monoids, which are completions of the Weyl groups (crystallographic Coxeter groups) for Zariski’s topology. In the second part of this thesis we extend our type A results to define and give a presentation of 0-Renner monoids in type B and D. This also leads to a presentation of the Renner monoids of type B and D, correcting a misleading presentation that appeared earlier in the litterature. As in type A we study the monoidal properties of the 0-Renner monoids of type B and D : they are still J-trivial but their R-order are not lattices anymore. We study nonetheless their representation theory and the restriction of projective modules over the corresponding 0-Hecke monoids. The third part of this thesis deals with different generalizations of permutations. In a recent series of papers, Châtel, Pilaud and Pons revisit the algebraic combinatorics of permutations (weak order, Malvenuto-Reutenauer Hopf algebra) in terms of the combinatorics of integer posets. This perspective encompasses as well the combinatorics of quotients of the weak order such as binary trees, binary sequences, and more generally the recent permutrees of Pilaud and Pons. We generalize the weak order on the elements of the Weyl groups. This enables us to describe the order on vertices of the permutahedra, generalized associahedra and cubes in the same unified context. These results are based on subtle properties of sums of roots in Weyl groups, and actually fail for non-crystallographic Coxeter groups
Khoshnoudirad, Daniel. "Aspects combinatoires des motifs linéaires en géométrie discrète." Thesis, Paris Est, 2016. http://www.theses.fr/2016PESC1046.
Discrete Geometry, as Theoretical Computer Science, studies in particular linear patterns such as discrete primitives in images: the discrete lines, discrete segments, the discrete planes, pieces of discrete planes, for example. In this work, I particularly focused on Farey diagrams that appear in the study of the $ (m, n) $ - cubes, ie the pieces of discrete planes. Among others, I study the Combinatorics of the Farey lines forming diagram Farey, establishing exact formulas. I also get an asymptotic estimate using Combinatorial Number Theory. Then, I get a lower bound for the cardinality of the Farey vertices. After that, we analyze the strategies used in the literature for the study of (m, n)- cubes only by Farey diagrams in two dimensions. In order to get new and more accurate bounds for (m, n)- cubes, one of the few available methods, is to propose a generalization for the concept of preimage of a discrete segment for (m, n) - cube, resulting in a new combinatorial inequality. Thus, we introduce the notion Farey diagram in three dimensions
Fossas, Ariadna. "Sur la géométrie et la combinatoire du groupe T de Thompson." Thesis, Grenoble, 2012. http://www.theses.fr/2012GRENM104/document.
This PhD thesis is concerned with Thompson's group T. This infinite, finitely presented, simple group is usually seen as a subgroup of the group of dyadic, piecewise linear, orientation-preserving homeomorphisms of the unit circle (piecewise linear T). However, T can also be identified to: 1.- a group of equivalence classes of balanced pairs of finite binary trees (combinatorial T), 2.- a subgroup of piecewise PSL(2,Z), orientation-preserving homeomorphisms of the projective real line (piecewise projective T), and 3.- the asymptotic mapping class group of a fattened complete trivalent tree in the hyperbolic plane (modular T). The first result shows that the canonical copy of PSL(2,Z) obtained from the piecewise projective T is a non-distorted subgroup of T. For this, one carries over this subgroup to obtain a characterization into combinatorial T, from which the word length of its elements can be estimated. Then, non-distortion follows from the metric properties of T established by Burillo-Cleary-Stein-Taback. As a corollary, T has non-distorted subgroups isomorphic to the free non-abelian group of rank 2. Furthermore, PSL(2,Z) is also explicitly given in the piecewise linear form.The second result uses modular T to state that there are exactly f(n) conjugacy classes of elements of order n, where f is the Euler function. Given a torsion element t of T of order n, a dyadic triangulation of the Poincaré disc which is invariant under the action of t modulo a convex polygon with n sides is found.The third result constructs a minimal simply-connected contractible cellular complex C on which the group T acts by automorphisms. The automorphism group of C is essentially T itself (strictly speaking it is an extension of T by the group of order 2). The cellular complex C can be seen as a generalization of Stasheff's associahedra for an infinitely sided convex polygon. The action of T on C is transitive on vertices and edges and, plus generally, on associahedral type cells in all dimensions.The final part deals with the first steps of a research project. One uses the geometric interpretation of the 1-skeleton of C in term of dyadic triangulations of the Poincaré disc to define a geometric boundary at infinity. Although the 1-skeleton of C is proved not to be hyperbolic, the construction imitates Gromov's construction of the boundary of hyperbolic spaces, and allows the description of the nature of some of the boundary points
Pharamond, Layla dit D'Costa. "Géométrie réelle des dessins d'enfant." Paris 6, 2002. http://www.theses.fr/2002PA066298.
Jeanne, Hadrien. "Langages géométriques et polycubes." Rouen, 2010. http://www.theses.fr/2010ROUES007.
This thesis falls into two parts. The first one is about the study of geometrical languages using formal languages and automata theory, as well as discrete geometry tools. A geometrical language is composed of words over an alphabet of size d, using the Parikh images of the set of prefixes of the words. Those images define a figure of dimension d. The second part refers to the study of 3-dimensional polycubes. We define 3-dimensional extensions of some properties of polyominoes. That allow us to define subclasses of polycubes : plateau polycubes, s-directed polycubes and vertically-convex s-directed polycubes. We define an enumeration method over directed polycubes, based on the strate decomposition of polyominoes defined by Temperley, and we use it in order to give the generating functions of the classes of polycubes defined above
Guilbot, Robin. "Quelques aspects combinatoires et arithmétiques des variétés toriques complètes." Phd thesis, Université Paul Sabatier - Toulouse III, 2012. http://tel.archives-ouvertes.fr/tel-00832228.
Martinez, Sandoval Leonardo Ignacio. "Contributions en géométrie combinatoire : rayons du cercle circonscrit différentes, théorèmes géométriques de type Hall, théorèmes fractionnaires de type Turán, matroïdes chemin du réseau et transversales de Kneser." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT277/document.
Combinatorial geometry is a broad and beautiful branch of mathematics. This PhD Thesis consists of the study of five different topics in this area. Even though the problems and the tools used to tackle them are diverse, they share a unifying goal: To explore the interaction between combinatorial and geometric structures.In Chapter 1 we study a problem by Paul Erdös: for a positive integer k, how many points in general position do we need in the plane so that we can always find a k-subset of them defining triangles with distinct circumradii? This question was posed in 1975 and Erdös himself proposed a solution in 1978. However, the proof inadvertently left out a non-trivial case. We deal with the case using basic tools from algebraic geometry and we provide a polynomial bound for the needed number of points.In Chapter 2 we are interested in providing geometric extensions of Hall's criterion for matchings in bipartite graphs (1935). We obtain geometric Hall-type theorems for pairwise disjoint convex sets and for points in general position in euclidean space. The tools of this chapter are topological, and are motivated by a remarkable method introduced by Aharoni and Haxell in 2000 and its generalizations.On the other hand, in Chapter 3 we begin with a fractional Helly theorem from 1979 by A. Liu and M. Katchalski to motivate a combinatorial result. We study combinatorial conditions on families of graphs that allow us to have sharpened variants of Turán's theorem. We find interesting relations between the Turán numbers, the chromatic numbers and the clique numbers of graphs in the family. The tools in this chapter are only combinatorial.In Chapter 4 we focus on obtaining some results for the well studied class of lattice path matroids introduced by Bonin, de Mier and Noy in 2003. The main contribution is proving for this class the validity of a 1999 conjecture of Merino and Welsh concerning an inequality involving certain values of the Tutte polynomial. In order to do this, we introduce and study snakes, a special class of ``thin'' lattice path matroids.Finally, in Chapter 5 we explore a variant of a transversal problem posed by J.L. Arocha, J. Bracho, L. Montejano and J.L. Ramírez-Alfonsín in 2010. In their original work, they realized that if we have few points in euclidean space then it is possible to find a transversal of a given dimension that goes through all the convex hulls of k-subsets of points. Similarly, they show that it is impossible to find such a transversal when we have many points. The authors give some specific bounds and they also leave some open problems. If the definition of transversal is slightly more restrictive, then the problem can be tackled using oriented matroid theory. We provide the details of the relation and we give bounds for the family of cyclic polytopes
Gross, Clauoe. "Opérations topologiques et géométriques sur les multicartes combinatoires : application à la cartographie thématique." Université Louis Pasteur (Strasbourg) (1971-2008), 1989. http://www.theses.fr/1989STR13032.
Labbé, Sébastien. "Structure des pavages, droites discrètes 3D et combinatoire des mots." Thèse, Paris 7, 2012. http://www.archipel.uqam.ca/4940/1/D2363.pdf.
Pouyanne, Nicolas. "Quelques contributions au carrefour de la géométrie, de la combinatoire et des probabilités." Habilitation à diriger des recherches, Université de Versailles-Saint Quentin en Yvelines, 2006. http://tel.archives-ouvertes.fr/tel-00403659.
Braun, David. "Approche combinatoire pour l'automatisation en Coq des preuves formelles en géométrie d'incidence projective." Thesis, Strasbourg, 2019. http://www.theses.fr/2019STRAD020.
This thesis work is part of the general field of computer-assisted proof and is methodologically based. The primary objective of proof assistants is to verify that handwritten demonstration is correct; the question here is how within such a system, it is possible to help a user to make a formal proof of the result in which he is interested. These questions around the verification of proofs, in particular in software certification, and beyond their traceability and readability have indeed become significant with the importance that algorithms have taken on in our society. Obviously, answering the question of proof assistance in all its generality goes far beyond the scope of this thesis. This is why we focus our work on proof in mathematics in a particular framework that is well known in our team: geometry and its formalization in the Coq system. In this field, we first highlight the levels at which we can work, namely the scientific context through the formalization methods but also the methodological and technical context within the Coq proof assistant. In a second step, we try to show how our methods and ideas can be generalized to other disciplines. In this way, we are putting in place the first steps towards effective proof assistance in a simple but omnipresent geometric context. Through a classical approach based on synthetic geometry and a complementary combinatorial approach using the concept of rank from matroid theory, we provide the user with general principles and tools to facilitate the development of formal proof. In this sense, we compare the automation capabilities of these two approaches in the specific context of finite geometries before finally constructing an automatic prover of geometric configurations of incidence
Fresse, Lucas. "Une étude combinatoire de la géométrie des fibres de Springer de type A." Lyon 1, 2007. http://www.theses.fr/2007LYO10322.
The variety of flags which are stable by a nilpotent endomorphism is called Springer fiber. We study this variety and its irreducible components. The fixed points of a torus on this variety are parameterized by a set of tableaux said row-standard. We construct a cell decomposition of the variety which is naturally parameterized by the row-standard tableaux, since each cell contains one fixed point, and such that the codimension of cells is analogous to a Bruhat length. This allows a handy calculation of the Betti numbers. When the nilpotent endomorphism is of hook, two-rows or two-columns type, we define a notion of constructibility for the row-standard tableaux which allows to describe the fixed points of the components. We deduce a calculation of the dimension of a finite intersection of components and, in the two-columns case, a criterion of singularity
Guilbot, Robin. "Quelques aspects combinatoires et arithmétiques des variétés toriques complètes." Phd thesis, Toulouse 3, 2012. http://thesesups.ups-tlse.fr/1905/.
In this thesis we study two distinct aspects of toric varieties, one purely geometric, over C, and the other of arithmetic nature, over quasi algebraically closed fields (C1 fields). Extremal curves, which generate the Mori cone of a projective toric variety, are primitive curves (V. Batyrev). In 2009, D. Cox and C. Von Renesse conjectured that the classes of primitive curves generate the Mori cone of any toric variety whose fan has full dimensional convex support. We present a family of counterexamples to this conjecture and propose a new formulation based on the notion of local contractibility, generalizing the contractibility defined by C. Casagrande. Using the corridors, a combinatorial tool that we introduce, we show how to write any given 1-cycle class as a linear combination with integer coefficients of toric curve classes. Corridors enable us to give an explicit decomposition of any class that is not contractible (straights corridors) as well as contractible classes in some particular cases (circular corridors). C1 fields are those over which the existence of rational points on a variety Y is ensured by any small degree embedding of Y in a projective space (by definition) or in a weighted projective space (according to an easy theorem of Kollar). For an ample divisor in a toric variety whose fan is simplicial and complete, we show that there is also a notion of small degree which ensures the existence of rational points. This way, we show the existence of rational points on a large class of rationally connected varieties
LIRA, DE LIMA ARILEIDE. "Groupes speciaux : aspects algebriques et combinatoires de la theorie des espaces d'ordres abstraits." Paris 7, 1996. http://www.theses.fr/1996PA077090.
Glisse, Marc. "Combinatoire des droites et segments pour la visibilité 3D." Phd thesis, Université Nancy II, 2007. http://tel.archives-ouvertes.fr/tel-00192337.
Hils, Martin. "Fusion libre et autres constructions génériques." Phd thesis, Université Paris-Diderot - Paris VII, 2006. http://tel.archives-ouvertes.fr/tel-00274128.
la fusion libre sur une fusion fortement minimale est effectuée. Puis, des variations sur le thème de la fusion sont étudiées (courbe générique et structures bicolores). À titre d'exemple, il suit des résultats que l'on peut donner un sens à la notion d'une courbe générique dans un corps pseudofini. Enfin, l'axiomatisabilité de l'automorphisme générique est démontrée dans certains contextes issus d'une amalgamation à la Hrushovski dont la fusion libre et les théories des différents corps bicolores de Poizat (noir, rouge et vert).
Modolo, Marie-Eve. "Histoire de la normalisation canonique d'une famille de courbes algébriques : aspects algorithmiques, combinatoires et géométriques." Poitiers, 2007. http://www.theses.fr/2007POIT2277.
Chaboud, Thomas. "Pavages et graphes de Cayley planaires." Lyon, École normale supérieure (sciences), 1995. http://www.theses.fr/1995ENSL0004.
De, Joannis de Verclos Rémi. "Applications des limites de structures combinatoires en géométrie et en théorie des graphes." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAM037/document.
This thesis is focused on problems related to the theory of combinatorial limits.This theory opened links between different fields such asanalysis, combinatorics, geometry and probability theory.In this thesis, we apply ideas coming from this framework toproblems in extremal combinatorics.In a first chapter we develop a theory of limits for emph{order types},a geometrical object that encodes configuration of a set of points in theplane by the mean of the orientations of their triangles.The order type of a point set suffices to determine many of its properties,such as for instance the boundary of its convex hull.We show that the limit of a converging sequence of order typescan be represented by random-free object analogous to a graphon.Further, we link this notion to the natural distributions of order typesarising from the sampling of random points from some probability measureof the plane.We observe that in this mean, every probability measure gives rise to a limitof order types.We show that this map from probability measure on the plane to limit oforder type is not surjective.Concerning its injectivity,we prove that if a measure has large enough support, for instance if its supportcontains an open ball, the limit of order types the measure generatessuffices to essentially determine this measure.A second chapter is focused on property testing.A tester is a randomized algorithm for distinguishing between objects satisfyinga property from those that are at some distance at least εfrom having itby means of the edition distance.This gives very efficient algorithms, and in particular algorithms whosecomplexity does not depend on the size of the input but only on the parameter ε.For graphs, it has been shown by Alon and Shapira that every hereditary propertyhas such a tester.We contribute to the following question :which classes of graphs have a one-sided property tester with a number of queries that is a polynomial in 1/ε ?We give a proof that the class of interval graphs has such a tester.The theory of flag algebras is a framework introduced by Razborovclosely related to dense limit of graphs, that gives a way to systematicallyderive bounds for parameters in extremal combinatorics.In a third chapter we present a program developed during my Phd.that implements this method.This program works as a library that can compute flag algebras,manipulate inequalities on densities and encode the optimization of some parameterin a semi-definite positive instance that can be given to a dedicated solverto obtain a bound on this parameter.This program is in particular used to obtain a new bound forthe triangle case of the Caccetta-Häggkvist conjecture
Vo, Phi Khanh. "Contributions à l'étude des arrangements : équivalences combinatoires et perturbations." Université Joseph Fourier (Grenoble), 1994. http://tel.archives-ouvertes.fr/tel-00344973.
Dehlinger, Christophe. "Spécifications et preuves en Coq pour les surfaces combinatoires et leur classification." Université Louis Pasteur (Strasbourg) (1971-2008), 2003. http://www.theses.fr/2003STR13236.
Delalleau, Guillaume. "Substitutions sur la droite et dans le plan." Paris 7, 2011. http://www.theses.fr/2011PA077218.
This memoir is split in two parts of three chapters each. The theme of the first part is S-adic words. The first chapter is concerned with the convergence of S-adic sequences; we propose a general form for the accumulation points of S-adic sequences, and infer from it general sufficient conditions for the convergence. In the second chapter, conditions on the alphabet of substitutions for the S-adic words to form an attractor in the set of infinite words. When these conditions are met, we adumbrate a way to a solution of the S-adic conjecture. The first step, a more systematic study of the factorial complexity of fixed points of substitutions, is taken and partial results are obtained. In the third chapter, we touch upon the question of the existence of frequencies for letters in S-adic words through the action of substitutions on the frequency simplex. The second part is concerned with tilings of the plane with square and colored tiles. In the fifth chapter, we propose a representation of patches by graphs and give necessary and sufficient conditions for a graph to represent a patch. In the sixth chapter we define bidimensional substitutions as transformations of the vertices ans edges of the graph representing patches; necessary and sufficient conditions for a graph thus built to represent a patch are given. In the seventh chapter we propose a construction of S-adic tilings of the plane by square and colored tiles
Kyriakoglou, Revekka. "Morphismes itérés, combinatoire des mots et systèmes dynamiques symboliques." Thesis, Paris Est, 2019. http://www.theses.fr/2019PESC2050.
The current thesis focuses on the topic of combinatorics on words and symbolic dynamical systems. The symbolic dynamical systems are objects for encoding word trajectories in dynamic systems of transformations in topological spaces. Among these dynamical systems, well-known examples are given by Sturmial words and by exchange of intervals. The Sturmian words are related to discrete geometry algorithms and the exchange of intervals form an interesting class of dynamical systems. Furthermore, it should be mentioned that some exchange families provide promising generalizations of Sturmian words.The main subject of the thesis is the recognizability of words generated by primitive morphisms. The concept of recognizability of morphisms originates in the paper of Martin [1] under the term of determinization. The term was first used by Host in his paper on the Ergodic theory of Dynamical Systems[2]. The notion of recognizability came in full bloom after the interest shown by many scientists due to its various theoretical applications in various topics, from combinatorics on words to symbolic dynamics. A similar notion is that of circularity. The two terms are often, but not always used as synonymous. This lack of consistency along the literature could result in confusion. To the best of the author’s knowledge, there is not, as of yet, any study that collects those definitions and proves their equivalence or indicates the differences among them. This thesis provides a solid approach to this subject, using a coherent definition of recognizability and circularity.The notion of recognizability alongside a technique used in [3] were used in order to prove the decidability of different properties of extension graphs (defined in [4]) of elements of a language. Families of sets can be defined from properties of the extension graph of their elements, such as acyclic sets, tree sets, neutral sets, etc. More precisely, given a set of words S, one can associate with every word w ∈ S it's extension graph which describes the possible left and right extensions of w in S. We show how to use the recognizability to provide decidability of extension graphs. Furthermore, recognizability is used in is the subject of Profinite Semigroups. We describe the relationship between the recognizability of morphisms and properties of the free profinite semigroups [5].Bibliography[1] John C. Martin. Minimal flows arising from substitutions of non-constant length. Math. Systems Theory, 7:72–82, 1973.[2] B. Host. Valeurs propres des systèmes dynamiques définis par des substitu-tions de longueur variable. Ergodic Theory Dynam. Systems, 6(4):529–540,1986.[3] Klouda, K. and Starosta, Š. "Characterization of circular D0L systems.", arXiv preprint arXiv:1401.0038 (2013).[4] Berthé, V., De Felice, C., Dolce, F. et al. Monatsh Math (2015) 176: 521. https://doi.org/10.1007/s00605-014-0721-4[5]Kyriakoglou ,R., Perrin ,D. "Profinite semigroups", arXiv:1703.10088 (2017)[6]Almeida, J., "Profinite semigroups and applications" In Structural theory of automata, semigroups, and universal algebra, volume 207 of NATO Sci.43 Ser. II Math. Phys. Chem., pages 1–45. Springer, Dordrecht, 2005. Notes taken by Alfredo Costa
Blondin, masse Alexandre. "A l'intersection de la combinatoire des mots et de la géométrie discrète : palindromes, symétries et pavages." Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00697886.
Blondin, Massé Alexandre. "A l'intersection de la combinatoire des mots et de la géométrie discrète : palindromes, symétries et pavages." Thesis, Grenoble, 2011. http://www.theses.fr/2011GRENM072/document.
In this thesis, we explore different problems at the intersection of combinatorics on words and discrete geometry. First, we study the occurrences of palindromes in codings of rotations, a family of words including the famous Sturmian words and Rote sequences. In particular, we show that these words are full, i.e. they realize the maximal palindromic complexity. Next, we consider a new family of words called generalized pseudostandard words, which are generated by an operator called iterated pseudopalindromic closure. We present a generalization of a formula described by Justin which allows one to generate in linear (thus optimal) time a generalized pseudostandard word. The central object, the f-palindrome or pseudopalindrome, is an indicator of the symmetries in geometric objects. In the last chapters, we focus on geometric problems. More precisely, we solve two conjectures of Provençal about tilings by translation, by exploiting the presence of palindromes and local periodicity in boundary words. At the end of many chapters, different open problems and conjectures are briefly presented
Bouttier, Jérémie. "Physique statistique des surfaces aléatoires et combinatoire bijective des cartes planaires." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2005. http://tel.archives-ouvertes.fr/tel-00010651.
Mora, Thierry. "Géométrie et inférence dans l'optimisation et en théorie de l'information." Paris 11, 2007. http://www.theses.fr/2007PA112162.
Salaün, Isabelle. "Deux problèmes de géométrie combinatoire : unimodalité de deux suites en théorie des matroïdes ; polyèdres : polyèdre régulier à vingt-quatre sommets de l'espace euclidien à quatre dimensions." Paris 6, 1988. http://www.theses.fr/1988PA066524.
Bertault, François. "Génération et tracé de structures décomposables." Nancy 1, 1997. http://www.theses.fr/1997NAN10297.
The main goal of the thesis is to conceive algorithms and tools to assist people who study a special kind of combinatorial structures, namely decomposable structures. The two major questions we try to solve are: How to generate, randomly or by some systematic procedure, a decomposable structure; How to draw decomposable structures. Decornposable structures are combinatorial structures that are recursively described using a small set of constructors. The idea consists in considering a structure as a process of construction from simpler structures. The main interest of the decomposable structure theory is that we can describe an infinite number of different sets of structures, including permutations, varions kind of trees or functional graphs, for which we can solve counting and random generation problems. Possible applications are the average case analysis of algorithms and the production of test inputs for the experimental validation of programs. We propose an algorithm for drawing decomposable structures based on the translation into special graphs, that we call composed graphs, in which bath inclusion and adjacency relationships can exist. The principle is based on the translation of decomposable structures into composed graphs, i. E. Graphs with both inclusion and adjacency relationships. The drawing of composed graph is achieved by using different classical graph drawing algorithm together. The number of algorithms that can be used on a sarne drawing is infinite. The only restriction is that the algorithms must be able to draw graphs with arbitrary node sizes. We present two graph drawing software realisations that we wrote in order to validate the algorithms presented in the thesis. They can be linked to combinatorial structure generation programs in order to form integrated systems. We also investigate their use for the visualisation of large data structures
Orantin, Nicolas. "Du développement topologique des modèles de matrices à la théorie des cordes topologiques : combinatoire de surfaces par la géométrie algébrique." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2007. http://tel.archives-ouvertes.fr/tel-00173162.
je montre que pour un choix particulier des paramètres, ces objets peuvent être rendus invariants modulaires et sont solutions des équations d'anomalie holomorphe de la théorie de Kodaira-Spencer donnant un nouvel élément vers la preuve de la conjecture de Dijkgraaf-Vafa.
Jartoux, Bruno. "On combinatorial approximation algorithms in geometry." Thesis, Paris Est, 2018. http://www.theses.fr/2018PESC1078/document.
The analysis of approximation techniques is a key topic in computational geometry, both for practical and theoretical reasons. In this thesis we discuss sampling tools for geometric structures and geometric approximation algorithms in combinatorial optimization. Part I focuses on the combinatorics of geometric set systems. We start by discussing packing problems in set systems, including extensions of a lemma of Haussler, mainly the so-called shallow packing lemma. For said lemma we also give an optimal lower bound that had been conjectured but not established in previous work on the topic. Then we use this lemma, together with the recently introduced polynomial partitioning technique, to study a combinatorial analogue of the Macbeath regions from convex geometry: Mnets, for which we unify previous existence results and upper bounds, and also give some lower bounds. We highlight their connection with epsilon-nets, staples of computational and combinatorial geometry, for example by observing that the unweighted epsilon-net bound of Chan et al. (SODA 2012) or Varadarajan (STOC 2010) follows directly from our results on Mnets. Part II deals with local-search techniques applied to geometric restrictions of classical combinatorial optimization problems. Over the last ten years such techniques have produced the first polynomial-time approximation schemes for various problems, such as that of computing a minimum-sized hitting set for a collection of input disks from a set of input points. In fact, it was shown that for many of these problems, local search with radius Θ(1/epsilon²) gives a (1 + epsilon)-approximation with running time n^{O(1/epsilon²)}. However the question of whether the exponent of n could be decreased to o(1/epsilon²) was left open. We answer it in the negative: the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results
Bus, Norbert. "The use of geometric structures in graphics and optimization." Thesis, Paris Est, 2015. http://www.theses.fr/2015PESC1117/document.
Real-world data has a large geometric component, showing significant geometric patterns. How to use the geometric nature of data to design efficient methods has became a very important topic in several scientific fields, e.g., computational geometry, discrete geometry, computer graphics, computer vision. In this thesis we use geometric structures to design efficient algorithms for problems in two domains, computer graphics and combinatorial optimization. Part I focuses on a geometric data structure called well-separated pair decomposition and its usage for one of the most challenging problems in computer graphics, namely efficient photo-realistic rendering. One solution is the family of many-lights methods that approximate global illumination by individually computing illumination from a large number of virtual point lights (VPLs) placed on surfaces. Considering each VPL individually results in a vast number of calculations. One successful strategy the reduce computations is to group the VPLs into a small number of clusters that are treated as individual lights with respect to each point to be shaded. We use the well-separated pair decomposition of points as a basis for a data structure for pre-computing and compactly storing a set of view independent candidate VPL clusterings showing that a suitable clustering of the VPLs can be efficiently extracted from this data structure. We show that instead of clustering points and/or VPLs independently what is required is to cluster the product-space of the set of points to be shaded and the set of VPLs based on the induced pairwise illumination. Additionally we propose an adaptive sampling technique to reduce the number of visibility queries for each product-space cluster. Our method handles any light source that can be approximated with virtual point lights (VPLs), highly glossy materials and outperforms previous state-of-the-art methods. Part II focuses on developing new approximation algorithms for a fundamental NP-complete problem in computational geometry, namely the minimum hitting set problem with particular focus on the case where given a set of points and a set of disks, we wish to compute the minimum-sized subset of the points that hits all disks. It turns out that efficient algorithms for geometric hitting set rely on a key geometric structure, called epsilon-net. We give an algorithm that uses only Delaunay triangulations to construct epsilon-nets of size 13.4/epsilon and we provide a practical implementation of a technique to calculate hitting sets in near-linear time using small sized epsilon-nets. Our results yield a 13.4 approximation for the hitting set problem with an algorithm that runs efficiently even on large data sets. For smaller datasets, we present an implementation of the local search technique along with tight approximation bounds for its approximation factor, yielding an (8 + epsilon)-approximation algorithm with running time O(n^{2.34})
Bellet, Thomas. "Transformations de graphes pour la modélisation géométrique à base topologique." Thesis, Poitiers, 2012. http://www.theses.fr/2012POIT2261/document.
Geometric modeling is now involved in many fields such as: video games, architecture, engineering and archaeology. The represented objects are very different from one field to another, and so are their modeling operations. Furthermore, many specific types of modeling software are designed for high programing costs, but with a relatively low rate of effectiveness.The following is an alternative approach:– we have conceived a dedicated language for geometric modeling that will allow us to define any operation of any field; objects in this language are defined with the topological model of generalized maps, this definition has been extended to the embedding informations; here the operations are defined as graph transformation rules which originate from the category theory;– we have ensured operation definitions with consistency conditions; these operations that satisfy those conditions do not generate anomalies; – we have designed generic modeling software to serve as an interpreter of this language; the operation definitions are directly applied without the need for more programing; the software also automatically checks the language conditions and warns the user if he designs a non-consistent operation.The provided language and software prove to be efficient, and all for a low programing cost. Designing a new operation takes only minutes thanks to the language conditions, as opposed to hours of programming and debugging with the past approach
Damiand, Guillaume. "Contributions aux Cartes Combinatoires et Cartes Généralisées : Simplification, Modèles, Invariants Topologiques et Applications." Habilitation à diriger des recherches, INSA de Lyon, 2010. http://tel.archives-ouvertes.fr/tel-00538456.
Cuneo, Rémi. "Généralisation d'une méthode de petites simplifications due à Mikhaïl Gromov et Yann Ollivier en géométrie des groupes." Thesis, Aix-Marseille 1, 2011. http://www.theses.fr/2011AIX10026/document.
In a paper published in 2003, M.Gromov proposes a rewording of the small cancellation theory in geometric group theory. In this version, a finite graph defines a finitely presented group; generators of the group are the labels of the graph; relators are the words associated with cycles; pieces, "short" words which allow small cancellations in a group, are words which label two distinct paths in the graph.Our thesis relies on a brief description of this theory published in2006 by Y.Ollivier. The concept of finitely presented "small cancellation" group, developed by R.Lyndon, M.Greendlinger and others in the 60's and 70's, is a precursor of Gromovword-hyperbolic groups in the late of the 80's, for which combinatorial properties of the presentation imply algebraic properties of the group. In our work, we build a rigorous small cancellation theory in terms of graphs, and develop the basic concept of "megatiles", implicitly used by Y. Ollivier in his article. We extend his results to non-hyperbolic and non-metric cases (eg. $C(4)-T(4)$). This point of view allows a new proof, more natural, of thesolvability of word and conjugacy problems for presentations of prime alternating link groups. We also extend the results of a M.Greendlinger theorem to thenon-metric case, in response to a question of I. Kapovich
Gagneur, Julien. "Algorithms for decomposition of bio-molecular networks." Châtenay-Malabry, Ecole centrale de Paris, 2004. http://www.theses.fr/2004ECAP0943.