Schwellenfunktion

Schwellenfunktionen sind ein Hilfsmittel bei der Behandlung zufälliger Graphen in der Graphentheorie.

Sie geben die Grenze $\hat{p}$ an, ab der ein zufällig erzeugter Graph mit Kantenwahrscheinlichkeit $\hat{p}$ eine feste Grapheneigenschaft fast sicher erfüllt.

Definition

$\hat{p}(n)$ ist eine Schwellenfunktion für eine Grapheneigenschaft $P$, wenn

$\underset{n\to \mathrm{\infty }}{\lim }(\mathbb{P}(𝒢(n,p(n))\in P)=\{\begin{array}{cc}0,& \text{falls }\lim \frac{p(n)}{\hat{p}(n)}=0\text{ für }n\to \mathrm{\infty }\\ 1,& \text{falls }\lim \frac{p(n)}{\hat{p}(n)}=\mathrm{\infty }\text{ für }n\to \mathrm{\infty }\end{array}$

Der obere Fall tritt ein, wenn die Kantenwahrscheinlichkeit langsamer als die Schwellenfunktion wächst, im unteren Fall wächst sie schneller.

Existenz

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

Beispiele

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 $H$ isomorphen Teilgraphen zu enthalten, bei $\hat{p}(n)=n^{-\frac{1}{{ϵ}^{\prime }(H)}}$liegt, wobei ${ϵ}^{\prime }(H)=max\{\frac{\mid E(H^{\prime })\mid }{\mid V(H^{\prime })\mid }:H^{\prime }\subseteq H\}$.

Dies gibt uns als Schwellenfunktion für die Eigenschaft einen Kreis (mit Länge $k\ge 3$) zu enthalten, $\hat{p}(n)=n^{-1}$.