combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, an independence system is a pair

(V, \mathcal)

, where is a finite

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

and is a collection of

subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...

s of (called the independent sets or feasible sets) with the following properties: # The

empty set In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...

is independent, i.e.,

\emptyset\in\mathcal

. (Alternatively, at least one subset of is independent, i.e.,

\mathcal\neq\emptyset

.) # Every subset of an independent set is independent, i.e., for each

Y\subseteq X

, we have

X\in\mathcal\Rightarrow Y\in\mathcal

. This is sometimes called the hereditary property, or downward-closedness. Another term for an independence system is an

abstract simplicial complex In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely c ...

Relation to other concepts

* A pair

(V, \mathcal)

, where is a finite

and is a collection of

s of is also called a

hypergraph In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...

. When using this terminology, the elements in the set are called vertices and elements in the family are called hyperedges. So an independence system can be defined shortly as a downward-closed hypergraph. * An independence system with an additional property called the augmentation property or the independent set exchange property yields a

matroid In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...

. The following expression summarizes the relations between the terms:

HYPERGRAPHS INDEPENDENCE-SYSTEMS ABSTRACT-SIMPLICIAL-COMPLEXES MATROIDS.

References

*. Combinatorics Hypergraphs {{combin-stub