|
|
Современные проблемы теории чисел
1 сентября 2011 г. 12:45, г. Москва, МИАН, комн. 530 (ул. Губкина, 8)
|
|
|
|
|
|
Telling graph properties from its largest eigenvalue
V. F. Lev |
Количество просмотров: |
Эта страница: | 200 |
|
Аннотация:
The spectrum is an important characteristic of a graph, encoding many of its intrinsic properties. In this talk we give an interpretation to the maximal eigenvalue of a graph (also known as its “spectral radius”), showing that it is equal, up to a logarithmic factor, to the quantity
$$
\max_{X,Y}\frac{e(X,Y)}{\sqrt{|X||Y|}},
$$
where the maximum is taken over all pairs of (non-empty, not necessarily disjoint) subsets of the vertex set of the graph, and $e(X,Y)$ denotes the number of edges between $X$ and $Y$.
|
|