Academic literature on the topic 'Quotients de treillis'

Une conséquence de la classification des théories complètes d'algèbres de Boole par Tarski [5] est que la théorie élémentaire d'une algèbre de Boole A est déterminée par le type d'isomorphisme du treillis de ses idéaux définissables et, pour chacun de ces idéaux, par le nombre d'atomes du quotient de A par cet idéal lorsque ce nombre est fini. Une remarque analogue peut être faite à propos des cas particuliers d'algèbres de Boole munies d'un idéal distingué étudiés par Ershov [1] et par Jurie et Touraille [3]; dans to us ces cas, c'est la simplicité des treillis possibles qui permet la classification des théories complètes. Le résultat principal de cet article est que, dans le cas général d'une algèbre de Boole munie d'une famille quelconque d'idéaux distingués, la théorie d'un modèle peut encore être caractérisée grâce à une structure algébrique sur l'ensemble de ses idéaux définissables. Il s'agit d'une structure d'algèbre de Heyting munie d'une opération unaire sa définie par sa(K) = {a: a/K est sans atome}, et cette structure s'avère être engendrée par les idéaux distingués du modèle. La méthode utilisée est l'élimination directe des quantificateurs, par réductions successives des formules. Elle nécessite des propriétés algébriques et topologiques qui sont données aux §§1 et 2: on introduit au §1 la notion d'algèbre de Heyting étoilée, c'est-à-dire d'algèbre de Heyting munie d'une opération unaire * vérifiant des égalités qui permettent de rendre compte, d'une certaine façon, de la dérivation de Cantor-Bendixon; le §2 est consacré à des propriétés topologiques qui, dans le cas de l'espace de Stone d'une algèbre de Boole A, permettent d'éclaircir les relations possibles entre les atomes des quotients de A par des idéaux différents.

International audience We present a generalization of the Tamari lattice to parabolic quotients of the symmetric group. More precisely, we generalize the notions of 231-avoiding permutations, noncrossing set partitions, and nonnesting set partitions to parabolic quotients, and show bijectively that these sets are equinumerous. Furthermore, the restriction of weak order on the parabolic quotient to the parabolic 231-avoiding permutations is a lattice quotient. Lastly, we suggest how to extend these constructions to all Coxeter groups. Nous présentons une généralisation du treillis de Tamari aux quotients paraboliques du groupe symétrique. Plus précisément, nous généralisons les notions de permutations qui évitent le motif 231, les partitions non-croisées, et les partitions non-emboîtées aux quotients paraboliques, et nous montrons de façon bijective que ces ensembles sont équipotents. En restreignant l’ordre faible du quotient parabolique aux permutations paraboliques qui évitent le motif 231, on obtient un quotient de treillis d’ordre faible. Enfin, nous suggérons comment étendre ces constructions à tous les groupes de Coxeter.

International audience The Tamari order is a central object in algebraic combinatorics and many other areas. Defined as the transitive closure of an associativity law, the Tamari order possesses a surprisingly rich structure: it is a congruence-uniform lattice. In this work, we consider a larger class of posets, the Grassmann-Tamari orders, which arise as an ordering on the facets of the non-crossing complex introduced by Pylyavskyy, Petersen, and Speyer. We prove that the Grassmann-Tamari orders are congruence-uniform lattices, which resolves a conjecture of Santos, Stump, and Welker. Towards this goal, we define a closure operator on sets of paths inside a rectangle, and prove that the biclosed sets of paths, ordered by inclusion, form a congruence-uniform lattice. We then prove that the Grassmann-Tamari order is a quotient lattice of the corresponding lattice of biclosed sets. L’ordre Tamari est un objet central dans la combinatoire algébrique et de nombreux autres domaines. Définie comme la fermeture transitive d’une loi d’associativité, l’ordre Tamari possède une structure étonnamment riche: il est un treillis congruence uniforme. Dans ce travail, nous considérons une classe plus large de posets, les ordres Grassmann-Tamari, qui découlent comme un ordre sur les facettes du complexe non-croisement introduit par Pylyavskyy, Petersen, et Speyer. Nous démontrons que les ordres Grassmann-Tamari sont treillis congruence uniformes, ce qui résout une conjecture de Santos, Stump, et Welker. Pour atteindre cet objectif, nous définissons un opérateur de fermeture sur des ensembles de chemins à l’intérieur d’un rectangle, et prouver que les ensembles bifermé de chemins, ordonné par inclusion, forment un réseau de congruence uniforme. Nous démontrons ensuite que l’ordre Grassmann-Tamari est un treillis quotient du treillis correspondant d’ensembles bifermés.

En combinatoire algébrique, les treillis sont des ensembles partiellement ordonnés qui possèdent à la fois des opérations inf et sup. L'ordre faible sur les permutations est un exemple classique de treillis qui possède une riche structure combinatoire. Cela en a fait un point de départ à partir duquel d'autres objets combinatoires ont été définis. Pour cette thèse, nous nous concentrons sur l'étude de deux familles différentes de treillis en relation avec l'ordre faible: les treillis des permusylvestres et le s-ordre faible. La première partie de la thèse concerne la théorie des quotients de treillis de l'ordre faible en s'appuyant sur le travail de N. Reading. On se concentre spécifiquement sur la famille des quotients des permusylvestres de l'ordre faible. En les considérant comme des permusylvestres, comme dans le travail de V. Pilaud et V. Pons, nous étendons la technologie des vecteurs de crochet des arbres binaires en définissant les vecteurs d'inversion et les vecteurs cubiques. Le vecteur d'inversion capture l'opération de meet de ces treillis tandis que le vecteur cubique permet de les réaliser géométriquement via une configuration cubique. En changeant de point de vue et en étudiant ces quotients à travers les éléments minimaux de leurs classes de congruence, nous utilisons la description de Coxeter de type A des permutations pour caractériser les permusylvestres avec l'aide d'automates. Ces automates capturent l'évitement de motifs ijk et/ou kij impliqués par ces quotients et nous permettent de définir des algorithmes qui généralisent le tri par pile. Dans le cas où le quotient correspond à un treillis cambrien, nous relions nos automates au tri de Coxeter. Nous donnons quelques indications sur le même phénomène pour les groupes de Coxeter de types B et D. La deuxième partie de cette thèse découle du travail de V. Pons et C. Ceballos qui ont défini le s-ordre faible sur les arbres s-décroissants où s est une séquence d'entiers positifs. Dans le cas de s=(1,ldots,1), cette définition récupère l'ordre faible. Dans leur premier article, les auteurs ont conjecturé que le s-permutaèdre pouvait être réalisé dans l'espace comme une subdivision polyédrique d'un zonotope. Nous donnons une réponse positive à leur conjecture lorsque s est une séquence d'entiers positifs en définissant un graphe dont les polytopes de flot nous permettent de récupérer le s-ordre faible. Nous utilisons des techniques de flots sur les graphes, de géométrie discrète et de géométrie tropicale pour obtenir des réalisations du s-permutaèdre avec différentes propriétés. Avec l'idée de décrire les quotients de treillis de le s-ordre faible, nous étudions leurs éléments sup-irréductibles. Nous introduisons également une opération sur les graphes pour définir un analogue des quotients de treillis des permusylvestres sur ces treillis
In algebraic combinatorics, lattices are partially ordered sets which possess both meet and join operations. The weak order on permutations is a classical example of a lattice that has a rich combinatorial structure. This has made it a starting point from which other combinatorial objects have been defined. For this thesis, we focus on studying two different families of lattices in relation to the weak order: the permutree lattices and the s-weak order. The first part of the thesis involves the theory of lattice quotients of the weak order building upon the work of N. Reading, specifically focusing on the family of permutree quotients of the weak order. Considering them as permutrees, as done by V. Pilaud and V. Pons, we extend the technology of bracket vectors from binary trees by defining inversion and cubic vectors. The inversion vector captures the meet operation of these lattices while the cubic vector helps realizes them geometrically via a cubical configuration. Changing our point of view and studying these quotients through the minimal elements of their congruence classes, we use the Coxeter Type A description of permutations to characterize permutrees using automata. These automata capture the pattern avoidance of ijk and/or kij implied by these quotients and allow us to define algorithms which generalize stack sorting. In the case where the quotient corresponds to a Cambrian lattice we relate our automata with Coxeter sorting. We give some insight about the same phenomenon for Coxeter groups of types B and D. The second part of this thesis stems from the work of V. Pons and C. Ceballos who defined the s-weak order on s-decreasing trees where s is a sequence of non-negative integers. In the case of s=(1,ldots,1) this definition recovers the weak order. In their first article, the authors conjectured that the s-permutahedron could be realized in space as a polyhedral subdivision of a zonotope. We give a positive answer to their conjecture when s is a sequence of positive integers by defining a graph whose flow polytopes allows us to recover the s-weak order. We use techniques from flows on graphs, discrete geometry, and tropical geometry to obtain realizations of the s-permutahedron with different properties. With the idea of describing the lattice quotients of the s-weak order, we study their join-irreducibles. We introduce as well a graph operation to define an analog of permutree quotients on these lattices

Découvrir des renversements de tendances entre deux cubes de données offre aux utilisateurs une connaissance nouvelle et intéressante lors des fluctuations de l’univers réel modélisé : quelles sont les nouveautés ? Quelle tendance apparaît ou disparaît ? Nous introduisons le nouveau concept de Cube Emergent. Il capture les renversements de tendances en mettant en oeuvre une contrainte d’émergence (conjonction de contrainte monotones et antimonotones). Les bordures, classiques en fouille de données, sont reprises pour le Cube Emergent. Dans un second temps, nous proposons un nouveau couple de bordures pour optimiser à la fois l'espace de stockage et le temps de calcul. Cette nouvelle représentation fournit une caractérisation simple de la taille du Cube Emergent aussi bien que des outils de classification et de navigation dans les cubes. La connexion entre les bordures classiques et celles proposées est formellement établie en utilisant le concept de cube transversal. Connaître la taille du Cube Emergent est d’un grand intérêt, en particulier pour ajuster au mieux la contrainte d’émergence sous-jacente. Cette problématique est traitée en étudiant une borne supérieure et en caractérisant la taille exacte du Cube Emergent. Deux stratégies sont proposées pour estimer rapidement cette taille : la première est basée sur une estimation analytique, sans acc`es à la base de données, la seconde s’appuie sur un comptage probabiliste utilisant les bordures proposées comme entrée de l’algorithme proche de l’optimal HYPERLOGLOG. Grâce à la particuli`ere efficacité de cet algorithme, plusieurs itérations peuvent être réalisées pour calibrer au mieux la contrainte d’émergence. De plus, des nouvelles représentations réduites et sans perte d’information du Cube Emergent sont proposées en utilisant le concept de fermeture cubique
Discovering trend reversals between two data cubes provides users with a novel and interesting knowledge when the real world context fluctuates : what is new? Which trends appear or emerge? Which tendencies are immersing or disappear? With the concept of Emerging Cube, we capture such trend reversals by enforcing an emergence constraint. We resume the classical borders fot eh Emerging Cube and introduce a new one which optimiszes both storage space and computation time, provides a simple characterization of the size Emerging Cubes, as well as classification and cube navigation tools. We soundly state the connection between the classical and proposed borders by using cube transversals. Knowing the size of Emerging Cubes without computing them is of great interest in particular for adjusting at best the underlying emergence constraint. We address the issue by studying an upper bound and characterization the exact size of Ermerging Cubes. We propose two strategies for quickly estimate their size : one based on analytical estimation, without database access, and one based on probabilistic counting using the proposed borders as the input of the near-optimal algorithm HyperLogLog. Due to the efficiency of the estimation algorithm various iterations can be performed to calibrate at the best the emergence constraint. Moreover, we propose reduced and lossless representations of the Emerging Cube by using the concept of cube closure. Finally we perform experiments for different data distributions in order to measure on one hand the size on the introduced condensed and concise representations and on the other hand the performance (accuracy and computation time) of the proposed estimation method

Découvrir des renversements de tendances entre deux cubes de données offre aux utilisateurs une connaissance nouvelle et intéressante lors des fluctuations de l'univers réel modélisé : quelles sont les nouveautés ? Quelle tendance apparaît ou disparaît ? Nous introduisons le nouveau concept de Cube Émergent. Il capture les renversements de tendances en mettant en œuvre une contrainte d'émergence (conjonction de contrainte monotones et antimonotones). Les bordures, classiques en fouille de données, sont reprises pour le Cube Émergent. Dans un second temps, nous proposons un nouveau couple de bordures pour optimiser à la fois l'espace de stockage et le temps de calcul. Cette nouvelle représentation fournit une caractérisation simple de la taille du Cube Émergent aussi bien que des outils de classification et de navigation dans les cubes. La connexion entre les bordures classiques et celles proposées est formellement établie en utilisant le concept de cube transversal. Connaître la taille du Cube Émergent est d'un grand intérêt, en particulier pour ajuster au mieux la contrainte d'émergence sous-jacente. Cette problématique est traitée en étudiant une borne supérieure et en caractérisant la taille exacte du Cube Émergent. Deux stratégies sont proposées pour estimer rapidement cette taille : la première est basée sur une estimation analytique, sans accès à la base de données, la seconde s'appuie sur un comptage probabiliste utilisant les bordures proposées comme entrée de l'algorithme proche de l'optimal HYPERLOGLOG. Grâce à la particulière efficacité de cet algorithme, plusieurs itérations peuvent être réalisées pour calibrer au mieux la contrainte d'émergence. De plus, des nouvelles représentations réduites et sans perte d'information du Cube Émergent sont proposées en utilisant le concept de fermeture cubique.