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
      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

      Identifiers