Monotone Grapheigenschaft
Als monotone Grapheigenschaft oder monotone Grapheneigenschaft bezeichnet man in der Graphentheorie eine Eigenschaft von Graphen, die für jeden Teilgraphen eines Graphen gilt, sobald der Graph selbst diese Eigenschaft hat.
Beispiele monotoner Eigenschaften
BearbeitenEigenschaften
BearbeitenNach dem Satz von Bollobás besitzt jede monotone Grapheneigenschaft eine Schwellenfunktion.[1]
Literatur
Bearbeiten- Béla Bollobás: Hereditary and Monotone Properties of Graphs. doi:10.1007/978-3-642-60406-5_7
- Ehud Friedgut, Gil Kalai: Every monotone graph property has a sharp threshold
- Noga Alon, Asaf Shapira: Every monotone graph property is testable
- B. Bollobás, A. G. Thomason: . In: . Band 7, Nr. 1, 1. März 1987, ISSN 1439-6912, S. 35–38, doi:10.1007/BF02579198
Einzelnachweise
Bearbeiten- ↑ B. Bollobás, A. G. Thomason: Threshold functions. In: Combinatorica. Band 7, Nr. 1, 1. März 1987, ISSN 1439-6912, S. 35–38, doi:10.1007/BF02579198.