Schwellenfunktion

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

ist 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.

Béla Bollobás zeigte bereits 1985, dass jede monotone Grapheneigenschaft eine Schwellenfunktion besitzt.[1]

Nach 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 | Quelltext bearbeiten]
  1. 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.
  2. Reinhard Diestel: Graphentheorie. 5. Auflage. Springer Spektrum, 2017, ISBN 978-3-662-53633-9 (springer.com [abgerufen am 6. Oktober 2019]).