No label defined (Q3708047)

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 3933115
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3933115

      Statements

      0 references
      0 references
      1984
      0 references
      concentrated family of graphs
      0 references
      Laplace operator of a graph
      0 references
      eigenvalue of a graph
      0 references
      [For the entire collection see Zbl 0564.00010.] Let \(G_ i=(V_ i,E_ i)\) be a family of graphs and let \(\rho_ i\) be the diameter of \(G_ i\). If \(A\subseteq V_ i\), \(\rho >0\) and \(\rho\) (v,A) \((v\in V_ i)\) is the distance between v and A in \(G_ i\), define \(A_{\rho}=\{v\in V_ i:\) \(\rho\) (v,A)\(\leq \rho \}\) and \[ \alpha (i,\rho)=1-\min \{| A_{\rho}| /| V_ i|:\quad A\subseteq V_ i,\quad \mu (A)=| A| /| V_ i| \geq 1/2\}. \] The family \(\{G_ i\}\) is called to be a Levy-family if for every \(\epsilon >0\lim_{i\to \infty}\alpha (i,\epsilon \rho_ i)=0\). It is called a concentrated (Levy) family if there are constants c, h such that for every i \(\alpha(i,\rho)\leq c\cdot \exp (-[h\rho /\sqrt{\rho_ i}])\). This definition is a generalization to graphs of a similar notion from metric probability spaces [see \textit{M. Gromov} and \textit{V. D. Milman}, Am. J. Math. 105, 843-854 (1983; Zbl 0522.53039), and \textit{V. D. Milman} and \textit{G. Schechtman}, Lect. Notes Math. (to appear)]. In this paper a general method is developed to prove that various families of graphs are concentrated. It uses the least and the second least eigenvalue of a graph, and a matrix associated to a graph. In particular it is proved that the family of graphs of \(\ell\)-dimensional cubes (\(\ell \to \infty)\) as well as a family of Cayley graphs on the groups \(SL(n,Z_ p)\) \((Z_ p=Z/pZ\), \(p\to \infty)\) are concentrated. The last result is proved using the theory of group representations.
      0 references

      Identifiers