No label defined (Q3687407)
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 3911368
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3911368 |
Statements
1984
0 references
limit theorems for the number of s-connections and for the s-degree
0 references
Poisson-distribution
0 references
labelled graphs
0 references
random multigraphs
0 references
0.8152303695678711
0 references
0.7947790026664734
0 references
0.793222188949585
0 references
[For the entire collection see Zbl 0561.00017.] Let \({\mathcal G}=\{\xi_ 1,...,\xi_ n\}\) be a nonempty set, \({\mathcal K}=\{\kappa_{ij}=(\xi_ i,\xi_ j):\xi_ i,\xi_ j\in {\mathcal G},1\leq i<j\leq n\}\) the set of all 2-element subsets of \({\mathcal G}\). For given positive integer t, let \({\mathcal K}_ t={\mathcal K}\times \{1,...,t\}\) with elements \(\kappa_{ijl}=((\xi_ i,\xi_ j), l),\) \(1\leq l\leq t\). For every \({\mathcal H}\subseteq {\mathcal K}_ t,\Gamma_ t=({\mathcal G},{\mathcal H})\) is an undirected, completely labelled multigraph. The elements of \({\mathcal G}\) are the vertices and the elements of \({\mathcal H}\) are the edges of \(\Gamma_ t\). Clearly, \(0\leq N=| {\mathcal H}| \leq t\left( \begin{matrix} n\\ 2\end{matrix} \right)\) holds true, and for \(t=1\) we get simple undirected, labelled graphs \(\Gamma\). Two vertices \(\xi_ i\) and \(\xi_ j\) are called s-connected if they are connected by at least s edges in \(\Gamma_ t\); in this case the set \({\mathcal E}_{ij}=\{\kappa_{ij1},...,\kappa_{ijt}\}\cap {\mathcal H}\) is called an s-connection. The s-degree of a vertex \(\xi_ i\) is the number of vertices s-connected to it; \(\xi_ i\) is said to be s-isolated if no s-connection links it to another vertex. Now, a random mechanism is introduced basically in the same way as in the fundamental paper of \textit{P. Erdős} and \textit{A. Rényi} [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 5, 17-61 (1960; Zbl 0103.163)] by defining \(\Omega_{tnN}=\{\Gamma_{tnN}=({\mathcal G},{\mathcal H}):{\mathcal G}=\{\xi_ i,...,\xi_ n\},{\mathcal H}\subseteq {\mathcal K}_ t,| {\mathcal H}| =N\}\) and introducing \(\Omega_{tnN}\)-valued random multigraphs whose distribution on \(\Omega_{tnN}\) is uniform: \[ P(\{\Gamma_{tnN}\})={t{n\choose 2}\choose N}^{-1}. \] Using basically the same techniques as in the author, Eine Erweiterung der Sätze vom Erdős-Renyi-Typ auf ungerichtete, vollständig indizierte Zufallsmultigraphen Ph. D. Thesis (1980; Zbl 0468.05069) and Probability theory, Proc. 6th Conf., Braşov/Romania 1979, 417-425 (1981; Zbl 0468.60017), the following propositions are proved. Let \((\Gamma_{tnN})_{n\in {\mathcal N},N=N(n)}\) be a sequence of random multigraphs. For \[ N(n)=[\frac{t}{2\left( \begin{matrix} t\\ s\end{matrix} \right)^{1/s}}\quad n^{2- 1/s}(c+o(1))^{1/s}]\quad (c>0) \] the s-degree of any vertex \(\xi_ i\) is asymptotically Poisson-distributed with parameter c. For \[ N(n)=[\frac{t}{2\left( \begin{matrix} t\\ s\end{matrix} \right)^{1/s}}\quad n^{2-2/s}(c+o(1))^{1/s}]\quad (c>0) \] the expected number of s-connections tends to c/2.
0 references