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

Bearbeiten

  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.

Existenz

Bearbeiten

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

Beispiele

Bearbeiten

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
  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]).