Hereditary property

From Wikipedia, the free encyclopedia

In mathematics, a hereditary property is a property of an object, that inherits to all its subobjects, where the term subobject depends on the context. These properties are particularly considered in topology and graph theory.

1 In topology
2 In graph theory
3 In model theory
4 In matroid theory
5 References

[edit] In topology

In topology, a topological property is said to be hereditary if whenever a space has that property, then so does every subspace of it. If the latter is true only for closed subspaces, then the property is called weakly hereditary.

For example, second countability and metrisability are hereditary properties. Sequentiality and Hausdorff compactness are weakly hereditary, but not hereditary^[1]. Connectivity is not weakly hereditary.

[edit] In graph theory

In graph theory, hereditary properties and monotone properties are properties of a graph which also holds for ("inherited" by) its substructures of certain kind, depending on the context: subgraphs^[2], induced subgraphs, graph minors. To draw a distinction, in the latter two cases the terms induced-hereditary property and minor-hereditary property are used respectively.

The Robertson–Seymour theorem is equivalent to the statement that a minor-hereditary property may be characterized in terms of forbidden minors.

[edit] In model theory

In model theory and universal algebra, a class K of structures of a given signature is said to have the hereditary propery if every substructure of a structure in K is again in K. A variant of this definition is used in connection with Fraïssé's theorem: A class K of finitely generated structures has the hereditary property if every finitely generated substructure is again in K. See age.

[edit] In matroid theory

In a matroid, every subset of an independent set is again independent. This is also sometimes called the hereditary property.

[edit] References

^ *Goreham, Anthony, "Sequential Convergence in Topological Spaces
^ Peter Mihok (1999) "Reducible properties and uniquely partitionable graphs" in: Ronald L. Graham, "Contemporary Trends in Discrete Mathematics", DIMACS Series in Discrete Mathematics and Computer Science, vol. 49, ISBN 0821809636 p. 214