Concept

Théorème de Dilworth

Le théorème de Dilworth en théorie des ordres et en combinatoire, dû à Robert Dilworth, caractérise la largeur de tout ordre (partiel) fini en termes d'une partition de cet ordre en un nombre minimum de chaînes. Dans un ensemble ordonné, une antichaîne est une partie dont les éléments sont deux à deux incomparables et une chaîne est une partie dont les éléments sont deux à deux comparables. Le théorème de Dilworth établit, pour un ordre fini, l'existence d'une antichaîne A et d'une partition de l'ensemble ordonné en une famille P de chaînes, telles que A et P aient même cardinal. Pour de tels A et P, A est nécessairement une antichaîne de cardinal maximum (puisque toute antichaîne a au plus un élément dans chaque membre de P) et P est nécessairement une partition en chaînes de cardinal minimum (puisque toute partition en chaînes a au moins une chaîne par élément de A). La largeur de l'ordre partiel (i.e. la taille maximum d'une antichaîne) peut donc être redéfinie comme le cardinal commun de A et P, ou comme la taille minimum d'une partition en chaînes. Une généralisation de ce théorème établit qu'un ordre (non nécessairement fini) est de largeur finie w si et seulement s'il peut être partitionné en w chaînes, mais pas moins. La preuve suivante, par récurrence sur la taille de l'ensemble partiellement ordonné S, s'inspire de celle de Galvin. Le résultat est immédiat si S est vide. Supposons donc S non vide, notons a l'un de ses éléments maximaux, et appliquons l'hypothèse de récurrence à l'ensemble ordonné T = S \ {a}. Il existe, pour un certain entier k, une partition de T en k chaînes C, ... , C, et une antichaîne A de T de cardinal k. Pour chaque i de 1 à k, il existe dans C des éléments appartenant à au moins une antichaîne de T de taille k (par exemple : les éléments communs à C et A) ; soient x le plus grand d'entre eux et A une telle antichaîne associée. Alors, l'ensemble A = {x, ... , x} est une antichaîne. En effet, pour tous indices i et j distincts, il existe au moins un y commun à A et C, et un tel élément vérifie y ≤ x (par définition de x), donc (puisque x ≱ y).

À 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.
Séances de cours associées (4)
Administration publique et mesure économique
Explore l'impact des choix de mesure économique sur la visibilité et la gouvernance des données, en soulignant l'importance de définir des catégories pour la compréhension et l'élaboration des politiques.
Ordre partiel: Relations, Séquences, Somme
Explore les ordres partiels, les relations de divisibilité, les réseaux, l'ordre lexicographique, la comparabilité et les ordres totaux.
Relations d'équivalence et ordres partiels
Introduit des relations d'équivalence, des partitions, des ordres partiels et des concepts d'ordre total avec des exemples et des définitions.
Afficher plus
Publications associées (13)

Modeling Structured Data in Attention-based Models

Alireza Mohammadshahi

Natural language processing has experienced significant improvements with the development of Transformer-based models, which employ self-attention mechanism and pre-training strategies. However, these models still present several obstacles. A notable issue ...
EPFL2023

Improved Ramsey-type results for comparability graphs

Istvan Tomon, Dániel József Korándi

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...
CAMBRIDGE UNIV PRESS2020

Edge Ordered Turan Problems

Gábor Tardos, Abhishek Methuku

We introduce the Turan problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge or ...
COMENIUS UNIV2019
Afficher plus
Personnes associées (1)
Concepts associés (5)
Mirsky's theorem
In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially ordered set in terms of a partition of the order into a minimum number of antichains. It is named for and is closely related to Dilworth's theorem on the widths of partial orders, to the perfection of comparability graphs, to the Gallai–Hasse–Roy–Vitaver theorem relating longest paths and colorings in graphs, and to the Erdős–Szekeres theorem on monotonic subsequences.
Perfect graph theorem
In graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by , and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs. A perfect graph is an undirected graph with the property that, in every one of its induced subgraphs, the size of the largest clique equals the minimum number of colors in a coloring of the subgraph.
Théorème de Kőnig (théorie des graphes)
vignette|Exemple d'un graphe biparti avec un couplage maximum (en bleu) et une couverture de sommets minimale (en rouge), tous les deux de taille 6. Le théorème de Kőnig est un résultat de théorie des graphes qui dit que, dans un graphe biparti, la taille du transversal minimum (i. e. de la couverture par sommets minimum) est égale à la taille du couplage maximum. La version pondérée du théorème est appelée théorème de Kőnig-. Un couplage d'un graphe G est un sous-ensemble d'arêtes de G deux-à-deux non adjacentes ; un sommet est couplé s'il est extrémité d'une arête du couplage.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.