Antichaîne | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

En mathématiques, plus précisément en théorie des ordres, une antichaîne est une partie d'un ensemble partiellement ordonné dont les éléments sont deux à deux incomparables. (Par opposition aux chaînes qui forment parties d'un ensemble dont les éléments sont toujours deux à deux comparables.) Dit autrement, soit E un ensemble muni d'une relation d'ordre ≤, un sous-ensemble A est une antichaîne de E si pour tout x,y de A, Une antichaîne est dite maximale si elle n'est incluse (strictement) dans aucune autre antichaîne. La famille de toutes les antichaînes d'un ensemble fini partiellement ordonné peut être muni des opérations d'union et d'intersection pour en faire un treillis distributif. Dénombrer les antichaînes d'un ensemble est un problème #P-complet. On peut noter que pour tout ensemble partiellement ordonné, l'intersection d'une antichaîne et une chaîne ne peut contenir au plus qu'un seul élément. Par le principe des tiroirs, on en déduit que si l'on partitionne cet ensemble en un nombre de chaînes (resp. d'antichaînes), alors la plus longue antichaîne (resp. chaîne) ne peut être de cardinal supérieur à . De façon intéressante les deux bornes sont atteintes et ceci amène à définir la largeur et la hauteur de l'ensemble. Le cardinal de la plus grande antichaîne d'un ensemble partiellement ordonné est la largeur de cet ensemble. De par le théorème de Dilworth, la largeur correspond aussi au nombre minimale de chaînes nécessaires pour partitionner l'ensemble. Par dualité, la hauteur d'un ensemble partiellement ordonné correspond à la longueur de la plus grande chaîne de cet ensemble et au nombre minimal d'antichaînes nécessaire pour le partitionner, c'est le théorème de Mirsky. Les antichaînes d'un ensemble totalement ordonné sont les singletons et l'ensemble vide. Par conséquent, la largeur d'un ordre total est 1. Soit l'ensemble des parties d'un ensemble donné , muni de la relation d'inclusion, on appelle famille de Sperner une antichaîne de .

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (5)

Concepts associés (7)

, ,

Distributionally robust chance constrained programs minimize a deterministic cost function subject to the satisfaction of one or more safety conditions with high probability, given that the probability distribution of the uncertain problem parameters affec ...

2022

An extremal problem on crossing vectors

Bartosz Maria Walczak, Michal Lason

For positive integers w and k, two vectors A and B from Z(w) are called k-crossing if there are two coordinates i and j such that A[i] - B[i] >= k and B[j] - A[j] >= k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k-crossing ...

Academic Press Inc Elsevier Science2014

Species-specific detection of the antiviral small-molecule compound CMA by STING

Andrea Ablasser

Extensive research on antiviral small molecules starting in the early 1970s has led to the identification of 10-carboxymethyl-9-acridanone (CMA) as a potent type I interferon (IFN) inducer. Up to date, the mode of action of this antiviral molecule has rema ...

2013

Order theory

Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary. Orders are everywhere in mathematics and related fields like computer science. The first order often discussed in primary school is the standard order on the natural numbers e.

Birkhoff's representation theorem

This is about lattice theory. For other similarly named results, see Birkhoff's theorem (disambiguation). In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets. The theorem can be interpreted as providing a one-to-one correspondence between distributive lattices and partial orders, between quasi-ordinal knowledge spaces and preorders, or between finite topological spaces and preorders.

Dedekind number

File:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|right|[[File:Loupe light.svg|15px|link=http://upload.wikimedia.org/wikipedia/commons/thumb/5/57/Monotone_Boolean_functions_0%2C1%2C2%2C3.svg/1500px-Monotone_Boolean_functions_0%2C1%2C2%2C3.svg.png]] The free distributive lattices of monotonic Boolean functions on 0, 1, 2, and 3 arguments, with 2, 3, 6, and 20 elements respectively (move mouse over right diagram to see description) circle 659 623 30 [[File:Boolean function 0000 0000.