Threshold function

Threshold functions are an aid in the treatment of random graphs in graph theory .

They indicate the limit from which a randomly generated graph with edge probability almost certainly fulfills a fixed graph property. ${\displaystyle {\widehat {p}}}$ ${\displaystyle {\widehat {p}}}$

definition

${\displaystyle {\widehat {p}}(n)}$is a threshold function for a graph property if ${\displaystyle P}$

${\displaystyle \lim _{n\to \infty }(\mathbb {P} ({\mathcal {G}}(n,p(n))\in P)={\begin{cases}0,&{\text{falls }}\lim {\frac {p(n)}{{\widehat {p}}(n)}}=0{\text{ für }}n\rightarrow \infty \\1,&{\text{falls }}\lim {\frac {p(n)}{{\hat {p}}(n)}}=\infty {\text{ für }}n\rightarrow \infty \end{cases}}}$

The upper case occurs when the edge probability grows more slowly than the threshold function, in the lower case it grows faster.

existence

Already in 1985 Béla Bollobás showed that every monotonous graph property has a threshold function.

Examples

According to the above theorem, all monotonic properties are threshold functions, including for example planarity or bipartite .

Erdös and Renyi showed in 1960 that the threshold function for the graph property of containing a subgraph that is isomorphic to a fixed graph is, where . ${\displaystyle H}$ ${\displaystyle {\hat {p}}(n)=n^{-{\frac {1}{\epsilon '(H)}}}}$ ${\displaystyle \epsilon '(H)=max\{{\frac {\mid {E(H')}\mid }{\mid {V(H')}\mid }}:H'\subseteq H\}}$

This gives us as a threshold function for the property of containing a circle (with length ) . ${\displaystyle k\geq 3}$ ${\displaystyle {\hat {p}}(n)=n^{-1}}$

Individual evidence

1. ^ B. Bollobás, AG Thomason: Threshold functions . In: Combinatorica . tape 7 , no. 1 , March 1, 1987, ISSN  1439-6912 , pp. 35-38 , doi : 10.1007 / BF02579198 .
2. ↑ Reinhard Diestel: Graph theory . 5th edition. Springer Spectrum, 2017, ISBN 978-3-662-53633-9 ( springer.com [accessed October 6, 2019]).