Threshold Functions for Random Graphs on a Line Segment (Q4819249)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2103166
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Threshold Functions for Random Graphs on a Line Segment |
scientific article; zbMATH DE number 2103166 |
Statements
Threshold Functions for Random Graphs on a Line Segment (English)
0 references
24 September 2004
0 references
random graph
0 references
geometric graph
0 references
threshold
0 references
0.8114092350006104
0 references
0.8045421242713928
0 references
0.7884964942932129
0 references
0.7876710891723633
0 references
There has been much interest in recent years in models of random graphs where \(n\) points are chosen at random in some space and two such are said to be adjacent if the distance (in some metric) between them is at most \(r(n)\). See, for example, \textit{M. Penrose} [Random geometric graphs (Oxford Studies in Probability 5, Oxford University Press, Oxford) (2003; Zbl 1029.60007)] for a recent book giving much information about this area (though he mainly concentrates on the case where the space is in \({\mathbb R}^{d}\), \(d\geq 2\)). The paper under review is a contribution to this theory when the \(n\) points \(v_{1},\ldots ,v_{n}\) are independent and uniformly distributed in the unit interval \([0,1]\) and two are adjacent if and only if \(| v_{i}-v_{j}| <\delta\). The resulting graph \(G_{n,\delta}\) is called Model RN. Model RN is not always terribly tractable, so the first step is to introduce a model which is \` similar\' , Model RN*. In it, we start with \(n\) independent exponential random variables \(\{\zeta_{i} \}_{i=1}^{n}\), form \(\xi_{t}=\sum_{i=1}^{t}\zeta_{i}\) and then form a random graph \(G_{n,\delta}^{*}\) with vertex set \(\{\xi_{i}\}_{i=1}^{n}\), with \(\xi_{i}\) adjacent to \(\xi_{j}\) if and only if \(| \xi_{i}-\xi_{j}| <\delta\). Let \(\Theta\) be a property of graphs which is upwards closed (i.e. if \(H\) is a subgraph of \(G\) and \(H\) has property \(\Theta\), then so does \(G\): such a property is called an increasing property in much of the random graphs literature). \textit{B. Bollobás} and \textit{A. Thomason} [Combinatorica 7, 35--38 (1987; Zbl 0648.05048)] showed that, in the more usual Erdős-Rényi model of random graphs \(G(n,p(n))\) with \(n\) vertices and each possible edge present with probability \(p(n)\) independently of all others, every increasing property has a threshold, i.e. a function \(p*(n)\) such that if \(p(n)\) grows faster than \(p*(n)\), then \(\lim_{n\rightarrow\infty}P\{G(n,p(n))\text{~has~}\Theta\}=1\), but if \(p(n)/p*(n)\) goes to zero, then \(\lim_{n\rightarrow\infty}P\{G(n,p(n))\) has \(\Theta\}=1\). In fact, one distinguishes strong threshold functions (where \(\lim_{n\rightarrow\infty}P\{G(n,(1-\varepsilon)p*(n)) \) has \(\Theta\}=o(1)\) and \(\lim_{n\rightarrow\infty}P\{G(n,(1+\varepsilon)p*(n))\) has \(\Theta\}=1\): an example is \` being connected\') from weak thresholds (the rest: an example is having a subgraph isomorphic to a particular fixed graph). (In fact, a result of E. Friedgut says (in hopelessly crude paraphrase) that properties of the form \` having a subgraph isomorphic to some fixed graph \(H\)\'\, are the essence of properties without a strong threshold in \(G(n,p)\).) The paper under review deals with extensions of these notions to the geometric models in the second paragraph. The author uses `weak threshold' to correspond to `threshold' in the above sense: thus \(\delta_{\Theta}(n)\) is a weak threshold for \(G_{n,\delta}\) if, when \(\delta(n)=o(\delta_{\Theta}(n))\) we have \(\lim_{n\rightarrow\infty}P\{G_{n,\delta(n)}\) has \(\Theta\}=0\) but when \(\delta_{\Theta}(n)=o(\delta(n))\) we have \(\lim_{n\rightarrow\infty}P\{G_{n,\delta(n)}\) has \(\Theta\}=1\). For example, the threshold for connectedness in \(G_{n,\delta}\) is \(\log(n)/n\). A strong threshold is now when \(\lim_{n\rightarrow\infty} P\{G_{n,(1-\varepsilon)\delta_{\Theta}(n)}\) has \(\Theta\}=0\) but \(\lim_{n\rightarrow\infty} P\{G_{n,(1+\varepsilon)\delta_{\Theta}(n)}\) has \(\Theta\}=1\). The first result is that Model RN and Model RN* have the same weak thresholds and the same strong thresholds. This is used to prove that any upwards closed property has a weak threshold in Model RN. By contrast, the author gives an example of a set \(I\subseteq \mathbb R\), of Lebesgue measure 1, for which the obvious generalisation of \(G_{n,\delta}\) to points uniformly distributed in \(I\) (Model GRN) does not even have a weak threshold for the upwards-closed property \` having no isolated vertex\' . (Thus weak thresholds are not quite as ubiquitous as one might have assumed.) The next topic is strong thresholds. It is shown that, if \(\delta(n)\geq \log(n)/n\) (the threshold for connectedness in Model RN) then that threshold is sharp. This is in clear contrast to the Erdős-Rényi model, where many properties whose thresholds are above the connectedness threshold have only weak thresholds. However, no such result can be true without a condition on the threshold: the property of (for fixed \(k>1\)) having a connected component of at least \(k\) vertices does not have a strong threshold in Model RN.
0 references