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
1984
0 references
concentrated family of graphs
0 references
Laplace operator of a graph
0 references
eigenvalue of a graph
0 references
0.7442964911460876
0 references
0.7440093755722046
0 references
0.7431805729866028
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