Worldlex Wiki En mathématiques combinatoires , un système d'indépendance est une paire , où est un ensemble fini et est une collection de sous-ensembles de (appelés ensembles indépendants ou ensembles réalisables ) avec les propriétés suivantes :
- L' ensemble vide est indépendant, c'est-à-dire . (Alternativement, au moins un sous-ensemble de est indépendant, c'est-à-dire .)
- Tout sous-ensemble d'un ensemble indépendant est indépendant, c'est-à-dire que pour chaque , nous avons . C'est ce qu'on appelle parfois la propriété héréditaire , ou la fermeture vers le bas .
Un autre terme pour un système d’indépendance est un complexe simplicial abstrait .
Relation avec d'autres concepts
- Une paire , où est un ensemble fini et est une collection de sous-ensembles de , est également appelée hypergraphe . Lorsque l'on utilise cette terminologie, les éléments de l'ensemble sont appelés sommets et les éléments de la famille sont appelés hyperarêtes . Ainsi, un système d'indépendance peut être défini brièvement comme un hypergraphe fermé vers le bas.
- Un système indépendant avec une propriété supplémentaire appelée propriété d'augmentation ou propriété d'échange d'ensembles indépendants donne un matroïde . L'expression suivante résume les relations entre les termes :
HYPERGRAPHES ⊃ SYSTÈMES INDÉPENDANTS = COMPLEXES ABSTRAITS-SIMPLICIAUX ⊃ MATROÏDES.
- Bondy, Adrian ; Murty, USR (2008), Théorie des graphes, Graduate Texts in Mathematics, vol. 244, Springer, p. 195, ISBN 9781846289699.
