No label defined (Q4792913)
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 1870235
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1870235 |
Statements
13 June 2003
0 references
random graph
0 references
random walk
0 references
generalized \(n\)-cube
0 references
0.7777460813522339
0 references
0.7776628136634827
0 references
0.7746451497077942
0 references
Let \(K_s^n\) be the graph defined as the Cartesian product of \(n\) copies of \(K_s\). The author studies induced subgraphs \(\Gamma\) of \(K_s^n\) obtained by selecting the vertices of \(K_s^n\) independently with probability \(n^{-a}\) for some \(0\leq a< 0.5\). The emphasis is put on the relationship between \(d_{\Gamma}(X,Y)\), the distance between vertices \(X\) and \(Y\) in \(\Gamma\), and \(d_{K_s^n}(X,Y)\), the distance between these vertices in \(K_s^n\). The main result is that almost surely \[ d_{\Gamma}(X,Y)\leq \left(2\left\lceil{1+3a\over 1-2a}\right\rceil+3\right)d_{K_s^n}(X,Y). \]
0 references