Schwellenfunktion
Schwellenfunktionen sind ein Hilfsmittel bei der Behandlung zufälliger Graphen in der Graphentheorie.
Sie geben die Grenze an, ab der ein zufällig erzeugter Graph mit Kantenwahrscheinlichkeit eine feste Grapheneigenschaft fast sicher erfüllt.
Definition
Bearbeitenist eine Schwellenfunktion für eine Grapheneigenschaft , wenn
Der obere Fall tritt ein, wenn die Kantenwahrscheinlichkeit langsamer als die Schwellenfunktion wächst, im unteren Fall wächst sie schneller.
Existenz
BearbeitenBéla Bollobás zeigte bereits 1985, dass jede monotone Grapheneigenschaft eine Schwellenfunktion besitzt.[1]
Beispiele
BearbeitenNach dem Satz von oben sind alle monotonen Eigenschaften Schwellenfunktionen, dazu gehören beispielsweise Planarität oder Bipartitheit.
Erdös und Renyi zeigten 1960, dass die Schwellenfunktion für die Grapheneigenschaft, einen zu einem festen Graphen isomorphen Teilgraphen zu enthalten, bei liegt, wobei .[2]
Dies gibt uns als Schwellenfunktion für die Eigenschaft einen Kreis (mit Länge ) zu enthalten, .
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.
- ↑ Reinhard Diestel: Graphentheorie. 5. Auflage. Springer Spektrum, 2017, ISBN 978-3-662-53633-9 (springer.com [abgerufen am 6. Oktober 2019]).